Лекция 16. Графы

Корневые деревья

Произвольно зафиксируем некоторую вершину  дерева  и назовем ее корнем дерева. Само дерево в этом случае будем называть деревом с корнем или корневым деревом.

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

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

На рис. 4. 38 приведены примеры дерева с корнем ,  его ориентированного дерева  и сети сборки .

Деревья графов

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

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

;    .

Следовательно, существует 50 различных деревьев, покрывающих этот граф. Один из 50 остовов мультиграфа  изображен на рис. 4.39 жирными линиями.

Экстремальные графы

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

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

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

   Для решения задач такого рода разработаны достаточно эффективные алгоритмы. Далее мы воспользуемся одним из них - алгоритмом Дж. Краскала. Его суть состоит в следующем. На первом шаге выбирается первая ветвь искомого остова - это ребро графа с наименьшим (наибольшим) весом. Затем на каждом следующем шаге рассматривается минимальное (максимальное) по весу ребро и, если оно не образует цикла с ранее выбранными ветвями, вводится в остов. Построение заканчивается после отбора для остова  ребер.

Теорема 4.13. Алгоритм Краскала позволяет построить экстремальный граф любого связного графа.

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

На первом шаге выбираем самый короткий участок искомой сети дорог, связывающей поселки. Это дорога длиною 12 км между поселками П1 и П2. Затем добавляем к ней дороги между П1 и П3 (13 км), П1 и П9 (14 км), П5 и П7 (15 км), П3 и П4 (18 км). Следующее минимальное расстояние между поселками равно 19 км. Таково расстояние между П1 и П8 и между П6 и П7. Так как обе эти дороги не образуют цикла с уже отобранными дорогами, то обе они добавляются в список. Следующие по длине (25 км и 26 км) дороги между П1, П2 и П5, П6 нельзя добавлять в наш список - иначе появятся циклы: П1, П2, П3, П2 или П5, П6, П7, П5. Восьмая и последняя дорога искомого минимального остова имеет длину 28 км, она проходит между П5 и П8. Минимальный остов, связывающий девять поселков, изображен на рис. 4.40. Минимальная длина дорог, связывающих поселки, равна 138 км.

                                  Рис.4.40

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