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

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

1. Упорядочиваем ребра графа в порядке неубывания их весов.

2. Строим пустой граф , где  количество вершин исходного графа

3. На каждом шаге к текущему, уже сформированному графу, добавляем ребро исходного графа с минимальным весом. Ребро не должно образовывать цикл и нарушать связность. Для этого список ребер каждый раз просматривается, начиная с 1 ребра.

4. Алгоритм заканчивает работу, если количество ребер в формируемом графе станет равным .

Пример: алгоритм Прима

С писок ребер

e₁=(1, 2), (4, 3)  1

e₂=(1, 5)  2

e₃=(4, 5)  3

e₄=(1, 3), (2, 3)  4

e₅=(2, 4)  5

Остов кратчайших маршрутов: M=((1, 2), (1, 5),(5,4), (4,3))

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

Задание к лабораторной работе

Исходные данные: граф ,

граф .

1. Для графа составить матрицу Кирхгофа и посчитать количество помеченных остовов.

2. Для графа построить дерево обхода вершин графа (использовать алгоритм в ширину, в глубину).

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

4. Сгенерировать все различные абстрактные, не изоморфные друг другу деревья порядка (4-7).

5. Разделить множество деревьев на 2 подмножества с одной и с двумя центральными вершинами.

Алгоритм генерации варианта GV(p,X) описан в приложении А.

Контрольные вопросы

1. Привести определение дерева и леса.

2. Способы обхода деревьев.

3. Какие вершины дерева называются центром?

4. Что называется остовом?

5. Как можно определить число остовных деревьев?

6. Чем отличаются алгоритмы Краскала и Прима?

Лабораторная работа №4

Циклы и обходы

Цель работы: приобретение практических навыков в нахождении эйлеровых и гамильтоновых циклов в неориентированных графах, решение задач «китайского почтальона» и коммивояжера

Теоретическая справка

Обходы графа

Эйлеровы циклы

Эйлеров цикл – цикл, содержащий все рёбра исходного графа (каждое ребро используется ровно 1 раз).

Эйлеров граф – связный граф, содержащий эйлеров цикл.

Например:

G₁:

2раза

Теорема Эйлера или критерий существования в графе

эйлерового цикла

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

когда степени всех его вершин четны

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

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

Алгоритм построения эйлерового цикла или алгоритм Флёри

1. Начиная с любой вершины v, присваиваем ребру vu №1. Вычеркиваем это ребро из списка ребер и переходим к вершине u.

2. Пусть w  вершина, в которую мы пришли в результате выполнения шага 1 и k  номер, присвоенный очередному ребру на этом шаге. Выбираем произвольное ребро инцидентное вершине w, причем мост выбираем только в крайнем случае, если других возможностей выбора ребра не существует. Присваиваем ребру номер k+1 и вычеркиваем его. Процесс длится до тех пор, пока все ребра не вычеркнуты.

Например:

Эйлерова цепь – цепь с концевыми вершинами (a, b), начинающаяся в вершине a, заканчивающаяся в вершине b и содержащая каждое ребро исходного графа ровно 1 раз.

Гамильтоновы циклы

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

Гамильтонов граф – граф, содержащий гамильтонов цикл.

Достаточные условия существования гамильтонова

цикла в графе

Теорема Дирака

Если число вершин графа p  3 и для любой вершины выполняется условие  v_i, i = ; deg v_i  , то граф G – гамильтонов

Теорема Оре

Если число вершин графа p  3 и для любых двух несмежных вершин u и v выполняется неравенство: deg u + deg v  p, то граф G – гамильтонов

Например:

p=8, deg v_i = 3, 3 = 4.

В данном графе не выполняется условие теоремы Дирака, но существует гамильтонов цикл: M = (v ₁, v ₂, v ₃, v ₄, v ₅, v ₆, v ₇, v ₈, v ₁).

Дерево полного перебора

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

Построение дерева производится слева направо:

Граф G:

Дерево полного перебора

Гамильтоновы циклы графа G:

1. (v₁, v₂, v₃, v₄, v₅, v₁);

2. (v₁, v₅, v₄, v₃, v₂, v₁)