Рисунок 3.6 – Граф G Рисунок 3.7 – Часть графа G
Пусть H1 и H2 – две части графа G. Сумма этих частей H1UH2 есть часть, состоящая из ребер, принадлежащих H1 или H2. Пересечение D=H1
H2 – есть часть, состоящая из ребер, принадлежащих H1 и H2 одновременно. Две части не пересекаются по вершинам, если они не имеют общих вершин, и, следовательно, ребер. Части H1 и H2 не пересекаются по ребрам, если они не имеют общих ребер H1 H2=0. Если H1 и H2 непересекающиеся части графа G, то их сумма называется прямой и H1UH2=G.Бинарные отношения и графы
Бинарные отношения можно изобразить графом: вершины графа – элементы множества V, ребра графа соединяют вершины, которые находятся в отношении друг к другу.
Любой граф определяет бинарное отношение R на множестве вершин V, если для каждого ребра (a, b) выполняется aRb. Нельзя говорить о взаимнооднозначном соответствии между графами и бинарными отношениями. Пустому бинарному отношению соответствует нуль-граф О. Универсальному бинарному отношению отвечает полный граф U. Бинарному отношению aRb, где R – отрицание R (дополнительное бинарное отношение) отвечает граф G(R)=U(V) – G(R). Обратному бинарному отношению bR*a отвечает обратный граф G (R*), т. е. граф с измененной ориентацией ребер. Операции, которые вводятся для бинарных отношений, могут быть перенесены на графы.
Симметричное бинарное отношение: если aRb, то bRa.
Рефлексивность: бинарное отношение aRa соответствует графу с петлей в каждой вершине.
Транзитивность: если aRb и bRc, то aRc. Для графа это означает, что если существует ребро (a, b) и ребро (b, c), то существует ребро (a, c). Такой граф называется связным.
Свойство связности можно рассмотреть как бинарное отношение, которое:
а) рефлексивно: вершина а связана сама с собой;
б) симметрично: если вершина а связана с вершиной b, то и вершина b связана с вершиной a;
в) транзитивно: если вершина a связана с вершиной b, и b связана с вершиной с, то вершина a связана с вершиной c.
Отношение связности есть отношение эквивалентности, т. е. оно разбивает множество вершин на попарно непересекающиеся классы.
Так как каждое множество Vi – множество связанных вершин, а вершины из разных множеств Vi не связаны, то имеем разложение графа G на части, которые не пересекаются и каждая часть – связная.
Подграфы G(Vi) называются связными компонентами графа G.
Каждый неориентированный граф распадается единственным образом в прямую сумму всех своих связных компонент.
Покрывающие деревья
Граф, не содержащий циклов, называется ациклическим. Деревом называется связный граф, не содержащий циклов. Пусть VG – число элементов в множестве вершин, VL – число элементов множества ребер дерева.
Рисунок 3.8 – Дерево
VG =VL‑1
Добавим ребро – появляется цикл, удалим ребро – теряется связность. Лесом называется несвязный граф, компонентами которого являются деревья.
Пусть VLl– число элементов в множестве ребер леса, VGl – число элементов в множестве вершин леса, k – число деревьев в лесе.
VLl= VGl- k
Если дерево Т имеет корень, то дерево называется деревом с корнем. Выделим в дереве Т некоторую цепь.
Рисунок 3.9 – Дерево
Задача.
Как узнать, существуют ли циклы в графе?
Для дерева связь между числом ребер и числом вершин такова
Vl=VG‑1. Рассмотрим s= Vl-VG+1, s называется цикломатическим числом. Если граф G – дерево, то s=0, если s не равно нулю, то в графе G есть циклы.
Алгоритм построения произвольного покрывающего дерева [20]
Ограничения: в графе не должно быть петель. Букетом называется произвольное дерево в графе.
Шаг 1. Выбираем произвольное ребро и помечаем его х (красим в голубой цвет).
Шаг 2. Выбираем другое произвольное непомеченное ребро. Если оба конца ребра лежат в одном букете, красим ребро в красный цвет. В противном случае – в голубой.
Шаг 3. Если все вершины графа вошли в один букет, то процедура заканчивается, т. к. помеченные голубым ребра образуют покрывающее дерево. В противном случае – перейти к шагу 2.
Рисунок 3.10 – Граф
1 шаг: (a, d) – помечаем голубым
2 шаг: (b, e) – помечаем голубым
3 шаг: (d, e) – помечаем голубым
4 шаг: (a, b) – помечаем красным
5 шаг: (a, c) – получаем голубым
Рисунок 3.11 – Дерево
Алгоритм построения минимального и максимального покрывающего дерева [21]
Пусть каждому ребру графа G присвоена длина (вес) l (x, y) (таблица 3.1). Весом дерева называется сумма весов ребер, входящих в дерево. Минимальным деревом называется дерево с минимальным весом.
Алгоритм формируется так же, как и алгоритм построения произвольного покрывающего дерева. Но ребра просматриваются в порядке возрастания их веса.
Таблица 3.1 – Веса ребер графа
Порядок просмотра
(a, b) – 5 (b, e) – 50 упорядочим ребра по возрастанию
(c, d) – 8 (b, d) – 60
(d, e) – 10 (b, c) – 70
(c, e) – 20 (a, d) – 85
(a, c) – 50 (a, b) – 90
1 шаг: (a, b) – помечаем голубым
2 шаг: (c, d) – помечаем голубым
3 шаг: (d, e) – помечаем голубым
4 шаг: (c, e) – помечаем красным
5 шаг: (a, c) – помечаем голубым
Дерево построено!
Рисунок 3.12 – Дерево
Алгоритм построения максимального ориентированного дерева(алгоритм Эдмонса) [15]:
Шаг 1. Последовательно в произвольном порядке просматриваем вершины графа G0. Просмотр вершины заключается в том, чтобы из дуг, заходящих в эту вершину, выбрать дугу с максимальным весом. При просмотре следующих вершин к уже отобранным ранее дугам добавляются новые дуги. Если добавление ребра не нарушает свойства букета, то добавление ребер продолжается. Если новое ребро образует контур, перейти к шагу 2.
Шаг 2. В случае формирования контура строится уменьшенный граф путем стягивания дуг и вершин выявленного контура исходного графа Go в одну вершину V.
В новом графе веса ребер (xi, vi) полагаются равными
l (x, vi)=l (x, y)+l (r, s) – l (t, y),
где К – контур, а у – вершина, принадлежащая контуру.
l (x, vi) – ребро, переходящее в ребро l (x, vi)
l (r, s) – ребро, имеющее в контуре минимальный вес
l (t, y) – ребро, заходящее в вершину у и имеющее максимальный вес
Шаг 3. Выполняется тогда, когда вершины нового графа попадают в букет, а дуги образуют дерево.
Возможны 2 случая:
вершина Vo является корнем дерева, тогда необходимо рассмотреть ребра букета в новом графе совместно с ребрами контура. Удалить из рассматриваемого множества ребер ребро с минимальным весом;
если Vo не является корнем дерева – в букете нового графа имеется лишь одно ребро, заходящее в некоторую вершину Z и одно ребро контура, заходящее в ту же вершину. Удаляем ребро контура, заходящее в вершину Z.
Пример.
Рисунок 3.13 – Граф
Просмотр вершин: Букет получаемых ребер
a (da)
b (da) (cb)
c (da) (cb) (ac)
d (da) (cb) (ac) (bd)
Рисунок 3.4 – Бесконечный однородный граф 
Рисунок 3.5 – Конечный однородный граф 
, которое состоит из всех ребер графа G, не принадлежащих H.
