6.8. Остовные деревья

• Определение. Остовным деревом связного неориентированного графа называется дерево являющееся подграфом графа и содержащее все его вершины (рис. 6.18).

Рис. 6.18. Связный граф и два остовных дерева

• Утверждение Дерево с вершинами содержит ребро. Доказательство. Доказательство проведем по индукции числа вершин. Заметим, что в дереве найдется вершина, степень которой равна единице (висячая вершина). Действительно, в противном случае, если степени вершин можно построить цикл, что противоречило бы определению дерева. Цикл строится следующим образом. Выполним проход по ребрам графа, начиная с произвольной вершины. Так как степени то, попав в вершину первый раз, можно всегда из нее выйти. Исходный граф — конечный и связный. Следовательно, наступит момент, когда вновь попадем в пройденную уже вершину, что доказывает существование цикла.

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

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

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

• Определение. Минимальным остовным деревом (лесом) называется остовное дерево (лес) с минимальным общим весом его ребер.