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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема)
(Теорема)
Строка 33: Строка 33:
  
 
1) <tex> \to </tex> 2) Поскольку <tex>G</tex> связный граф, то любые две его вершины соединены простой цепью. Пусть <tex>P_1</tex> и <tex>P_2</tex> - две различные простые цепи, соединяющие вершины <tex>u</tex> и <tex>v</tex>,  и пусть <tex>w</tex> - первая вершина, принадлежащая <tex>P_1</tex> (при переходе по <tex>P_1</tex> из <tex>u</tex> в <tex>v</tex>), такая, что <tex>w</tex> принадлежит и <tex>P_1</tex> и <tex>P_2</tex>, но вершина, предшествующая ей в <tex>P_1</tex>, не принадлежит <tex>P_2</tex>.Если <tex>w'</tex> - следующая за <tex>w</tex> вершина в <tex>P_1</tex>, принадлежащая также <tex>P_2</tex>, то сегменты (части) цепей <tex>P_1</tex> и <tex>P_2</tex>, находящиеся между вершинами <tex>w</tex> и <tex>w'</tex>, образуют простой цикл в графе <tex>G</tex>. Поэтому если <tex>G</tex> - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепь.
 
1) <tex> \to </tex> 2) Поскольку <tex>G</tex> связный граф, то любые две его вершины соединены простой цепью. Пусть <tex>P_1</tex> и <tex>P_2</tex> - две различные простые цепи, соединяющие вершины <tex>u</tex> и <tex>v</tex>,  и пусть <tex>w</tex> - первая вершина, принадлежащая <tex>P_1</tex> (при переходе по <tex>P_1</tex> из <tex>u</tex> в <tex>v</tex>), такая, что <tex>w</tex> принадлежит и <tex>P_1</tex> и <tex>P_2</tex>, но вершина, предшествующая ей в <tex>P_1</tex>, не принадлежит <tex>P_2</tex>.Если <tex>w'</tex> - следующая за <tex>w</tex> вершина в <tex>P_1</tex>, принадлежащая также <tex>P_2</tex>, то сегменты (части) цепей <tex>P_1</tex> и <tex>P_2</tex>, находящиеся между вершинами <tex>w</tex> и <tex>w'</tex>, образуют простой цикл в графе <tex>G</tex>. Поэтому если <tex>G</tex> - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепь.
 +
 
2) <tex> \to </tex> 3) Ясно, что граф <tex>G</tex> - связный. Соотношение <tex>p = q + 1</tex> докажем по индукции. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает его несвязным, в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, общее число ребер в графе <tex>G</tex>  должно равняться <tex>p-1</tex>.
 
2) <tex> \to </tex> 3) Ясно, что граф <tex>G</tex> - связный. Соотношение <tex>p = q + 1</tex> докажем по индукции. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает его несвязным, в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, общее число ребер в графе <tex>G</tex>  должно равняться <tex>p-1</tex>.
 +
3) <tex> \to </tex> 4) Предположим, что в графе <tex>G</tex> есть простой цикл длины <tex>n</tex>. Этот цикл содержит <tex>n</tex> вершин и <tex>n</tex> ребер, а для любой из <tex>p - n</tex> вершин, не принадлежащих циклу,существует инцидентное ей ребро, которое лежит на геодезической , идущей от некоторой вершины цикла. Все такие ребра попарно различны; отсюда <tex>q \ge p</tex>, т. е. пришли к противоречию.
 
}}
 
}}
 
'''Следствие:'''
 
 
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.
 
  
 
==Литература==
 
==Литература==
  
 
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6

Версия 00:53, 22 декабря 2010

Определения

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


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


Определение:
Граф, не содержащий циклов, называется лесом.

Теорема

Теорема:
Для графа [math]G[/math] с [math]p[/math] вершинами и [math]q[/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] будет точно один простой цикл.
Доказательство:
[math]\triangleright[/math]

Для примера докажем эквивалентность первых четырёх утверждений.

1) [math] \to [/math] 2) Поскольку [math]G[/math] связный граф, то любые две его вершины соединены простой цепью. Пусть [math]P_1[/math] и [math]P_2[/math] - две различные простые цепи, соединяющие вершины [math]u[/math] и [math]v[/math], и пусть [math]w[/math] - первая вершина, принадлежащая [math]P_1[/math] (при переходе по [math]P_1[/math] из [math]u[/math] в [math]v[/math]), такая, что [math]w[/math] принадлежит и [math]P_1[/math] и [math]P_2[/math], но вершина, предшествующая ей в [math]P_1[/math], не принадлежит [math]P_2[/math].Если [math]w'[/math] - следующая за [math]w[/math] вершина в [math]P_1[/math], принадлежащая также [math]P_2[/math], то сегменты (части) цепей [math]P_1[/math] и [math]P_2[/math], находящиеся между вершинами [math]w[/math] и [math]w'[/math], образуют простой цикл в графе [math]G[/math]. Поэтому если [math]G[/math] - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепь.

2) [math] \to [/math] 3) Ясно, что граф [math]G[/math] - связный. Соотношение [math]p = q + 1[/math] докажем по индукции. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше [math]p[/math] вершин. Если же граф [math]G[/math] имеет [math]p[/math] вершин, то удаление из него любого ребра делает его несвязным, в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, общее число ребер в графе [math]G[/math] должно равняться [math]p-1[/math].

3) [math] \to [/math] 4) Предположим, что в графе [math]G[/math] есть простой цикл длины [math]n[/math]. Этот цикл содержит [math]n[/math] вершин и [math]n[/math] ребер, а для любой из [math]p - n[/math] вершин, не принадлежащих циклу,существует инцидентное ей ребро, которое лежит на геодезической , идущей от некоторой вершины цикла. Все такие ребра попарно различны; отсюда [math]q \ge p[/math], т. е. пришли к противоречию.
[math]\triangleleft[/math]

Литература

  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6