Подсчет деревьев. 
Деревья как частный вид графов

Теорема Кэли о числе деревьев — названное в честь А. Кэли явное выражение в теории графов для числа деревьев с данным числом пронумерованных вершин. А именно, оказывается, что на n вершинах, пронумерованных числами от 1 до р, существует ровно рр? 2 различных деревьев.

Количество деревьев на n пронумерованных вершинах оказывается также равным числу разложений р-цикла (12…р) в произведение (р-1) транспозиции, а также числу (соответствующим образом нормированных) многочленов степени n с заданными (р-1) критическими значениями общего положения. Наконец, это последнее является частным случаем топологической классификации разветвлённых накрытий сферы Римана — тем самым, подсчёт числа деревьев оказывается частным случаем вычисления чисел Гурвица, соответствующим случаю накрывающей поверхности рода 0.

Доказательство. Пусть G (X, E) — дерево с p помеченными вершинами. Для простоты предположим, что вершины пронумерованы в произвольном порядке числами 1, 2, …, p. Рассмотрим способ, позволяющий однозначно закодировать дерево G.

В соответствии с теоремой 2 дерево G имеет концевые вершины. Пусть x1 — первая концевая вершина в последовательности 1, 2, …, p и пусть e1 = (x1, y1) — соответствующее концевое ребро. Удалим из дерева вершину x1 и ребро e1. Получим новое дерево G1 с числом вершин p — 1.

Найдем теперь первую концевую вершину x2 дерева G1 в последовательности вершин 1, 2, … …, p из множества {1, 2, …, p }{x1}, далее возьмем концевое ребро e2 = (x2, y2) и удалим из G1 x2 и e2. Эту процедуру последовательно повторяем. Через (p-2) шага остается дерево из двух вершин xp-1, yp-1 и одного ребра ep-1 = (xp-1, yp-1). Рассмотрим последовательность вершин:

(G) = {y1, y2, …, yp-2}.

Очевидно, что по данному дереву последовательность строится однозначно. Покажем теперь, что по данной последовательности вершин (G) дерево G можно восстановить однозначно. В последовательности 1, 2, …, p существуют вершины, не принадлежащие (G). Выберем первую из них x1 и построим ребро e1 = (x1, y1). Затем удалим x1 из последовательности 1, 2, …, n и y1 удалим из (G). Аналогичным образом построим ребро e2 = (x2, y2). Продолжая этот процесс, мы однозначно восстановим дерево G. Рассмотрим пример.

Табл. 1

Построение кода.	Восстановление.
(G).	(G) и список вершин.

Рассмотренный пример позволяет отметить следующие две особенности:

• 1. В списке (G) вершины могут повторяться.
• 2. При восстановлении дерева последнее ребро соединяет вершину yp-2 и оставшуюся в списке 1, 2, …, p вершину не равную yp-2.

Итак, существует взаимно однозначное соответствие между множеством помеченных деревьев с p вершинами и множеством последовательностей вершин (G). Число таких последовательностей равно, очевидно, pp-2, что и требовалось доказать.

Отметим, что среди pp-2 помеченных деревьев с p вершинами могут быть и изоморфные.

Определение 3. Подграф G1(X1, E1) неориентированного графа G (X, E) называется каркасом, или остовным деревом графа G, если G1 — дерево и X = X1.

Теорема 4. Граф G (X, E) тогда и только тогда обладает каркасом, когда он связен.

Доказательство. Необходимость этого очевидна. Докажем достаточность. Пусть G (X, E) — связный граф. Выясним, есть ли в графе G такое ребро, удаление которого не нарушает связности графа G. Если таких ребер нет, то граф есть дерево в соответствии с теоремой 1. Если же такое ребро, например e, существует, то выбросим его и придем к графу G1(X, E{e}). Затем указанную процедуру проделываем с графом G1 и т. д. Через конечное число шагов будет построен, очевидно, каркас графа G. Теорема доказана.

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

Определение 4. Графом с нагруженными ребрами (нагруженным графом) называется неориентированный граф G (X, E), каждому ребру e? E которого поставлено в соответствие число (e) 0, называемое весом или длиной ребра e.

Аналогично можно определить нагруженный орграф.

Поставим задачу нахождения такого каркаса G1(X, E1) в нагруженном графе G (X, E), для которого сумма:

минимальна. Каркас с таким свойством называется минимальным каркасом. В соответствии с теоремой 4 каждый нагруженный связный граф обладает минимальным каркасом. Эта задача возникает при проектировании линий связи и электропередач, дорог, трубопроводов и т. п., когда требуется соединить системой каналов связи заданные узлы так, чтобы любые два узла были связаны (возможно, через другие узлы), а общая длина каналов связи была минимальной; при этом узлы можно считать вершинами нагруженного графа, весам ребер которого соответствует длина возможного канала связи между соответствующими узлами. Тогда искомая сеть каналов будет минимальным каркасом этого графа.