Некоторые общие понятия теории графов.

Определение. Граф G^,′(V′ , E′) называется подграфом графа G(V, E), если V′ .

Обозначение: Таким образом, каждая вершина в G′ является вершиной в G, и каждое ребро в G′ ребром в G.

v₁ v₂

v₃ v₄

неограф без петель подграфы первого графа.

Путь (маршрут в графе) – это совокупность ребер , которые объединены вместе вершинами так, что вдоль них можно двигаться по графу.

Определение.

Пусть G=G(V, E) – граф с вершинами v₀, v_1, v₂, ... , v_k, V и ребрами e₁, e₂ e₃ ,..., e_k E. Маршрутом на неориентированном графе G называется последовательность v₀, e₁, v₁, e₂, v₂, e₃, ..., v_{k -1}, e_k, v_k., где e_i = {v_{i – 1}, v_i}.

v₂

v₁ e₂ e₃

e₁ v₃

e₄

v₀ v₄

В дальнейшем маршрут будем обозначать через перечисление вершин.

Вершину v₀ называют началом, а v_k − концом пути. Если v₀ = v_k , то маршрут называют циклом. Маршрут, в котором все ребра попарно различны, называют простым циклом (нет повторяющихся ребер). Цикл, в котором попарно различны все его вершины (кроме начальной и конечной вершины), называется элементарным циклом.

Связный граф называется эйлеровым, если на нем существует простой цикл, проходящий через все дуги графа (простой цикл, проходящий через все дуги графа, т.е. проходящий по одному разу через каждую дугу).

Теорема (критерий эйлеровости графа). Для того, чтобы конечный связный граф был эйлеровым. необходимо и достаточно, чтобы степени всех его вершин были четными числами.

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

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

a

b c

d

Определение. Граф называется деревом, если он связен и не имеет циклов.

Определение. Несвязный неориентированный граф называется лесом.

Лес состоит из деревьев.

дерево лес.

Взвешенные графы и алгоритмы поиска кратчайшего пути.

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

Определение.

Граф, каждому ребру которого поставлено в соответствие некоторое число, называется взвешенным графом. Число, поставленное в соответствие ребру, называется весом этого ребра.

Одной из важнейших задач в теории взвешенных графов является задача о кратчайшем соединении, основанная на применении алгоритма Краскала. Краскал (род. в 1928 г. в Нью-Йорке. рассматриваемый далее алгоритм был предложен Краскалом еще на втором курсе университета.

Теорема (алгоритм Краскала).

Последовательность дуг покрывающего дерева минимального веса мжожепт быть найдена с помощью следующего алгоритма:

1. v₁ – дуга наименьшего веса из всех имеющихся, не являющаяся петлей;

2. если уже определен начальный отрезок последовательности v₁, v₂, ..., v_k-1, то дуга v_k

а) добавление дуги v_к не приводит к образованию цикла;

b) из всех дуг, удовлетворяющих условию а), дуга v_k - обладает наименьшим весом.

Применим алгоритм Краскала к графу, изображенному на рисунке. Пусть А, В, С, D, E, F – населенные пункты, линии – проектируемые участки дорог, цифры над линиями – их стоимость.

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

6 C

B 1

5 3

D

1 3 F 4 3

2

A E

6

В нашем случае выбираем v₁ = CD, v₂ = AB, v₃ = ED далее отпадает возможность выбора CE, т.к. приводит к образованию цикла. Далее v₄ = CF и отпадает возможность выбора EF, v₅ = AF, отпадает возможность выбора BC, BF, AE и процесс выбора дуг автоматически оборвался. Полученный путь изображен на рисунке. Пунктиром обозначены дуги, не вошедшие в этот маршрут. Полученный путь изображен на рисунке.

6

B C

5 1

1 F D

4 3 2

3

A E

6