Алгоритмы построения ОСТОВа

1. Удаление ребер исходного графа; причем очередное удаляемое ребро не должно приводить к нарушению связности, но делать граф ацикличным.

Пример:

2. Добавление ребра пустому графу (количество вершин в нем должно совпадать с количеством вершин исходного графа); причем очередное добавляемое ребро не должно приводить к образованию цикла.

Пример:

3. Остовы кратчайших маршрутов: из произвольной вершины алгоритм строит не просто дерево, а геодезические до каждой вершины графа.

МАТРИЧНАЯ ТЕОРЕМА КИРХГОФА

Матрица Кирхгофа – это квадратная матрица

,

где – соответствующий элемент матрицы смежности.

Пример:

Замечание. Матрица Кирхгофа обладает следующим свойством: сумма элементов любой строки матрицы равна сумме элементов любого столбца, равна сумме всех элементов матрицы и равна нулю.

Теорема Кирхгофа.Число остовных деревьев в связном графе G порядка n (n ³ 2) равно алгебраическому дополнению любого элемента матрицы Кирхгофа.

В связном помеченном графе все алгебраические дополнения матрицы Кирхгофа равны между собой и определяют общее число помеченных остовов графа.

Следствиеиз теоремы Кирхгофа. При n ≥ 2 (где n - количество вершин графа) число остовов полного графа K_n равно .

Теорема А. Кэли (1897 г.). Число помеченных деревьев порядка n равно .

АЛГОРИТМЫ ПОИСКА ОСТОВОВ КРАТЧАЙШИХ МАРШРУТОВ

Постановка задачи.Имеется связный граф G = (V,E), заданный матрицей весов C = ||C_ij||, i, j = . Требуется найти остов с минимальным суммарным весом ребер.

Алгоритм Краскала

Ребра графа упорядочиваются в порядке не убывания их весов. На каждом шаге к пустому графу О_р, где р - количество вершин исходного графа, добавляется ребро с минимальным весом из списка. Добавляемое ребро не должно приводить к образованию цикла. Алгоритм заканчивает работу, если количество ребер в формируемом графе станет равным р – 1.

Алгоритм Прима

Отличается от алгоритма Краскала тем, что на каждом шаге строится не просто граф без циклов, но дерево.

Упорядочиваются ребра исходного графа в порядке не убывания их весов. Строится пустой граф О_р, где р - количество вершин исходного графа. На каждом шаге в граф О_р добавляется ребро из списка ребер таким образом, чтобы не образовался цикл и не нарушалась связность. Для этого список ребер каждый раз просматривается сначала. Алгоритм строит остов кратчайших маршрутов посредством разрастания поддерева T за счет присоединения очередного ребра (x_i, x_j) с наименьшим весом.

Пример:

Для заданного графа G упорядочим ребра в порядке не убывания их весов.

Ребра: Вес:

e₁ = (v₁,v₂), – 1

e₇ = (v₃,v₄) – 1

e₂ = (v₁,v₅) – 2

e₃ = (v₄,v₅) – 3

e₆ = (v₁,v₃) – 4

e₄ = (v₂,v₃) – 4

e₅ = (v₂,v₄) – 5

алгоритм Краскала	алгоритм Прима

(v₁,v₃), (v₂,v₃), (v₂,v₄) – хорды;

(v₁,v₂), (v₁,v₅), (v₄,v₅), (v₃,v₄) – ветви.

Общий суммарный вес = 7.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Определения дерева, леса.

2. Рисунки деревьев заданного порядка с указанием центральных вершин.

3. Сгенерировать все различные абстрактные, неизоморфные друг другу деревья порядка (4,7). Разделить множество деревьев на 2 подмножества с одной и двумя центральными вершинами.

4. Теорема о висячих вершинах дерева.

5. Ярусное представление деревьев.

6. Перечислить способы обходы деревьев. Найти обходы для заданного дерева.

7. Определение остова, ветвей, хорд. Алгоритмы построения остовных деревьев.

8. Остовы кратчайших маршрутов. Отличие алгоритмов Прима и Краскала.

9. Матричная теорема Кирхгофа и следствие из нее.

10. Теорема Кэли.

ЦИКЛОМАТИКА

ЭЙЛЕРОВЫ ГРАФЫ

Начало теории графов, как отмечалось ранее, связывают с так называемой задачей о кенигсбергских мостах. Эта знаменитая в свое время задача состоит в следующем. Семь мостов г. Кенигсберга (ныне Калининград) были расположены на реке Прегель так, как изображено на рисунке. Возможно ли, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту?

Сопоставим рисунку граф G, вершины которого соответствуют четырем разделяемым рекой участкам суши A, B, C и D, а ребра - мостам.

Таким образом, данную задачу на языке теории графов можно сформулировать следующим образом: существует ли в мультиграфе G цикл, содержащий все его ребра ровно раз? В 1767 г. Л.Эйлер доказал, что данная задача не имеет решения. Он сформулировал и решил общую проблему теории графов: при каких условиях связный граф содердит цикл, проходящий через каждое его ребро?

Цикл в графе G называется эйлеровым, если он содержит все ребра исходного графа. Цепь, содержащая все ребра графа, называется эйлеровой цепью.

Связный граф называется эйлеровым, если он содержит эйлеровцикл.

Пример: не эйлеров граф эйлеров граф

Теорема о существовании эйлерового цикла в графе.Связный граф G является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

Следствие №1. Если граф G эйлеров, то множество его ребер можно разбить на простые циклы.

Следствие №2. Для того чтобы связный граф G покрывался единственной эйлеровой цепью, необходимо и достаточно, чтобы он содержал ровно две вершины с нечетной степенью. Тогда цепь начинается в одной из этих вершин и заканчивается в другой.