Изменения
→Доказательство эквивалентности
==Доказательство эквивалентности==
Докажем эквивалентность 1 определения с остальными:
* <tex> 1 \Rightarrow 2 </tex> Связность, очевидно, вытекает из существования пути между любыми двумя вершинами, а ацикличность из единственности. Повторив эти рассуждения в обратном порядке получим <tex> 1 \Leftarrow 2 </tex>.
* <tex> 1 \Rightarrow 3 </tex> Ацикличность получаем аналогично первому пункту. Теперь рассмотрим <tex> u </tex> и <tex> v </tex> такие, что ребра <tex> uv </tex> не существует. Между ними, как мы знаем, уже существует путь, и при добавлении нового ребра мы получим второй путь. Из существования двух различных путей вытекает существование цикла. Опять же повторив эти рассуждения в обратном порядке получим <tex> 1 \Leftarrow 3 </tex>.
==Литература==
