12
правок
Изменения
Новая страница: «{{Определение |definition = Ациклический граф - граф, в котором нет циклов. }} {{Определение |definition =…»
{{Определение
|definition =
Ациклический граф - граф, в котором нет циклов.
}}
{{Определение
|definition =
Дерево - это связный ациклический граф.
}}
{{Определение
|definition =
Граф, не содержащий циклов, называется лесом.
}}
{{Теорема
|statement=
Для графа <math>G</math> следующие утверждения эквивалентны:
1) <math>G</math> - дерево;
2) любые две вершины в <math>G</math>соединены единственной простой цепью;
3) <math>G</math> связный граф и <math>p = q + 1</math>;
4) <math>G</math> ациклический граф и <math>p = q + 1</math>;
5) <math>G</math> - ациклический граф, и если любую праву несмежных вершин соединить ребром x, то в графе <math>G + x</math> будет точно один простой цикл;
6) G - связный граф, отличный от K<sub>p</sub> для p <tex>\ge</tex> 3, и если любую пару несмежных вершин соеденить ребром х, то в графе G + x будет точно один простой цикл;
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=
}}
'''Следствие'''
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.
|definition =
Ациклический граф - граф, в котором нет циклов.
}}
{{Определение
|definition =
Дерево - это связный ациклический граф.
}}
{{Определение
|definition =
Граф, не содержащий циклов, называется лесом.
}}
{{Теорема
|statement=
Для графа <math>G</math> следующие утверждения эквивалентны:
1) <math>G</math> - дерево;
2) любые две вершины в <math>G</math>соединены единственной простой цепью;
3) <math>G</math> связный граф и <math>p = q + 1</math>;
4) <math>G</math> ациклический граф и <math>p = q + 1</math>;
5) <math>G</math> - ациклический граф, и если любую праву несмежных вершин соединить ребром x, то в графе <math>G + x</math> будет точно один простой цикл;
6) G - связный граф, отличный от K<sub>p</sub> для p <tex>\ge</tex> 3, и если любую пару несмежных вершин соеденить ребром х, то в графе G + x будет точно один простой цикл;
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=
}}
'''Следствие'''
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.
