4.10. Деревья

Связный неориентированный граф называетсядеревом, если он не имеет циклов. Это определение исключает нали­чие на дереве петель и кратных ребер. Прямая сумма не­связных деревьев, рассматриваемая, в целом, как граф, на­зывается лесом.

В произвольном графе G вершина а называется кон­цевой, если (а) = 1. Инцидентное ей ребро называется кон­цевым ребром.

Теорема 4.8 Любое конечное дерево имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.

Доказательство. Пусть v_a — некоторая вершина де­рева. Будем обходить дерево, начиная с этой вершины так, что войдя в вершину по одному ребру, выходим из нее по другому. Так как дерево не содержит циклов, то ни одна из пройденных вершин не будет повторена. В связи с тем, что дерево конечно, процесс должен закончиться в некоторой вершине v_b. Эта вершина концевая и ей инцидентно только одно ребро, по которому в нее вошли. Если v_a также кон­цевая вершина, то имеем две концевые вершины и не менее одного концевого ребра.

Если же v_a не является концевой вершиной, то по­строим вторую цепь из v_a. По этой цепи придем к некоторой концевой вершине v_c. Вершины v_b и v_c различны, так как граф не содержит циклов. То, что построенная цепь из v_b в v_c содержит не менее одного ребра, теперь очевидно.

Теорема 4.9 Дерево с n вершинами содержит n - 1 ребро.

Доказательство проведем индукцией по n. При n = 2 утверждение очевидно. Пусть дерево G содержит n вершин. Удалим из него какую‑нибудь концевую вершину и инци­дентное ей концевое ребро. Получим новое дерево, содер­жащее n - 1 вершину и, по нашему индуктивному предположению (n - 1) -1= n - 2 ребра. Следовательно, исходное дерево содержит (n - 2) + 1 = n - 1 ребро.

Теорема 4.10 В дереве G любые две вершины v_a начала и v_b конца какого‑либо маршрута определяют цепь и притом единственную.

Доказательство. Предположим, что на дереве G имеется два маршрута, связывающих v_a и v_b. Тогда имеем цикл и G не является деревом. Это противоречие доказывает теорему.

Теорема 4.11 На n вершинах можно построить n^n-2 различных дерева.

Доказательство. Пусть V — множество вершин мощ­ности n. Обозначим элементы множества V числами

1, 2, …, n (4.7)

и построим какое‑либо дерево G на V. Для этого дерева введем символ, характеризующий его однозначно.

Согласно теореме 4.8 в G существуют концевые вер­шины. Обозначим через b₁ первую концевую вершину в пос­ледовательности (4.7), а через (а₁, b₁) — соответствующее кон­цевое ребро. Удалив из G это ребро вместе с вершиной b₁, мы получим новое дерево G₁. Для этого дерева снова най­дется в (4.7) первая концевая вершина b₂ c ребром (a₂, b₂). Будем повторять такой процесс до тех пор, пока не оста­нет­ся единственное ребро (a_{n - 1}, b_{n - 1}), соединяющее две ос­тав­шиеся вершины. Тогда символ

 (G) = [a₁, a₂, …, a_n-2] (4.8)

однозначно определяется деревом G.

Обратно, каждый символ  (G) определяет дерево G с помощью обратного построения. Если дано (4.8), то находим первую вершину b₁ в (4.7), которая не содержится в (4.8). Далее удаляем вершину a₁ из (4.8) и b₁ из (4.7) и продолжаем построение для всех оставшихся чисел из (4.8).

В (4.8) каждая вершина может принимать все воз­мо­жные значения из (4.7). Следовательно, имеем задачу раз­ме­щения из n-2 по n, что на основании теоремы 3.1 и определяет n^{n - 2} различных дере­вьев.

Теорема 4.11 представляет интерес в связи с постановкой сле­ду­ющей задачи.

Задача о минимальном соединении. Пусть для некоторого множества V населенных пунктов известна стои­мость (v_i, v_j) (i, j  n) сооружения средств информационной сети между любыми двумя городами v_i,v_j  V. Как должна быть спроектирована сеть, чтобы она обеспечивала связь между всеми городами, а ее общая стоимость была мини­мальна? Аналогичные вопросы возникают при проек­ти­ро­вании дорог, трубопроводов и т.д.. Такие задачи име­ну­ются задачами о минимальном соединении.

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

(E₁  E₂) = (E₁) + (E₂),

где E₁ и E₂ — любые непересекающиеся множества.

Задача о минимальном соединении состоит в пост­роении части графа G^*  G, содержащего все вершины G и такого, чтобы мера  = _{E  G}* (E) была минимальной.

Ясно, что G^* есть дерево ибо, предположив на­личие цикла в G^*, мы имеем возможность уменьшить , уда­лив ребро.

По теореме 4.11 решение этой задачи полным пере­бором потребует построения, n^{n - 2} деревьев. Можно значи­тельно уменьшить число вариантов, если воспользоваться простым алгоритмом, который предложил Борувка. Этот ал­горитм состоит в следующем.

Вначале находим ребро E₁ с минимальной мерой (E₁). Обозначим соответствующую ему часть дерева G₁^*. На каждом последующем шаге строим часть G_i^* при помощи добавления к G^*_{i - 1} такого ребра E_i, что оно имеет минимальную меру (E_i), а граф G^*_{i - 1} не имеет циклов. Если имеется несколько ребер одинаковой длины, то можно выбрать любое из них. Ясно, что граф G^*_{n - 1} есть остовное дерево. То, что он имеет мини­мальную меру  доказано в [5].