2. Задача об остове экстремального веса

Пусть G = (S,U,Ω) - связная сеть. В приложениях часто возникает задача о построении остове графа G, имеющего наименьший вес. Пусть, например, G = (S,U,Ω) служит моделью железнодорожной сети, соединяющей пункты , а - расстояние между пунктами . Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все пункты были связаны между собой телеграфной сетью и общая протяжённость линий телеграфной сети была наименьшей.

Алгоритм Прима (алгоритм ближайшего соседа) построения экстремального остовного дерева.

Пусть , т.е. - разбиение множества узлов сети на 2 непересекающиеся подмножества. Определим пошаговое расстояние между множествами следующим образом:

, (1)

где - дуга, соединяющая вершины .

Шаг 1. Присвоение начальных значений. Полагают .

Шаг 2. Обновление данных. Находится ребро , такое, что , и определяется расстояние по формуле (1).

Полагают

Шаг 3. Проверка на завершение. Если то искомый остов. Иначе переходим ко 2-му шагу.

Замечание. Если нужно получить максимальное по весу дерево, то в формуле (1) надо min заменить на max.

Пример. Построить остов с наименьшим весом для сети, заданной матрицей весов Ω.

П остроим на этой матрице сеть. Т.к.Ω - симметрическая матрица, то дан неориентированный граф.

Рис. 42

Шаг 1. .

Первая итерация.

Шаг 2. Шаг 3. , переход на начало 2-го шага.

Вторая итерация.

Шаг 2.

Шаг 3. , переход на начало 2-го шага.

Третья итерация.

Шаг 2. .

Шаг 3. , переход на начало 2-го шага.

Четвёртая итерация.

Шаг 2.

Шаг 3. , переход на начало 2-го шага.

Пятая итерация.

Шаг 2.

Шаг 3. .

Итак, получен остовный граф , его вес

Рис. 43

3. Обходы графов. Фундаментальные циклы

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

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

Необходимое и достаточное условие эйлеровости связного графа.

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

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

1. Произвольно выбирают некоторую вершину х₁ и ребро u₁, инцидентное х₁. Этому ребру присваивают номер 1. Вычёркивают это ребро u₁ и переходят в вершину х₂ по ребру u₁ = (х₁,х₂).

2. Находясь в вершине х_i, не следует выбирать ребро, соединяющее х_i с х_1, если имеется возможность иного выбора.

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

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

Пример. Построить эйлеров цикл в графе G.

Рис. 44

Решение.

Граф эйлеров, т.к.

1. Выбираем х₁ и ребро u₁ = (х₁,х₇) и присвоим ему номер 1, затем перейдём в вершину х_i = х₇.

2. Находясь в х₇, не выбираем вычёркнутое ребро 1. Из оставшихся трёх рёбер ни одно не является перешейком, поэтому выбираем любое, например в вершину х_i =х₆.

3. После восьми шагов опять приходим в вершину х₁.

Построенный цикл:

Определение. Если каждое ребро графа G входит в одну из существующих рёберно–непересекающихся цепей этого графа, то говорят, что набор таких цепей покрывает граф G.

Теорема о минимальном числе рёберно – непересекающихся цепей.

Если связный граф содержит ровно к вершин нечётной степени, то минимальное число покрывающих его рёберно –непересекающихся цепей равно к/2.

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

Теорема. Граф со степенной последовательностью (списком степеней его вершин) является гамильтоновым, если для всякого к, удовлетворяющего неравенством , истинна импликация

Теорема Оре. Если для любой пары х и у несмежных вершин графа G порядка выполняется условие , то G – гамильтонов граф.

Следствие. Если Card G = и для любой вершины х графа G выполнено неравенство , то G – гамильтонов граф.

Для ориентированных эйлеровых графов получены следующие результаты.

Теорема 1. Для связного ориентированного графа G следующие утверждения равносильны:

1. граф эйлеров;

2. для любой вершины верно равенство ;

3. граф G является объединением контуров, попарно не имеющих рёбер.

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

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

Теорема. Пусть G – сильно связный орграф порядка n>1 без петель и параллельных дуг. Если для любой пары х и у его несовпадающих несмежных вершин справедливо неравенство , то в G есть гамильтонов контур.

Фундаментальные циклы.

Пусть - неориентированный граф, содержащий n вершин, m рёбер и к компонент связности, - остов графа G. - имеет Эти рёбра называются ветвями остова . Оставшиеся рёбер ,не входящие в , называются хордами остова .

По определению дерева, если к остову добавить произвольную хорду , то в полученном графе найдётся ровно один цикл С_i, состоящий из хорды и некоторых ветвей остова . Цикл С_i называется фундаментальным циклом графа G относительно хорды остова . Множество всех фундаментальных циклов относительно хорд остова называется фундаментальным множеством циклов графа G относительно остова .

.

Пусть последовательность , всех рёбер графа G. Фундаментальному циклу С_i соответствует вектор , определённый следующим образом:

Тогда фундаментальное множество циклов С задаётся матрицей фундаментальных циклов.

которая имеет вид:

где - единичная матрица порядка - содержит лишь хорды фундаментальных циклов С_i.

Пример. Найти матрицу фундаментальных циклов графа G:

Рис. 45

Решение. Здесь m = 10, n = 7, k = 1.

Т.к. цикломатическое число равно , то для получения остова необходимо удалить 4 ребра. Пусть это будут рёбра 1,2,3 и 4. Получим остов :

Рис. 46

Остальные рёбра графа G занумеруем цифрами от 5 до 10. Из верхнего рисунка видно, что фундаментальный цикл С₁, соответствующий хорде 1, состоит из рёбер 1,6,7,8; цикл С₂ – из рёбер 2,7,9; цикл С₃ – из рёбер 3,5,7, цикл С₄ – из рёбер 4,5,7,10.

Тогда имеет вид: