Изменения
Нет описания правки
{{Определение
|definition =
'''Дерево''' — связный ациклический [[Основные определения теории графов|граф]].
}}
{{Определение
|definition =
'''Лес''' {{---}} [[Основные определения теории графов|граф]], являющийся набором непересекающихся деревьев.
}}
[[Файл:2 3.gif|300px|Пример леса]]
==Определения==
Для [[Основные определения теории графов|графа ]] G эквивалентны следующие утверждения:
# G - дерево
# Любые две вершины графа G соединены единственным простым путем
==Доказательство эквивалентности==
* <tex> 1 \Rightarrow 2 </tex> Граф связен, поэтому любые две вершнины соединены путем. Граф ацикличен, значит путь единственен, а так же [[Теорема о существовании простого пути в случае существования пути||прост]], поскольку никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.
* <tex> 2 \Rightarrow 3 </tex> Очевидно, что граф связен. Докажем по индукции, соотношение <tex>p = q + 1</tex>. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает граф <tex> G </tex> несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на еденицу больше числа ребер. Таким образом, <tex> p = q + 1 </tex>.
