|
|
| Строка 9: |
Строка 9: |
| | * G - ацикличен, и простой цикл формируется при добавлении любого ребра | | * G - ацикличен, и простой цикл формируется при добавлении любого ребра |
| | * G - связен, и удаление любого ребра приводит к потере связности | | * G - связен, и удаление любого ребра приводит к потере связности |
| − | * G - связен, и полный 3-х вершинный граф не является его минором | + | * G - связен, и полный 3-х вершинный граф не является его минором |
| − | | |
| − | Для примера докажем эквивалентность первых четырёх утверждений.
| |
| − | | |
| − | <tex>1 \Rightarrow 2</tex> Поскольку <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> - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепь.
| |
| − | | |
| − | <tex>2 \Rightarrow 3</tex> Ясно, что граф <tex>G</tex> - связный. Соотношение <tex>p = q + 1</tex> докажем по индукции. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает его несвязным, в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, общее число ребер в графе <tex>G</tex> должно равняться <tex>p-1</tex>.
| |
| − | | |
| − | <tex>3 \Rightarrow 4</tex> Предположим, что в графе <tex>G</tex> есть простой цикл длины <tex>n</tex>. Этот цикл содержит <tex>n</tex> вершин и <tex>n</tex> ребер, а для любой из <tex>p - n</tex> вершин, не принадлежащих циклу,существует инцидентное ей ребро, которое лежит на геодезической , идущей от некоторой вершины цикла. Все такие ребра попарно различны; отсюда <tex>q \ge p</tex>, т. е. пришли к противоречию.
| |
| − | | |
| − | <tex>4 \Rightarrow 1</tex> Предположим граф <tex>G</tex> имеет <tex>k</tex> компонент связности, и т. к. граф ациклический, то каждая компонента связности является деревом. Ввиду того, что <tex>1 \Rightarrow 3</tex> <tex>q = \sum \limits_{i = 1}^k (p_i - 1) = p - k</tex>, где <tex>p_i</tex> - количество вершин в <tex>i</tex>-й компоненте связности. Учитывая, что <tex>p = q + 1</tex>, получаем, что <tex>k = 1</tex>, т. е. <tex>G</tex> - дерево.
| |
| − | }}
| |
| | | | |
| | ==Литература== | | ==Литература== |
В теории графов Дерево - неориентированный граф, в котором две любых вершины соединены единственным простым путем. Другими словами, любой связный граф без циклов дерево.
Лес - граф, являющийся набором непересекающихся деревьем.
Определения
Дерево - неориентированный простой граф G, который удовлетворяет любому из эквивалентных утверждений:
- любые две вершины графа G соединены единственным простым путем
- G - связен и ацикличен
- G - ацикличен, и простой цикл формируется при добавлении любого ребра
- G - связен, и удаление любого ребра приводит к потере связности
- G - связен, и полный 3-х вершинный граф не является его минором
Литература
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Википедия — свободная энциклопедия
