Глава 4. Задачи по теории графов

Задача 1. На строительном участке нужно создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефонные линии не мешали строительству, их решили проводить вдоль дорог. Схема участка изображена на рис.6, где бытовкам соответствуют вершины графа и указаны длины дорог между ними.

рис.6

Каким образом провести телефонные линии, чтобы их общая длина была минимальной?

Решение. Подграф графа G, содержащий все вершины графа, называется остовным. Если остовный подграф является деревом, то он называется остовным деревом. Очевидно, что наша задача заключается в построении остовного дерева, имеющего минимальную суммарную длину рёбер (минимального остовного дерева).

Длину ребра графа G будем обозначать l(e),а суммарную длину рёбер дерева T – L(T).

Рассмотрим следующий алгоритм построения остовного дерева.

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

Этот алгоритм носит название алгоритма Краскала. Докажем, что он действительно строит минимальное остовное дерево. Доказательство проведём от противного.

Пусть T – дерево, построенное с помощью алгоритма Краскала, а S- минимальное остовное дерево, и L(S)<L(T). Поскольку в графе может быть несколько минимальных остовных деревьев, то в качестве S выберем из них дерево, имеющее наибольшее число общих рёбер с деревом T. Занумеруем рёбра дерева T в том порядке, в котором они выбирались с помощью алгоритма Краскала: e₁, e₂, …, e_i, …. Пусть e_i = (a, b) – ребро с наименьшим номером в списке, не принадлежащее дереву S. В дереве S между вершинами a и b существует единственная цепь. Добавив ребро e₁ к этой цепи, получим цикл C в новом графе S₁. Поскольку T – дерево, то какое – то ребро e_p цикла C не должно принадлежать T ((рис.7) дерево T изображено сплошной линией, а дерево S – пунктирной).

рис.7.

Сравним длины ребер е_i и е_p. Ребро е_i принадлежит дереву S, следовательно оно не образует циклов с ребрами е₁, е₂,…,e_i-1, также принадлежащими дереву S. Поэтому, если бы его длина была бы меньше, чем длина ребра е_p, то на і-м шаге алгоритма было бы выбрано не ребро е_i, а ребро е_p. Следовательно, l (е_i,)≤l (е_p).В графе S₁ удалим ребро е_p. Этим самым мы разрушаем единственный цикл графа S₁ и получаем дерево S₂. Деревья S и S₂ отличаются друг от друга только ребрами е_i и e_p. Из соотношения длин этих ребер следует что L (S₂) ≤ L(S). Но дерево S было минимальным остовным дере­вом, поэтому L(S₂) = L(S) и S₂ — также минимальное остовное дерево. Мы получили противоречие с выбором дерева S, так как дерево S₂ имеет больше общих ребер с деревом T, чем дерево S. Доказано, что алгоритм Краскала в самом деле строит минимальное дерево. Теперь с помощью алгоритма построим минимальное дерево для нашего графа. На первом шаге выбираем одно из ребер (1,4) или (3,6), на втором шаге — оставшееся из них. Третьим выбирается ребро (2,3), чет­вертым — (2,5). Теперь ребром минимальной длины из оставшихся явля­ется ребро (2,6), но оно образует цикл с ранее выбранными ребрами и поэтому не попадает в дерево. Затем в минимальное дерево выбираются ребра (1,2) и (5,7). На рисунке ребра минимального дерева выделе­ны. Вдоль дорог, соответствующим выделенным ребрам, нужно прово­дить телефонные линии.

Задача 2. Почтальон должен разнести почту по всем улицам своего участка. На схеме указаны расстояния между перекрёстками. Буквой П обозначается почта (рис.8). Найдите кратчайший маршрут почтальона.

рис.8

Решение. Если бы граф G был бы эйлеровым, то маршрут почтальона определялся бы эйлеровым циклом. Но степени вершин 1 и 6 не чётные, поэтому эйлерова цикла не существует и некоторые улицы почтальон должен будет пройти дважды. Допустим, что мы нашли маршрут обхода. Если улица проходится почтальоном дважды, то добавим соответствующее ребро к графу G. Таким образом мы получим элеров мультиграф. Следовательно, для решения задачи мы должны удвоить некоторые рёбра так, чтобы степени всех вершин стали чётными. При этом сумма длин добавленных рёбер должна быть наименьшей. В нашем графе степени вершин 1 и 6 должны стать чётными. Но при удвоении некоторого ребра, выходящего из вершины 1, например рёбра (1, 2), степень вершины 2 станет нечётной и придётся удваивать какое – то ребро, выходящее из вершины 2 и т.д. процесс удваивания рёбер может окончиться только в вершине 6. Следовательно, мы должны найти кратчайшую цепь, соединяющую вершины 1 и 6, и удвоить рёбра это цепи. Такой цепью является цепь L = (1, 2, 4, 6). В полученном мультиграфе найдём эйлеров цикл, который и определит маршрут почтальона(рис.9).

рис9.