Дерево, эквивалентные определения — различия между версиями

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

Версия 07:06, 11 октября 2010

Определение:
Ациклический граф - граф, в котором нет циклов.


Определение:
Дерево - это связный ациклический граф.


Определение:
Граф, не содержащий циклов, называется лесом.
Теорема:
Для графа [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] - ациклический граф, и если любую праву несмежных вершин соединить ребром [math]x[/math], то в графе [math]G + x[/math] будет точно один простой цикл;

6) [math]G[/math] - связный граф, отличный от Kp для [math]p \ge 3[/math], и если любую пару несмежных вершин соединить ребром [math]x[/math], то в графе [math]G + x[/math] будет точно один простой цикл;

7) [math]G[/math] - Граф, отличный от K3 [math]\cup[/math] K1 и K3[math]\cup[/math] K2, [math]p = q + 1[/math], и если любую пару несмежных вершин соединить ребром [math]x[/math], то в графе [math]G + x[/math] будет точно один простой цикл.

Следствие

В любом нетривиальном дереве имеется по крайней мере две висячие вершины.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дерево,_эквивалентные_определения&oldid=3612»