Графы. Основные понятия.

Графом G наз. пара мн-в: G=(N,U). Эл. N наз. вершинами, а U – рёбрами. U представляет собой некоторое мн-во неупорядоченых пар вершин.

Есл мн-во N конечно, то граф наз. конечным. Рёбра вида (i,j) и (j,i) наз. паралельными, а рёбра вида (i,i) наз. петлёй. Граф наз. простым, если он не имеет параллельных рёбер и петель (Если имеет параллельные рёбра, то U – мульти мн-во). Вершины, связаные ребром наз. смежными. Если в графе имеется (i,j), то вершины i, j наз. инцедентными этому ребру и наоборот, ребро наз. инцедентным этим вершинам. Два ребра, имеющие общую вершину наз. смежными. Если в графе имеется ребро (i,j), то i, j – концевые вершины ребра (i,j). Число рёбер, инцедентных вершине наз. степенью вершины (deg(i)). Вершиа нулевой степени наз. изолированой, вершина первой степени наз. висячей. Граф, все вершины к-го имеют нулевую степень, наз. пустыми. Граф, любые две вершины к-госмежны наз. полным.

Два графа G и D наз. изоморфными : G  D, если  взаимно однозн. соотв. между их вершинами, сохр. смежность(G=(N,U), D=(M,W); f:NM; (i,j)G (f(i),f(j))W).

Очевидно что ni=1­­­deg(i)=2m, где n – число вершин, m – число рёбер.

Подграфом D графа G (DG) наз. граф, такой, что MN; WU.

Граф D наз. остовным подграфом графа G, если M=N. Пусть G=(N,U) и TN.

Вершинопорждённым подграфом графа G с порждающим мн-вом T: G(T), наз. подграфом графа G с мн-вом рёбер W: G(T)=(T,W) такой, что две вершины G(T) смежны тогда и только тогда, когда они смежны в исходном графе.

28. Содержание

    • Множества. Основные понятия.
    • Операции над множествами и их свойства.
    • Декартово произведение. Разбиение множеств.
    • Алгебра множеств
    • Отношение. Бинарное отношение
    • Алгебра бинарных отношений
    • Отображение. Виды отображений
    • Отношение порядка. Изоморфизм упорядоченных множеств.
    • Алгебраические системы. Изоморфизм алгебраических систем.
    • Функции алгебры логики.
    • Формулы. Реализация функций формулами.
    • Эквивалентность формул. Свойства элементарных булевых функций.
    • Двойственные функции. Принцип двойственности
    • Разложение булевых функций по переменным. Сднф.
    • Полнота и замкнутость.
    • Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
    • Классы т0, т1.
    • Класс s.
    • Класс м.
    • Класс l
    • Теорема о функциональной полноте. Проверка системы функций на полноту.
    • Задача минимизации булевых функций.
    • Задача минимизации булевых функций в геометрической постановке.
    • Сокращенные днф.
    • Тупиковые днф и решение задачи минимизации.
    • Графы. Основные понятия.
    • Орграфы. Основные понятия.
    • Маршруты. Цепи. Циклы. Связность.
    • Операции над графами