Деревья

Неориентированное дерево. Критерии: n вершин и n − 1 ребро (при наличии связности; единственность цепи, соединяющей произвольные две вершины. Ориентированное дерево. Остовное дерево (остов). Пример орграфа без остова. Максимальный остовный лес и его построение с помощью алгоритма поиска в глубину. Алгоритм построения всех остовных деревьев графа. Понятие кратчайшего остовного дерева. Алгоритм Краскала и алгоритм Прима. Задача Штейнера.

Связный ациклический (т.е. без циклов) неориентированный граф называется неориентированным деревом (далее просто деревом).

Орграф называется ориентированным деревом (ордеревом), если выполняются условия:

1) существует выделенная вершина v0, имеющая полустепень захода 0 (корень ордерева);

2) все некорневые вершины имеют полустепень захода 1;

3) орграф не имеет контуров (т.е. является бесконтурным).

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

Все вершины ордерева распадаются на уровни. Глубиной вершины называется длина пути в эту вершину из корня. Один уровень составляют вершины одной глубины. Все дуги графа ведут с какого-либо уровня на следующий. Отметим, что в ордереве из n вершин имеется n − 1 дуга, поскольку каждой вершине можно поставить в соответствие дугу, входящую в эту вершину. Это соответствие распространяется на все вершины кроме корня. Таких вершин n−1. Стало быть, и дуг тоже n−1.

Перейдем теперь к случаю неориентированного дерева, имеющего n вершин. Зафиксируем одну из вершин v₀ этого дерева, назвав ее корнем. Тогда каждая вершина графа связывается с корнем единственной простой цепью, длина которой представляет собой ее глубину. Единственность цепи из корня в вершину позволяет, как и в случае ордерева, разделить вершины графа на уровни в соответствии с длиной цепи, связывающей вершину с корнем: единственная вершина уровня 0 — корень v₀, вершины уровня 1 — вершины, смежные с v0, вершины второго уровня — те, которые соединяются с корнем двузвенной цепью и т.д.

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

Теорема 6.1. Следующие условия эквивалентны:

• граф является деревом;

• граф связен и имеет n − 1 ребро, где n — количество вершин;

• любые две вершины графа можно соединить простой цепью, и притом единственным спо- собом.

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

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

Докажем, что любой связный граф с n вершинами и n−1 ребром есть дерево. Доказательство проведем индукцией по количеству вершин. Утверждение очевидно, например, при n = 2. Пусть утверждение доказано для всех графов с n−1 вершиной. Выберем произвольный связный n-вершинный граф с n − 1 ребром. У этого графа есть вершина v степени 1. Действительно, в противном случае, если все степени вершин не меньше 2, общая сумма степеней не менее 2n, а значит, у графа не менее n ребер. Удалим из графа вершину степени 1 и единственное ребро, инцидентное этой вершине. Получим граф из n − 1 вершины и n − 2 ребер. Этот граф связный, поскольку удаленная вершина не может быть внутренней вершиной простой цепи, а следовательно, цепь соединяющая две вершины, не проходит через удаленную вершину. В соответствии с предположением индукции он есть дерево. Тогда и исходный граф есть дерево, поскольку не имеет циклов: удаляемое ребро с тупиковым концом не может быть звеном какого-либо цикла.▶

Пусть G — связный граф. Всякий остовный подграф графа G, являющийся деревом, называется остовным деревом, или остовом

Теорема 6.2. Всякий связный неориентированный граф имеет остов.

◀Рассмотрим множество всех подграфов графа G, являющихся деревьями. Это множество конечно и упорядочено по включению. Следовательно, оно имеет максимальный элемент. По- кажем, что максимальное поддерево в G является остовным подграфом. Пусть T — подграф в G, являющийся деревом и содержащий k < n вершин. Среди вершин графа G, не включенных в T, можно выбрать вершину v, смежную с одной из вершин дерева T. В самом деле доста- точно выбрать цепь, первый конец которой находится в T, а второй — за пределами T. Тогда первая вершина, не попадающая в T будет смежна с предшествующей, относящейся к T . Итак, существует вершина v, не попадающая в T, связанная некоторым ребром {v, w} с некоторой вершиной из T. Добавив к T вершину v и ребро {v, w}, мы получим подграф G, не имеющий циклов, так как добавляемое ребро не может быть звеном цикла.

Итак, мы показали, что любой подграф-дерево, содержащий k < n вершин, не может быть максимальным. Значит, максимальный подграф-дерево содержит n вершин и является остовным. ▶

Неориентированным лесом называется граф, любая компонента связности которого является деревом. Лес — это просто ациклический граф.

Следствие 6.1. Любой граф имеет максимальный остовный лес.

◀Построим для каждой компоненты связности остов. Объединение всех этих остовов будет остовным подграфом-лесом данного графа. Предположив, что он не максимальный, мы прихо- дим к выводу, что к нему можно добавить ребро графа G, сохраняющее свойство ацикличности. Но это ребро будет относиться к одной из компонент связности, и его добавление будет означать, что к остову компоненты можно добавить ребро, сохраняя ацикличность. Но это противоречит максимальности остова.

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

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

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

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

1. Из массива лидеров выбираем первую непомеченную вершину как текущую. Если таких нет, переходим к пункту p6. Иначе переходим к следующему пункту.

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

3. Увеличиваем значение указателя на единицу и проверяем не закончился ли список смеж- ности текущей вершины. Если нет, переходим к следующему пункту. Если закончился, пере- ходим к пункту p5.

4. В списке смежности в соответствии с указателем выбираем очередную вершину. Если эта вершина помечена, пропускаем ее и переходим к пункту p3. Если это непомеченная вершина, записываем в стек номер текущей вершины и значение указателя для нее. В качестве текущей устанавливаем выбранную вершину и переходим к пункту p2.

5. Если стек пуст, переходим к пункту p1. Иначе выбираем из стека номер записанной вершины, делая ее текущей, и номер указателя для ее списка смежности. Затем переходим к пункту p3.

6. Процесс заканчиваем.

При проведении этого алгоритма выделяется часть ребер, по которым проводится переход к новой текущей вершине, которые в совокупности с пройденными вершинами образуют подграф анализируемого графа. Отметим, что каждое из таких ребер проходится ровно один раз в прямом направлении (пункт p2) и один раз в обратном (пункт p5). Если учитывать только прямой ход, то каждая вершина будет однозначно связана с одним входным ребром. Исключение составляет стартовая вершина, вход в которую выполняется на основании пункта p1. При повторном возврате к этому пункту все вершины будут помечены, поскольку граф связный. Поэтому количество ребер в подграфе на единицу меньше количества вершин. Следовательно, этот граф — дерево, причем остовное.

Итак, рассмотренный алгоритм поиска в глубину позволил построить остов связного графа. Однако роль алгоритма поиска в глубину на самом деле гораздо выше, чем поиск остова графа. Он является основой для широкого спектра алгоритмов, решающих различные задачи анализа графов.

Связный ориентированный граф может не иметь остовного ордерева хотя бы потому, что у него есть пара вершин с полустепенью захода 0. Тогда и у любого подграфа будет не ме- нее двух вершин с полустепенью захода 0, а это уже противоречит структуре дерева. Можно рассматривать подграфы-ордеревья данного орграфа и среди них есть максимальные. Просто максимальный подграф-дерево не будет остовным. Если мы применим алгоритм поиска в глу- бину, мы получим не ордерево (из-за пункта p1), а ориентированный лес. Так что утверждение теоремы остается в силе, но в ослабленном варианте.