Основные свойства свободных деревьев

Глава 9 Деревья

Деревья заслуживают отдельного и подробного рассмотрения по двум причинам.

• Деревья являются в некотором смысле простейшим классом графов. Для них выполняются многие свойства, которые не всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассужде­ния оказываются намного проще. Выдвигая какие-то гипотезы при решении задач теории графов, целесообразно сначала их проверять на деревьях.
• Деревья являются самым распространенным классом графов, применяемых в программировании, причем в самых разных ситуациях. Более половины объ­ема этой главы посвящено рассмотрению конкретных применений деревьев в программировании.

9.1. Свободные деревья

9.1.1. Определения

Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Таким образом, компонентами связности леса являются деревья. ЗАМЕЧАНИЕ Прилагательное «свободное» употребляется в том случае, когда нужно подчеркнуть от­личие деревьев от других объектов, родственных деревьям: ориентированных деревьев, упорядоченных деревьев и т. д. В связном графе G выполняется неравенство q(G)  p(G) — 1. Граф G, в котором q(G)=p(G)-1, называется древовидным. В ациклическом графе G z(G) = 0. Пусть u, v — несмежные вершины графа G, х = (u, v)  Е. Если граф G + х имеет только один простой цикл, z(G + х) = 1, то граф G называется субциклическим. Пример На рис. 9.1 показаны диаграммы всех различных (свободных) деревьев с 5 вер­шинами, а на рис. 9.2 — диаграммы всех различных (свободных) деревьев с 6 вершинами Рис. 9.1. Свободные деревья с 5 вершинами Рис. 9.2. Свободные деревья с 6 вершинами

9.1 .2. Основные свойства деревьев

Следующая теорема устанавливает, что два из четырех свойств — связность, аци­кличность, древовидность и субцикличность — характеризуют граф как дерево. ТЕОРЕМА Пусть G(V, Е) — граф с р вершинами, q ребрами, k компонентами связности и z простыми циклами. Пусть далее х — ребро, соединяющее любую пару несмежных вершин в G. Тогда следующие утверждения эквивалентны: 1. G — дерево, то есть связный граф без циклов, k(G)=1&z(G)=0; 2. любые две вершины соединены в G единственной простой цепью, u, v  ! ; 3. G — связный граф, и любое ребро есть мост, k(G) = l&eЕ k(G – е) > 1;. 4. G — связный и древовидный, k(G) = l&q(G)=p(G)-l; 5. G — ациклический и древовидный, z(G) = 0&q(G)=p(G)-l; 6. G — ациклический и субциклический, z(G) =0&z(G + x) = 1; 7. G — связный, субциклический и неполный, k(G) = l&GK_p&p3&z(G + x) = 1; 8. G — древовидный и субциклический (за двумя исключениями), q(G)=p(G)-l&GK₁K₃&GK₂K₃&z(G + x) = l. доказательство [1 2.] От противного. Пусть существуют две цепи (рис. 9.3 слева). Тогда w₁, w₂ — простой цикл. Рис. 9.3. К доказательству теоремы о свойствах деревьев [2 3.] Имеем: u,v ! , следовательно, k(G) = 1. Далее от противного. Пусть ребро х — не мост. Тогда в G — х концы этого ребра связаны цепью. Само ребро х — вторая цепь. [3 4.] Индукция по p. База: р=1  q = 0. Пусть q(G) = p(G) —1 для всех графов G с числом вершин меньше р, у которых любое ребро суть мост. Тогда удалим из G ребро х (которое является мостом). Получим две компоненты G’ и G», удовлетворяющие индукционному предположению. Имеем: q’ = р’ — 1, q» = р» — 1, q = q’ + q» + 1 = р’ — 1 + р» — 1 + 1 = р — 1. [4 5.] От противного. Пусть есть цикл с n вершинами и n ребрами. Остальные р — n вершин имеют инцидентные им ребра, которые связывают их с циклом. Следовательно, q  р, что противоречит условию q = р — 1. [51.] Граф без циклов, следовательно, его компоненты — деревья. Пусть их k. Имеем: Ho q = p — 1, следовательно, k = 1. [56.] По ранее доказанному 5  1 2. Имеем: u,v ! . Соединив две несмежные вершины, получим единственный простой цикл. [67.] При р  3 граф К_р содержит цикл, следовательно, G  К_р. Далее от противного. Пусть G несвязен, тогда при соединении ребром двух ком­понент связности цикл не возникнет. [72.] Имеем k(G) = 1, следовательно, u,v  . Пусть цепь не единственная. Тогда существует цикл Z, причем Z = К₃ = C₃. Действительно, пусть Z > Сз, тогда, соединив две несмежные вершины этого цикла, получим два цикла. Но G связен и G  K₃, следовательно, существу­ет другая вершина w, смежная с Z = К₃ (см. рис. 9.3 справа). Если w смежна с более чем одной вершиной Z, то имеем больше одного цикла. Если w смежна только с одной вершиной Z, то соединив ее с другой вершиной, получим два цикла. [78.] Имеем k(G) = 1, следовательно, G  К₂  K₃, G  K₁  K₃. Имеем по доказанному: 723 4, то есть q = р — 1. [85.] От противного. Пусть в G есть цикл Z = С_n. Если n > 3, то если внутри Z уже есть смежные вершины, имеем два цикла. Если в Z нет смежных вершин, то, соединив несмежные вершины в Z, получим два цикла. Сле­довательно, Z = К₃. Этот цикл Z является компонентой связности G. Действительно, пусть это не так. Тогда существует вершина w, смежная с Z. Если w смежна более чем с одной вершиной Z, то имеем больше одного цикла. Если w смежна только с одной вершиной Z, то, соеди­нив ее с другой вершиной, получим два цикла. Рассмотрим G’: = G — Z. Имеем: р = р’ + 3, q = q’ + 3. Но q = р — 1, следовательно, q’ = р’ — 1. От­сюда z(G’) = 0, так как один цикл уже есть. Следовательно, компоненты G’ — деревья. Пусть их fc. Имеем: но q’ = p’ — 1, следовательно, k = 1, то есть дерево одно. Если в этом дереве соединить несмежные вершины, то получим второй цикл. Два исключения: деревья, которые не имеют несмежных вершин, — это К₁ и К₂. Общая схема доказательства представлена на рис. 9.4. Граф доказательства силь­но связен, следовательно, теорема доказана. Рис. 9.4. Схема доказательства теоремы о свойствах деревьев СЛЕДСТВИЕ В любом нетривиальном дереве имеются по крайней мере две ви­сячие вершины. доказательство Рассмотрим дерево G(V,E). Дерево — связный граф, следовательно, v_iV d(v_i)1. Далее от противного. Пусть i l..p — l d(v_i) > 1. Тогда . Но q = р — 1, то есть 2q = 2р — 2. Имеем противоречие: 2р — 2 > 2р — 1.

Источник

§5. Остовные деревья минимальной стоимости.

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

Остовным деревом графа называется свободное дерево , , содержащее все вершины графа .

Теорема 1. (Свойства свободных деревьев)

1. Каждое свободное дерево, имеющее n вершин (n≥1), имеет ровно n-1 ребро.

2. При добавлении в любое свободное дерево нового ребра образуется цикл.

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

В этом разделе рассматриваются методы нахождения остовных деревьев минимальной стоимости.

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

Теорема 2. (Свойство остовных деревьев минимальной стоимости).

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

Доказательство. Допустим противное: не существует остовного дерева минимальной стоимости для графа , содержащего , то есть для любого остовного дерева , содержащего его стоимость не минимальна.

Рассмотрим произвольное остовное дерево , имеющее минимальную стоимость. В частности, для него

Добавим к дереву ребро , получим , . По теореме 1(2), — граф с циклом. Цикл содержит ребро , соединяющее и , а также некоторое ребро , соединяющее и . (рис. 5.1.1)

Причем, по выбору ребра , справедливо .

Рис. 5.1.1.

Удалим ребро из дерева , получим , .

Так как удаление ребра привело к разрыву цикла, то — свободное дерево, содержащее все вершины , следовательно — остовное дерево графа , содержащее , стоимость которого . Однако, выбирая в (1) , получим . Противоречие. Значит допущение неверно. Теорема доказана.

Существуют различные способы построения остовных деревьев минимальной стоимости. Многие из них основаны на теореме 2. Далее будут рассмотрены два таких алгоритма.

5.2. Алгоритм Прима.

Пусть дан граф , . Множество вершин , входящих в остовное дерево минимальной стоимости, строится в алгоритме Прима (Prim) по следующим правилам:

1. Сначала состоит из одной произвольной вершины. Например, .

2. На каждом шаге алгоритма находится ребро наименьшей стоимости такое, что и . Ребро добавляется к дереву, вершина переносится из множества во множество .

Согласно теореме 2, существует остовное дерево минимальной стоимости графа , содержащее новое множество вместе с ребром .

3. Шаг 2 повторяется до тех пор, пока множество не станет равным множеству , то есть, пока не будет достигнуто . Это означает, что в остовное дерево будут включены все вершины графа и некоторые его ребра. По теореме 2, существует остовное дерево минимальной стоимости графа , содержащее именно те ребра, которые выбирались на шаге 2. Значит, полученное остовное дерево и является остовным деревом минимальной стоимости.

Эскиз алгоритма показан в листинге 5.2.1.

Листинг 5.2.1. Эскиз алгоритма Прима

procedure Prim ( G: граф; var T: множество ребер );

нахождение ребра (u, v) наименьшей стоимости и такого,

Для выбора ребра с наименьшей стоимостью, соединяющего множества и на каждом шаге алгоритма используются два массива. Массив CLOSEST[i] для каждой вершины i из множества содержит вершину из , с которой она соединена ребром минимальной стоимости (это ребро выбирается среди ребер, инцидентных вершине i, и которые ведут в множество ). Другой массив LOWCOST[i] хранит значение стоимости ребра (i, CLOSEST[i]).

На каждом шаге алгоритма просматривается массив LOWCOST, находится минимальное значение LOWCOST[k] (строки (5)-(10)). Вершина k принадлежит множеству и соединена ребром с вершиной из множества . Затем выводится на печать ребро (k, CLOSEST[k]) (строка (11)).

После нахождения очередной вершины k остовного дерева значение LOWCOST[k] устанавливается равным infinity (бесконечность), очень большому числу, такому, чтобы эта вершина уже в дальнейшем не рассматривалась (строка (12)). Значение числа infinity должно быть больше стоимости любого ребра графа.

Так как вершина k присоединяется к множеству , то вследствие этого изменяются массивы LOWCOST и CLOSEST (строки (13)-(16)).

Программа на языке Pascal, реализующая алгоритм Прима, представлена в листинге 5.2.2. На вход программы поступает матрица стоимостей ребер графа — массив С размера , чьи элементы C[i, j] равны стоимости ребер . Если ребра не существуют, то элемент C[i, j] полагается равным некоторому достаточно большому числу.

Листинг 5.2.2. Программа выполнения алгоритма Прима

procedure Prim ( С: аггау[1..n, 1..n] of real );

для графа с вершинами и матрицей стоимости С>

CLOSEST: array[1..n] of integer;

к — номер найденной вершины, min = LOWCOST[k] >

инцидентное ребро, оканчивающееся в множестве U >

Пример. Рассмотрим этапы построения остовного дерева минимальной стоимости для графа на рис. 5.2.1.

Рис. 5.2.1.

Решение. Результаты последовательных итераций приведем в таблице

Источник