Связность графов

курсовая работа

§8. Элементарные свойства деревьев

Лесом называется граф, не содержащий циклов; связный лес называется деревом. Например, на Рис. 1 изображен лес, состоящий из четырех компонент, каждая из которых является деревом. Заметим, что по определению деревья и леса являются простыми графами.

Рис.1

По многим показателям дерево представляет собой простейший нетривиальный тип графа. Как будет показано в теореме 9А, оно обладает некоторыми «приятными» свойствами; например, любые две его вершины соединены единственной простой цепью. Пытаясь доказать какой-нибудь общий результат или проверить гипотезу для графов, удобно бывает начать с деревьев, хотя и существует несколько гипотез, которые еще не доказаны для произвольных графов, несмотря на то, что они верны для деревьев.

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

Теорема 9А. Пусть граф Т имеет n вершин. Тогда следующие утверждения эквивалентны: (i) Т является деревом, (ii) Т не содержит циклов и имеет n -- 1 ребер; (iii) Т связен и имеет n -- 1 ребер; (iv) Т связен и каждое его ребро является мостом; (v) любые две вершины графа Т соединены ровно одной простой цепъю; (vi) Т не содержит циклов, но, добавляя к нему любое новое ребро, получим ровно один цикл.

Доказательство. Если n = 1, утверждение очевидно. Предположим поэтому, что n? 2.

(i) => (ii). По определению Т не содержит циклов,удаление любого ребра разбивает Т на два графа, каждый из которых является деревом. По индуктивному предположению число ребер в каждом из этих деревьев на единицу меньше числа вершин. Отсюда выводим, что полное число ребер графа Т равно n -- 1.

(ii) => (iii). Если граф Т несвязен, то каждая его компонента представляет собой связный граф без циклов. Из предыдущей части доказательства следует, что число вершин в каждой из компонент больше числа ее ребер на единицу. Значит, полное число вершин графа Т больше полного числа его ребер по крайней мере на 2, а это противоречит тому, что Т имеет n -- 1 ребер.

Делись добром ;)