Эйлеров граф.
Эйлеровой цепью называется цепь, проходящая по всем ребрам графа.
Эйлеровым циклом называется эйлеровая цепь, начинающаяся и заканчивающаяся в одной вершине.
Эйлеровым графом называется граф, содержащий Эйлеров цикл.
ТЕОРЕМА: Для того чтобы связанный граф был Эйлеровым, необходимо и достаточно, чтобы степени всех вершин были четны
Данная теорема позволяет решить задачу о Кенигсбергских мостах. Граф, соответствующий данной задаче, имеет вид
А
С D
B
Рис. 3.5 Граф «Кенигсбергские мосты»
Вершины графа (A, B, C, D) имеют степени:
(3.3)
Тогда в соответствии с теоремой Эйлера данный граф не является Эйлеровым. А это означает, что нельзя обойти все мосты г. Кенигсберга строго по одному разу, начав и закончив путь в одной точке суши.
Следствие из ТЕОРЕМЫ: Для того чтобы граф содержал Эйлеровую цепь, необходимо и достаточно, чтобы две вершины имели нечетную степень. При этом в одной из вершин цепь будет начинаться, в другой – заканчиваться.
Алгоритм фронта волны.
Пусть необходимо
найти минимальный путь из вершины
в вершину
.
Выписываются все вершины с 1 по n. Вершина помечается индексом 0.
Находится первый фронт волны
как множество вершин образа вершины
.
(3.17)
Все вершины, принадлежащие первому фронту волны, помечаются индексом 1.
Вводится счетчик шагов (фронтов волны)
.Если
или
,
то вершина
недостижима из вершины, и работа
алгоритма на этом заканчивается. В
противном смысле переходим к пункту
6.Если
,
то переходим к пункту 8. В противном
случае существует путь из вершины
в вершину
длиной в
единиц, и этот путь минимальный:
Находятся промежуточные вершины
z
по правилу:
, (3.18)
где
-
прообраз
вершины
- множество
вершин, из которых заходят дуги в вершину
Определяется
фронт волны как все непомеченные
вершины, принадлежащие образу вершин
- го фронта волны. Помечаются индексом
вершины
фронта волны. Далее осуществляется
переход к пункту 5.
Ярусно-параллельная форма графов
Граф, не имеющий контуров, может быть представлен в ярусно-параллельной форме. Ярусно-параллельная форма – это такой вид графа, у которого в верхний нулевой ярус помещены вершины, имеющие только исходящие дуги; в нижний ярус помещены вершины, имеющие только входящие дуги. На k-том ярусе помещены вершины, которые имеют входящие дуги из предыдущих ярусов, среди которых хотя бы одна дуга из (k-1)-того яруса.
Количество вершин в ярусе определяет ширину яруса. Наибольшая ширина яруса определяет ширину графа в ярусно-параллельной форме. Количество ярусов определяет высоту графа в ярусно-параллельной форме.
Алгоритм приведения графа к ярусно-параллельной форме.
Составляется матрица смежности графа.
Матрица смежности просматривается в поисках нулевых столбцов. Вершины, которым соответствуют нулевые столбцы, помещаются в нулевой ярус.
Из матрицы смежности столбцы и строки, соответствующие вершинам нулевого яруса.
Повторяется п.2 данного алгоритма до тех пор, пока не будут охвачены все вершины.
По исходной матрице смежности восстанавливаются дуги между вершинами.
Отделенными называются вершины, для которых не существует соединяющего эти вершины пути.
Неотделенными называются вершины, между которыми существует путь.
Подграфом графа называется граф вида:
(3.19)
Компонентой связности называется подграф, порождаемый множество неотделенных вершин.
ПРИМЕР
На рис. 3.10 представлен граф, имеющий две компоненты связности {1,2,3,4} и {5.6}
Рис. 3.10 Граф
Связанным графом называется граф, имеющий одну компоненту связности.
Дерево – связный неориентированный граф, в котором отсутствует цикл.
На рис. 3.11 представлены графы- деревья.
Рис. 3.11 Граф
Лесом называется граф, имеющий несколько компонентов связности, причем каждая из компонент является деревом.
Цикломатическим числом () графа называется минимальное количество ребер, которое необходимо изъять из графа, чтобы он стал деревом. Цикломатическое число определяется по формуле:
, (3.20)
где N – количество ребер,
k – количество вершин.