Дерево, эквивалентные определения — различия между версиями
Geork (обсуждение | вклад) |
Geork (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Для графа < | + | Для графа <math>G</math> следующие утверждения эквивалентны: |
| − | 1) < | + | 1) <math>G</math> - дерево; |
| − | 2) любые две вершины в < | + | 2) любые две вершины в <math>G</math>соединены единственной простой цепью; |
| − | 3) < | + | 3) <math>G</math> связный граф и <math>p = q + 1</math>; |
| − | 4) < | + | 4) <math>G</math> ациклический граф и <math>p = q + 1</math>; |
| − | 5) < | + | 5) <math>G</math> - ациклический граф, и если любую праву несмежных вершин соединить ребром x, то в графе <math>G + x</math> будет точно один простой цикл; |
| − | 6) | + | 6) G - связный граф, отличный от K<sub>p</sub> для p <tex>\ge</tex> 3, и если любую пару несмежных вершин соединить ребром х, то в графе G + x будет точно один простой цикл; |
| − | 7) | + | 7) G - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, p = q + 1, и если любую пару несмежных вершин соединить ребром x, то в графе G + x будет точно один простой цикл. |
|proof= | |proof= | ||
Версия 06:59, 11 октября 2010
| Определение: |
| Ациклический граф - граф, в котором нет циклов. |
| Определение: |
| Дерево - это связный ациклический граф. |
| Определение: |
| Граф, не содержащий циклов, называется лесом. |
| Теорема: |
Для графа следующие утверждения эквивалентны:
1) - дерево; 2) любые две вершины в соединены единственной простой цепью; 3) связный граф и ; 4) ациклический граф и ; 5) - ациклический граф, и если любую праву несмежных вершин соединить ребром x, то в графе будет точно один простой цикл; 6) G - связный граф, отличный от Kp для p 3, и если любую пару несмежных вершин соединить ребром х, то в графе G + x будет точно один простой цикл; 7) G - Граф, отличный от K3 K1 и K3 K2, p = q + 1, и если любую пару несмежных вершин соединить ребром x, то в графе G + x будет точно один простой цикл. |
Следствие
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.
