Математика. Графы. Доказательство двух недружественных деревьев.

Свойства деревьев:

Граф G(V,X) является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

4. Граф G(V,X) связен и не содержит циклов.

5. Граф G(V,X) связный , но утрачивает это свойство после удаления любого ребра.

ТЕОРЕМА 1. Дерево с n вершинами имеет n-1 ребер.

Вместо одного дерева рассмотрим теnерь лес, состояшиий из k связных компонент, каждая из которых является деревом (рис. 35). Для каждой из компонент число ребер на единиuу меньше числа вершин. Следовательно, справедлива.

ТЕОРЕМА 2. Лec, состоящий из k компонент и имеющий n вершин, содержит n-k ребер.

Нашу новую задачу мы сформулируем в сельскохозяйственных терминах. На рис. 37 изображена карта полей пекоторой фермы. Предположим, что это карта нескольких рисовых полей, расnоложенных на острове; поля окружены земляными плотинами, которые в свою очередь окружены водами озера. Как обычно nри возделывании риса, мы хотим иметь возможность заливать nоля водой, открывая отверстия в некоторых из стенок. Для того чтобы оросить все поля, необходимо, очевидно, сломать по крайней мере одну стенку в каждом цикле карты, т. е. сделать так, чтобы стенки, оставшиеся несломанными, образовали граф без циклов. Вопрос состоит в том, чтобы выяснить, сколько именно стен nридется сломать

.

Это приводит к следующей общей задаче относительно графов: каково наименьшее число ребер, которые надо удалить из данного связного графа, чтобы на нем не осталось ни одного цикла.(т.е. он стал деревом)

Решение.Пусть дан граф имеющий N ребер.По теореме 1 дерево с n вершинами имеет n-1 ребро. Пусть X - количество ребер, которые надо удалить из данного графа. Тогда,N-X=n-1, X=N-n+1,следовательно, надо удалить N-n+1 ребер, чтобы граф стал деревом.

Проиллюстрируем это превращение графа в дерево на рис.38. Удалим сначала ребро ED, принадлежащее циклу EFD, затем ребро AD, принадлежащее циклу DFA, и, наконец, ребра АС и ВЕ Остается дерево, изображенное на рис. 38. Всего мы удалили X= 9 - 6 + 1 = 4 ребра.