Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака.

Цикл может входить только в одну компоненту связности графов.

k(G)=2

Следовательно, далее будем рассматривать связанные графы. Цикл (простой) рассматривается как множество рёбер. Разрез связного графа – это множество ребер, удаление которых делает граф не связным.

е1

С3 – {e1, e2}→k(G’)=2

е3

С3:

Простой разрез – это минимальный разрез, т.е. такой, никакое собственное подмножество которого разрезом не является. Между циклами и разрезами существует определенная двойственность. Следовательно, разрезы называют коциклами. Чем больше в графе циклов, тем труднее его разрезать. В дереве, напротив, каждое ребро является разрезом. Максимальное независимое множество циклов – это фундаментальная система циклов. Циклы фундаментальной системы называются фундаментальными, а количество циклов в данной фундаментальной системы – циклическим рангом, или циклическим числом. Обозначение: m(G). Максимальное независимое множество коциклов (разрезов) – фундаментальная система разрезов. Коциклы фундаментальной системы – фундаментальные, а количество коциклов в данной фундаментальной системе называется к-циклическим рангом, или коциклическим числом графа G. Обозначение: m^*(G).

Пусть T(V, ET) – остов графа G(V, T). Кодерево T^*(V, ET^*) остова T(V, GT) – такой подграф (остовный), что ET^* = E / ET. Кодерево не является деревом. Ребра кодерева – хорды остова.

Теорема 1.Если граф G – связный граф, то цикломатическое число определяется как: m(G) = q - p + 1, а коцикломатическое – как: m^*(G) = p - 1.

Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то это Эйлеров цикл, а граф – Эйлеров граф. Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу, то цепь – Эйлерова цепь, а граф – полуэйлеров граф. Эйлеров цикл содержит не только все ребра (по одному разу), но и все вершины графа (возможно по несколько раз). Эйлеровым может быть только связный граф.

Теорема 2.Если граф G связен и не тривиален, то справедливы следующие утверждения: 1) Граф G – Эйлеров граф; 2) Каждая вершина графа G имеет четную степень. 3) Множество ребер графа G можно разбить на простые циклы.

Чтобы убедится в наличии Эйлерова цикла, в графе необходимо и достаточно проверить, что степени всех вершин четные.

эйлеров граф

Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл – Гамильтонов, а граф – Гамильтонов граф. Гамильтонов цикл не обязательно содержит все ребра графа. Гамильтоновым может быть только связный граф.

Теорема 3 (теорема Дирака). Если в графе G(V, E) для любой вершины u из множества V d(u)іp / 2, то граф G – Гамильтонов.

гамильтонов граф

Раскраска графов. Хроматическое число. Планарность. Укладка графов. Алгоритмы раскрашивания.

Раскраска графов – приписывание цветов (например, чисел) его вершинам так, что никакие две смежные вершины не получают одинаковый цвет. Наименьшее возможное число цветов раскраски – хроматическое число. Обозначение: x(G). Очевидно, что существует m-раскраска графа G для любого m в диапазоне x(G) £ m £ p. Множество вершин одного цвета - одноцветный класс. Одноцветные классы образуют независимые множества вершин, т. е. никакие две вершины в одноцветном классе не смежны.

Теорема 1. Хроматическое число графа G не превышает максимальной степени вершин графа, увеличенной на 1. x(G) £ 1 + DG.

Граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы ребра графа при этом не пересекались. Граф – планарный, если его можно уложить на плоскость. Плоский граф – граф, уложенный на плоскости. Область, ограниченная ребрами в плоскости графа и не содержащая внутри себя вершин и ребер, – грань. Число граней плоского графа G обозначается r(G).

Планарный граф и его укладка на плоскости.

Внешняя часть плоскости также образует грань. Для графов, уложенных на некоторой поверхности, справедливо определенное соотношение между числом вершин, ребер и граней, это соотношение – Эйлерова характеристика поверхности.

Теорема 1(формула Эйлера). В связном планарном графе справедливо следующее: p - q + r = 2.

Теорема 2(о 5 красках). Всякий планарный граф можно раскрасить пятью красками.

Алгоритм раскрашивания: для раскрашивания графа применяют следующую схему рекурсивной процедуры p:

1) Выбрать в графе G некоторое максимальное множество вершин S;

2) Покрасить вершины множества S в очередной цвет;

3) Применить процедуру p к графу G – S.

Тема 18. Переключательные функции. Основные понятия и определения. Способы задания переключательных функций. Таблица истинности. Переключательные функции одного и двух аргументов. Специальные разложения ПФ.