Дерево, эквивалентные определения

В теории графов Дерево - неориентированный граф, в котором две любых вершины соединены единственным простым путем. Другими словами, любой связный граф без циклов дерево.

Лес - объединение непересекающихся деревьев.

Определения

Дерево - неориентированный простой граф G, который удовлетворяет любому из эквивалентных утверждений:

• любые две вершины графа G соединены единственным простым путем
• G - связен и ацикличен
• G - ацикличен, и простой цикл формируется при добавлении любого ребра
• G - связен, и удаление любого ребра приводит к потере связности
• G - связен, и полный 3-х вершинный граф не является его подмножеством

Для примера докажем эквивалентность первых четырёх утверждений.

[math]1 \Rightarrow 2[/math] Поскольку [math]G[/math] связный граф, то любые две его вершины соединены простой цепью. Пусть [math]P_1[/math] и [math]P_2[/math] - две различные простые цепи, соединяющие вершины [math]u[/math] и [math]v[/math], и пусть [math]w[/math] - первая вершина, принадлежащая [math]P_1[/math] (при переходе по [math]P_1[/math] из [math]u[/math] в [math]v[/math]), такая, что [math]w[/math] принадлежит и [math]P_1[/math] и [math]P_2[/math], но вершина, предшествующая ей в [math]P_1[/math], не принадлежит [math]P_2[/math]. Если [math]w'[/math] - следующая за [math]w[/math] вершина в [math]P_1[/math], принадлежащая также [math]P_2[/math], то сегменты (части) цепей [math]P_1[/math] и [math]P_2[/math], находящиеся между вершинами [math]w[/math] и [math]w'[/math], образуют простой цикл в графе [math]G[/math]. Поэтому если [math]G[/math] - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепь.

[math]2 \Rightarrow 3[/math] Ясно, что граф [math]G[/math] - связный. Соотношение [math]p = q + 1[/math] докажем по индукции. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше [math]p[/math] вершин. Если же граф [math]G[/math] имеет [math]p[/math] вершин, то удаление из него любого ребра делает его несвязным, в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, общее число ребер в графе [math]G[/math] должно равняться [math]p-1[/math].

[math]3 \Rightarrow 4[/math] Предположим, что в графе [math]G[/math] есть простой цикл длины [math]n[/math]. Этот цикл содержит [math]n[/math] вершин и [math]n[/math] ребер, а для любой из [math]p - n[/math] вершин, не принадлежащих циклу,существует инцидентное ей ребро, которое лежит на геодезической , идущей от некоторой вершины цикла. Все такие ребра попарно различны; отсюда [math]q \ge p[/math], т. е. пришли к противоречию.

[math]4 \Rightarrow 1[/math] Предположим граф [math]G[/math] имеет [math]k[/math] компонент связности, и т. к. граф ациклический, то каждая компонента связности является деревом. Ввиду того, что [math]1 \Rightarrow 3[/math] [math]q = \sum \limits_{i = 1}^k (p_i - 1) = p - k[/math], где [math]p_i[/math] - количество вершин в [math]i[/math]-й компоненте связности. Учитывая, что [math]p = q + 1[/math], получаем, что [math]k = 1[/math], т. е. [math]G[/math] - дерево. }}

Литература

• Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
• Википедия — свободная энциклопедия