Основы дискретной математики

Рисунок 3.8 – Дерево

VG =VL‑1

Добавим ребро – появляется цикл, удалим ребро – теряется связность. Лесом называется несвязный граф, компонентами которого являются деревья.

Пусть VLl – число элементов в множестве ребер леса, VGl – число элементов в множестве вершин леса, k – число деревьев в лесе.

VLl = V

Gl - 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)

Ребра (ac) (cb) (bd) (da) образуют контур. Минимальный вес ребра в контуре 2.

Стягиваем контур в одну вершину и рассматриваем граф:

Рисунок 3.14 – Граф

l(fe)=1

l (e, Vo)=l(ea)+2–3=3+2–3=2

l (f, Vo)=l (f, a)+2–3=-1

l (f, Vo) 1=l(fd)+2‑l (b, d)=1+2–2=1

Просмотр вершин Букет ребер

e (fe)

f (fe)

Vo (fe) (eVo)

Получили множество ребер исходного графа Go такое:

(fe) (ea) – образуют букет

(ac) (cb) (bd) (da) – образуют контур

Vo не является контуром дерева, удаляем (da), поскольку (da) – ребро из контура. Получили дерево:

(fe) (ea) (ac) (cb) (bd) с весом l=1+2+3+2+2=10

Задача о кратчайших путях

Пусть G – ориентированный граф, Е – ребра графа. Каждому ребру соответствует число.

 Скачать реферат