Деревья. 
Прикладная математика: технологии применения

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

Рис. 16.9. Иллюстрации к определению дерева.

Несвязный граф без циклов называется лесом. При этом любая связная часть леса является деревом (рис. 16.10). Могут рассматриваться и деревья с ориентированными ребрами. Ориентированное дерево называется прадеревом с корнем у, если существует путь между вершиной у и любой другой его вершиной (рис. 16.11).

Рис. 16.10. Лес.

Рис. 16.11. Прадерево с корнем У.

Пара S = (G, С), называется сетью, если G = (X, А) — произвольный ориентированный граф, С: А —" R — функция, ставящая в соответствие каждой дуге графа неотрицательное вещественное число с (а" а_;), которое в зависимости от решаемой задачи называют по-разному: весом дуги, пропускной способностью дуги, длиной дуги и т. п. Сеть иногда называют взвешенным графом, а сумму весов всех дуг — весом графа.

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