Графы деревья. Лес

Последовательность присоединяемых ребер, составляющих в конечном счете остов, - в первом столбце таблицы 1. Во втором столбце – ребра, не включаемые в остов на данном этапе построения: комментарий – в третьем столбце. Обратив внимание на то, что ребра, первоначально не присоединенные, могут впоследствии войти в остов (таковы ребра 5, 6, 7).

Ребро 8 отвергается дважды по разным причинам. Ребра 4, 8, 10, 11, 12, 13, 14, 18 – хорды.

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

Таблица 1

Обратно, пусть связный граф G c b вершинами содержит (b-1) ребер. Докажем, что G-дерево в соответствии с характеристическим свойством (2). Действительно, в противном случае, удалив некоторое число q циклических ребер, мы получили бы остов с b вершинами и (b-1 – q) ребрами, что невозможно (так как остов дерево).

Если к дереву Д добавить ребро (α, β), где α, β є Д, то в графе появится (единственный!) элементарный цикл, составленный из этого ребра и (единственной) элементарной цепи [α, β] є Д. Если удалить из дерева Д произвольное ребро (γ, δ), не удаляя вершин, то получится состоящий ровно из двух компонент связности (так как восстановление этого ребра превращает граф в связный). Любой подграф Н дерева не содержит элементарных циклов, поэтому все компоненты связности подграфа Н-деревья.