§ 15. Деревья

Повторим два слова из главы о графах. Если в пути по графу ни одна вершина не встретилась дважды, такой путь называют цепью. А замкнутый путь, который вернулся в ту же вершину и ни по одному ребру не прошёл дважды, называют циклом. Цикл — это кольцо в графе: из вершины можно уйти и вернуться в неё, не повторяя рёбер. Графы без колец устроены проще остальных, и у них своё название.

Определение. Дерево — связный граф без циклов.

На рис. 1 три дерева. У первого семь вершин и шесть рёбер; оно и правда похоже на дерево, только перевёрнутое. Второе — обычная цепь: в цепи вершины не повторяются, значит, кольцу взяться неоткуда, и цепь — тоже дерево. Третье — одна вершина без рёбер: циклов нет, добираться никуда не надо — это самое простое дерево. А петли в дереве не бывает: петля — ребро из вершины в саму себя — это уже кольцо, самое короткое.

В определении два требования, и оба обязательны. Связность значит, что из любой вершины по рёбрам можно добраться до любой другой, а отсутствие циклов — что кольца нет ни одного. Стоит убрать одно требование — и дерева не получится: связный граф с кольцом деревом не будет, и граф без колец, распавшийся на две отдельные части, тоже не будет (рис.