|
|
| Строка 18: |
Строка 18: |
| | | | |
| | ==Доказательство эквивалентности== | | ==Доказательство эквивалентности== |
| − | Докажем эквивалентность 1 определения с остальными:
| + | * <tex> 1 \Rightarrow 2 </tex> |
| | | | |
| − | * <tex> 1 \Rightarrow 2 </tex> Связность, очевидно, вытекает из существования пути между любыми двумя вершинами, а ацикличность из единственности. Повторив эти рассуждения в обратном порядке получим <tex> 1 \Leftarrow 2 </tex>. | + | * <tex> 2 \Rightarrow 3 </tex> |
| | | | |
| − | * <tex> 1 \Rightarrow 3 </tex> Ацикличность получаем аналогично первому пункту. Теперь рассмотрим <tex> u </tex> и <tex> v </tex> такие, что ребра <tex> uv </tex> не существует. Между ними, как мы знаем, уже существует путь, и при добавлении нового ребра мы получим второй путь. Из существования двух различных путей вытекает существование цикла. Опять же повторив эти рассуждения в обратном порядке получим <tex> 1 \Leftarrow 3 </tex>. | + | * <tex> 3 \Rightarrow 4 </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>.
| |
| − | | |
| − | Получив эквивалентность всех утверждений первому, по транзитивности автоматически получим эквивалентность остальных утверждений.
| |
| | | | |
| | ==Литература== | | ==Литература== |
Версия 20:03, 24 ноября 2011
| Определение: |
| Дерево — связный ациклический граф. |
| Определение: |
| Лес — граф, являющийся набором непересекающихся деревьев. |
Определения
Для графа G эвивалентны следущие утверждения:
- G - дерево
- Любые две вершины графа G соединены единственным простым путем
- G - связен, количество вершин [math]n[/math], а ребер [math] n - 1 [/math]
- G - ацикличен, количество вершин [math]n[/math], а ребер [math]n - 1[/math]
- G - ацикличен, при добавлении любого ребра для несмежных вершин появляется цикл
- G - связный граф, отличный от [math] K_p [/math] для [math] p \gt = 3 [/math], при добавлении любого ребра для несмежных вершин появляется цикл
- G - граф, отличный от [math] K_3 \cup K_1 [/math] и [math] K_3 \cup K_2 [/math], количество вершин [math]n[/math], а ребер [math]n - 1[/math], при добавлении любого ребра для несмежных вершин появляется цикл
Доказательство эквивалентности
- [math] 1 \Rightarrow 2 [/math]
- [math] 2 \Rightarrow 3 [/math]
- [math] 3 \Rightarrow 4 [/math]
Литература
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Википедия — свободная энциклопедия
