Дерево — это граф, не содержащий циклов. Распознать дерево в изображении графа бывает не просто. На рисунке изображено дерево, рассмотрите его. Шаг 1: Найдите корень дерева.

Краткий ответ: корень дерева — вершина G.

Почему именно G. В дереве корень — это вершина, от которой все остальные вершины расходятся по ветвям, и при движении от корня нельзя вернуться назад другим путём (в дереве нет циклов). На рисунке G стоит в центре: от неё в разные стороны уходят три главные ветви — в сторону \(C\), \(F\) и \(H\). Если начать с \(G\) и идти по рёбрам «от корня», мы обойдём все вершины, а замкнутых колец не возникнет.

Например, ветвь через \(F\) ведёт к \(B\), \(J\), \(K\), \(L\); ветвь через \(C\) — к \(D\), \(A\), \(E\); ветвь через \(H\) — к \(I\). В итоге задействованы все 12 вершин: \(A, B, C, D, E, F, G, H, I, J, K, L\).

Проверка. У дерева с 12 вершинами должно быть 11 рёбер. Когда мы идём от \(G\) по ветвям, используем 11 рёбер; линии, которые замыкали бы кольцо, рёбрами дерева не являются — иначе получился бы цикл. Полезно проверить и так: мысленно удалите \(G\) — дерево распадётся на несколько частей, и внутри каждой части не будет циклов. Если бы корнем была другая вершина, то часть путей шла бы «вверх» к \(G\), а потом возвращалась бы обратно, что нарушало бы структуру дерева.

Как действовать в похожем задании. Ищите вершину, из которой «растут» основные ветви: часто она в центре рисунка или сверху. Главный признак корня: от него до любой другой вершины ровно один путь, и все рёбра можно ориентировать «от корня». Если на рисунке какая-то линия образует замкнутое кольцо, значит, это не ребро дерева — в дереве циклов быть не может.