Следствия

1. Число попарно неизоморфных неупорядоченных корневых деревьев с ребрами не превосходит числа упорядоченных корневых деревьев и, следовательно, не превосходит .

2. Число попарно неизоморфных деревьев с ребрами не превосходит числа корневых деревьев с ребрами, так как они различаются выбором корневой вершины, следовательно, не превосходит .

Пример 7. Деревья, приведенные на рис. 20, попарно изоморфны, но различны с точки зрения корневых деревьев.

Рис. 20

Задача о соединении городов. Пусть есть городов, расстояние между каждыми двумя городами известно. Надо соединить их дорогой минимальной длины (или минимальной стоимости, если известна цена дороги между каждыми двумя городами).

Эту задачу можно сформулировать на языке теории графов, полагая города вершинами, а расстояния – ребрами графа. Пусть каждому ребру графа поставлено в соответствие положительное число , называемое мерой ребра (расстояние между городами или стоимость прокладываемой дороги). Обозначим меру графа

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

Алгоритм Краскала построения остовного дерева минимальной меры.

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

Покажем, что не будет остовных деревьев с мерой меньшей, чем мера дерева .

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

так как , иначе при построении дерева по алгоритму Краскала мы вместо ребра взяли бы ребро (ребра ) у деревьев и общие и не образует с ними цикла).

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

. Повторив эту процедуру конечное число раз, перестроим граф в и получим противоречие .

Пример 8. Найти остовное дерево минимальной меры в графе (рис. 21). Дерево, построенное по алгоритму Краскала, показано на рис. 22.

Рис. 21 Рис. 22

Определение. Циклическим рангом связного графа (или цикломатическим числом) называют число ребер, которые необходимо убрать, чтобы граф стал деревом.