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