Графы; деревья

ДИСКРЕТНАЯ МАТЕМАТИКА ГРАФЫ. ДЕРЕВЬЯ Преподаватель: Шилова З.В. Деревья и лес 1. Определение. Связный граф, не имеющий циклов, называется деревом, а ребра дерева называются ветвями. У дерева с n вершинами есть ровно (n—1) ветка (ребро) (см. рис.1а). Рис. 1 (а, б, в). Если добавить лишь одно ребро, соединяющее две вершины дерева, то в графе появится цикл (рис.1 б). Если же убрать хотя бы одно ребро, то граф станет несвязным (рис.1 в). Рис. 1 (а, б, в). Несвязный граф без циклов называется лесом (см. рис.2). При этом любая связная часть леса является деревом. Рис. 2. Приложения графов 1.Определение покрывающего дерева. Пусть задан неориентированный граф G = (X, Е). Дерево D(Y, I) называется покрывающим деревом графа G(X, Е), если X = Y и I  E Рис. 3. Исходный граф и покрывающий его граф Задача 1. «Для заданной сети S = (G, С) построить покрывающее дерево минимального веса.» К этой задаче могут быть сведены многие практические проблемы. Например. В строящемся микрорайоне необходимо разработать схему подводки газа к домам, причем затраты на строительство должны быть наименьшими. На языке теории графов: для заданного множества домов построить схему газоснабжения таким образом, чтобы суммарная стоимость строительства была минимальной. Для решения этой задачи удобной моделью является взвешенный граф, вершины которого соответствуют домам, ребра — возможным газовым коммуникациям между ними, веса ребер — стоимости прокладки газопровода между соответствующими домами. Задача 2. «Для связного графа G(X,E) без петель построить покрывающее дерево.» Алгоритм построения покрывающего дерева. Шаг 0. Все ребра исходного графа G(X, E) неокрашены и множество связок пусто. Шаг 1. Произвольным образом выбирается ребро. Окрашиваем это ребро. Формируем из этого ребра и инцидентных ему вершин первую связку. Шаг 2. Произвольным образом выбираем следующее неокрашенное ребро. При этом возможно возникновение одной из четырех ситуаций: 2.1. Обе вершины выбранного нового ребра принадлежат выбранной ранее связке (в дальнейшем — одной из рассмотренных ранее связок). Исключаем выбранное ребро из дальнейшего рассмотрения. Переходим к шагу 3. 2.2. Одна вершина выбранного ребра принадлежит одной из связок, а другая не принадлежит ни одной из связок. Окрашиваем ребро и включаем его вторую концевую вершину в ту связку, в которую входит первая концевая вершина (наращиваем связку). Переходим к шагу 3. 2.3. Ни одна из вершин инцидентных выбранному ребру не принадлежит ни одной из связок. Окрашиваем это ребро и формируем новую связку из выбранного ребра и смежных ему вершин. Переходим к шагу 3. 2.4. Концевые вершины выбранного ребра принадлежат различным связкам. Окрашиваем это ребро. Обе связки, которые связывает рассматриваемое ребро, сливаем в одну связку и переходим к шагу 3. Шаг 3. Если все ребра графа рассмотрены, то переходим к шагу 4, иначе переходим к шагу 2. Шаг 4. Если получилась единственная связка, то она и является искомым покрывающим деревом, иначе задача не имеет решения. Конец алгоритма. Пример. Построить покрывающее дерево для графа, изображенного на рис. 4. Решение. Произвольным образом пронумеруем ребра графа, например, так, как показано выше на рис. 4. Согласно изложенному алгоритму, первое выбранное ребро (а, Ь) образует первую связку D, = {(а, Ь)}. Второе ребро (b, f) окрашивается (реализуется ситуация 2.2), а связка D, уже включает вершины a, b и f (рис. 5а). Рис. 5а Наращивается первая связка Выбор третьего ребра (с, d) реализует случай 2.3. Поэтому образовывается вторая связка D2 = {(с, d)} (рис. 5б) Рис. 5б Образовалась вторая связка Четвертое выбранное ребро (d, g), как показано на рис. 5в, наращивает вторую связку D2 = {(с, d),(d, g)}. Рис. 5в Наращивается вторая связка Рассматривая следующее ребро (а, с), видим, что реализуется случай 2.4. Это требует объединения обеих связок в одну, а именно, D = {(а, Ь), (b, f), (а, с), (с, d), (d, g)} (см. рис. 5г). Рис. 5г Связки сливаются в одну, образуя покрывающее дерево Шестое ребро в дерево не включается так же, как и все остальные ребра (случай). В итоге получаем покрывающее исходный граф дерево (см. рис.). Замечание 1. В общем случае граф может иметь более одного покрывающего дерева. Необходимость выбора наиболее подходящего дерева и приводит к задаче 1 — построению покрывающего дерева минимального веса. Замечание 2. Для построения покрывающего дерева минимального веса достаточно сохранить алгоритм решения задачи 2, но выбирать очередное ребро не произвольным образом, а строго в порядке возрастания весов. Пример. Построим минимальное покрывающее дерево для графа (рассмотренного в предыдущем примере). Рис. 6а. Исходный граф Рис. 6б. Покрывающее дерево Замечание. Вес дерева, изображённого на рис.6б составляет 15 единиц. Вес дерева, полученного в предыдущем примере 27 единиц.