33. Дерево. Лес

Граф, не имеющий циклов, называется ациклическим. Связный ациклический граф называется деревом.

Граф, каждая компонента связности которого-дерево, называется лесом.

Теорема. Для графа G=(N,U) следующее свойство эквивалентно:

1.G является деревом

2.Любые 2 вершины графа связаны единственной простой цепью.

3. Граф G ацикличен и число рёбер на единицу меньше числа вершин (l=v-1)

4.Граф G связан и число рёбер на единицу меньше числа вершин.

Схема доказательства. Докажем, что1=>2=>3=>4=>1. Покажем, что из 1=>. Пусть свойство 1 выполняется, а свойство 2 при этом не выполняется. Так как граф связан, то найдётся пара вершин, связанных двумя простыми цепями. А это противоречит определению дерева, потому что граф является ацикличен. Показали, что из 1=>2.

Покажем, что из 2=>3. Предположим, что свойство 2 выполняется. Покажем, что при выполнении свойства 2, граф имеет, по крайней мере, одну висячую вершину. Показывать будем от противного: предположим, что висячих вершин нет. Так как выполняется свойство 2, то граф связан и отсутствие висячих вершин будет обозначать, что степень каждой вершины≥2. Тогда покажем, что в этом графе можно выделить цикл, например, следующим образом:берём произвольную вершину и двигаемся от неё к смежной по ребру i2, от i2 к смежной по ребру i3, и т.д.

Так как степень каждой вершины ≥2, то, войдя в некоторую вершину по ребру, мы можем выйти из неё по другому ребру. Число рёбер в графе-конечно. Поэтому через конечное число шагов некоторая вершина с номером k повторится, а это значит, что в исходном графе найдётся пара вершин (i,j), связанных двумя простыми цепями. А это противоречит свойству 2. Итак, в исходном графе сущ висячая вершина. Удаление этой вершины не нарушает свойство 2. Следовательно, новый граф тоже имеет висячую вершину. Продолжая удаление висячих вершин, мы получим одновершинный граф. Следовательно, число рёбер исходного графа на 1 меньше числа вершин. Удаление висячей вершины не нарушает ацикличность. Одновершинный граф ацикличен, а значит исходный тоже ацикличен. Показали, что из 2=>3.

Покажем, что из 3=>4. Для этого необходимо показать, что при выполнении свойства 3 грая является связным. Так как граф G ацикличен, то каждая компонента его связности является деревом. Пусть граф содержит m-компонент связности, так как каждая из них-число рёбер на 1 меньше от числа вершин, то для исходного графа выполняется l=v-m (l-число рёбер, m-число вершин)

Но так как в нашем случае m=1, l=v-1, а компонента связности 1, то граф G-связный.

Покажем, что 4=>1. Нужно показать, что при выполнении 4-граф-дерево.

Доказательство от противного. Предположим, что граф G-простой цикл длины n, он содержит n-вершин и n-рёбер. Тогда для любой из остальных v-n вершин(не принадлежащих циклу) сущ инциндентное ей ребро, лежащее на геодезической (ломаной) идущей от некоторой вершины цикла. Все такие рёбра попарно различны. Тогда получаем, что e≥v. А это противоречит 4 пункту. Тогда выходит, что граф ациклический, а связный ациклический граф является деревом по определению.

Теорема доказана.