Дискретка / Учебники / diskretka-lekcii
Рис . 3.22. Рис . 3.23. Рис . 3.24. Упражнение 3.15. Представить диаграммами все ( с точностью до изоморфизма ) деревья с шестью вершинами . Деревья обладают рядом характеристических свойств , по наличию или отсутствию каждого их которых в рассматриваемом графе G = ( V , E ) можно определить , является граф деревом или нет . Перечислим эти свойства : 1) граф G — дерево в том и только в том случае , когда в нем нет циклов и E = V −1 ; 2) граф G — дерево в том и только в том случае , когда он связный и E = V −1 ; 3) граф G — дерево в том и только в том случае , когда он связный , и каждое его ребро является мостом ; 4) граф G — дерево в том и только в том случае , когда любые две вершины графа G можно соединить простой цепью , притом единственной ; 5) граф G — дерево в том и только в том случае , когда в нем нет циклов и добавление к нему нового ребра приводит к образованию единственного простого цикла . Также приведем одно из характеристических свойств леса : граф G = ( V , E ) , имеющий k компонент связности , является лесом в том и только в том случае , когда E = V − k . Упражнение 3.16. Представить диаграммами все леса с тремя ребрами и шестью вершинами . 2. Остовы графа. Подграф G % графа G называется остовным подграфом , если множество его вершин совпадает с множеством вершин графа G . Остовом обыкновенного графа называется его остовный подграф , являющийся деревом . Пусть G = ( V , E ) — связный граф . Если G содержит хотя бы один цикл , то удалив из графа G некоторое ребро этого цикла , мы уменьшим число циклов графа по крайней мере на единицу , сохранив при этом его связность . Ясно , что , последовательно разрушая циклы данного графа , можно прийти к остову графа . Поскольку дерево с V вершинами имеет ровно V − 1 ребро , то для получения остова нужно удалить из графа E − ( V −1 ) ребро , т . е . число ребер , равное цикломатическому числу ν( G ) связного графа G .
Пусть теперь G = ( V , E ) — произвольный граф с k компонентами связности . Из каждой компоненты связности G i = ( V i , E i ) этого графа удалим E i − V i + 1 ребро так , чтобы получился остов этой компоненты . В результате получим некоторый остовный подграф графа G . Подсчитаем общее число ребер , которое нам пришлось для этого удалить . Сложив равенства E i − V i + 1 , 1 ≤ i ≤ k , получим :
| k | k | k | ||||||||||||
| å ( | E i | − | V i | + 1 ) = å | E i | − å | V i | + k = | E | − | V | + k = ν( G ) . | ||
| i =1 | i =1 | i =1 | ||||||||||||
Таким образом , чтобы получить остовный подграф , нужно , последовательно разрушая циклы графа , удалить из него число ребер , равное его цикломатическому числу . Пример 3. Построим остов графа G , диаграмма которого изображена на рис . 3.25. Удалим из графа G ребро e 1 ; получим граф G 1 ( рис . 3.26). Из графа G 1 удалим ребро
| e 5 ; получим граф G 2 ( рис . 3.27). Из графа G 2 | удалим ребро e 6 ; получим граф G 3 ( рис . | ||||||||
| 3.28), который является одним из остовов графа G . | |||||||||
| a | e 1 | b | a | b | |||||
| e 4 | e 5 | e | e 4 | e 5 | e | ||||
| e 6 | 2 | e 6 | 2 | ||||||
| d | e 3 | c | d | e 3 | c | ||||
| G | G 1 | ||||||||
| Рис . 3.25. | Рис . 3.26. | ||||||||
| a | b | a | b | ||||
| e 6 | e 4 | e 2 | e 4 | e 2 | |||
| d | e 3 | c | c | ||||
| d | e 3 | ||||||
| G 2 | G 3 | ||||||
| Рис . 3.27. | Рис . 3.28. | ||||||
Упражнение 3.17. Построить остовы графов G 1 , G 2 , G 3 , G 4 , изображенных на рис . 3.6. Пусть G — обыкновенный связный граф . Упорядочим множество его вершин V = < v 1 , v 2 . v n >. Определим матрицу Кирхгофа K ( G ) графа G , положив :
| æ deg v 1 | 0 | K | 0 | ö | |
| ç | 0 | deg v | K | 0 | ÷ |
| K ( G ) = ç | M | 2 | O | M | ÷ — A ( G ) , |
| ç | M | ÷ | |||
| ç | ÷ | ||||
| è | 0 | 0 | K deg v n ø | ||
где A ( G ) — матрица смежности графа , соответствующая данному упорядочению вершин . Справедливы следующие утверждения : 1) алгебраические дополнения всех элементов матрицы Кирхгофа графа равны между собой ; 2) число остовов в связном неодноэлементном обыкновенном графе равно алгебраическому дополнению любого элемента его матрицы Кирхгофа . Доказательство этих утверждений опустим . Пример 4. Найдем число остовов в полном графе K 3 с помеченными вершинами и представим их диаграммами . ◄ Пометим вершины графа K 3 ( рис . 3.29) и выпишем для полученного графа матрицу Кирхгофа :
| æ | 2 | 0 | 0 ö æ | 0 | 1 | 1 ö æ | 2 — 1 | — 1 ö | ||||||
| ç | 0 | 2 | 0 | ÷ | ç | 1 | 0 | 1 | ÷ | ç | — 1 | ÷ | ||
| K ( K 3 ) = ç | ÷ | — ç | ÷ | = ç | 2 — 1 ÷ . | |||||||||
| ç | 0 | 0 | 2 | ÷ | ç | 1 | 1 | 0 | ÷ | ç | — 1 | — 1 | 2 | ÷ |
| è | ø è | ø è | ø | |||||||||||
Найдем алгебраическое дополнение к элементу матрицы K , стоящему на пересечении первой строки и первого столбца ( элемент взят нами произвольно ):
| A | (1,1) | 1+1 | 2 — 1 | = 3 . |
| = ( — 1) | — 1 2 |
Таким образом , число помеченных остовов в полном графе с тремя вершинами равно 3. Их диаграммы изображены на рис . 3.30 — 3.32. ►
| v 2 | v 2 | v 2 | v 2 | |||
| v 3 | v 3 | v 3 | v 3 | |||
| v 1 | v 1 | v 1 | v 1 | |||
| Рис . 3.29. | Рис . 3.30. | Рис . 3.31. | Рис . 3.32. | |||
Упражнение 3.18. Найти число остовов , а также сами остовы в помеченном графе K 2,2 .
3. Построение минимального остова. Взвешенным графом называется граф , на множестве ребер которого задано отображение ρ : E →[0; +∞) , приписывающее каждому ребру e неотрицательное число ρ ( e ) . Число ρ ( e ) называется весом ребра e , число ρ ( G ) = å ρ( e ) — весом графа G . e E Остов T связного взвешенного графа G называют минимальным остовом , если для любого остова T % выполнено неравенство ρ ( T ) ≤ ρ ( T % ) . Опишем алгоритм построения минимального остова в связном взвешенном графе , предложенный Дж . Краскалом в 1956 г .
| Пусть G — связный взвешенный граф . | |
| 0- й шаг . Строим остовный подграф T 0 графа G , множество E 0 | ребер которого пусто . |
| k — й шаг . Пусть T k −1 — остовный подграф с множеством ребер E k −1 = < e 1 , e 2 . e k −1 >, | |
| построенный к началу этого шага . Из множества ребер E \ E k −1 | выбираем ребро e k так , |
| чтобы выполнялись два условия : | |
а ) добавление ребра e k не приводит к образованию циклов ; б ) из ребер , удовлетворяющих условию а ), ребро e k обладает наименьшим весом . Если такого ребра нет , то T k −1 — остов минимального веса ; если есть , то , добавляя выбранное ребро e k к остовному подграфу T k −1 , получаем остовный подграф T k с множеством ребер E k = E k −1 < e k >. После чего повторяем k — й шаг . Замечания. 1. В случае несвязного графа , следуя алгоритму Краскала , можно построить остовный лес минимального веса . 2. Если граф невзвешенный , то , присвоив всем ребрам одинаковые веса , по алгоритму Краскала можно построить остов ( остовный лес ). Пример 5. Построить остов минимального веса графа G , представленного диаграммой на рис . 3.33 ( на диаграмме около каждого ребра проставлен его вес ). ◄ Согласно алгоритму Краскала , строим последовательность остовных подграфов :
| e 3 | e 8 | T 0 | с пустым множеством ребер ( рис . 3.34); | ||||||||||||||||||
| e 1 | 1 | ||||||||||||||||||||
| 8 | T 1 | с множеством ребер < e 8 >( рис . 3.35); | |||||||||||||||||||
| 2 | e | e 5 7 e 7 | 3 | ||||||||||||||||||
| 6 | 4 | 4 | 2 | T 2 | с множеством ребер | ( рис . 3.36); | |||||||||||||||
| e 2 | e 6 | ||||||||||||||||||||
| Рис . 3.33. | T 3 | с множеством ребер < e 8 , e 1 , e 6 >( рис . 3.37); | |||||||||||||||||||
| T 4 | смножеством ребер < e 8 , e 1 , e 6 , e 7 >( рис . 3.38); | ||||||||||||||||||||
| T 5 | с множеством ребер | ||||||||||||||||||||
| ( рис . 3.39). | |||||||||||||||||||||
| Добавление к графу T 5 | любого из оставшихся ребер графа G ведет к образованию | ||||||||||||||||||||
| цикла . Таким образом , остовный подграф T 5 c множеством ребер | — | ||||||||||||||||||||
| минимальный остов ; его вес равен ρ( T 5 ) = 1+ 3 + 2 + 4 + 6 = 16 . ► | |||||||||||||||||||||
| e 3 | e 8 | e 3 | e 8 | e 8 | |||||||||||||||||
| e 1 | 1 | e 1 | 1 | e 1 | e 3 | 1 | |||||||||||||||
| 8 | 8 | 8 | |||||||||||||||||||
| 2 e | e 5 7 e 7 3 | 2 e | e 5 7 e 7 3 | 2 e | e 5 7 e 7 3 | ||||||||||||||||
| 6 | 4 | 4 | 2 | 6 | 4 | 4 | 2 | 6 | 4 | 4 | 2 | ||||||||||
| e 2 | e 6 | e 2 | e 6 | e 2 | e 6 | ||||||||||||||||
| Рис . 3.34. | Рис . 3.35. | Рис . 3.36. | |||||||||||||||||||
| e 8 | e 8 | e 8 | |||||||||||||||||||
| e 1 | e 3 | 1 | e 1 | e 3 | 1 | e 1 | e 3 | 1 | |||||||||||||
| 8 | 8 | 8 | |||||||||||||||||||
| 2 e | e 5 7 e 7 3 | 2 e | e 5 7 e 7 | 3 | 2 e | e 5 7 e 7 | 3 | ||||||||||||||
| 6 | 4 | 4 | 2 | 6 | 4 | 4 | 2 | 6 | 4 | 4 | 2 | ||||||||||
| e 2 | e 6 | e 2 | e 6 | e 2 | e 6 | ||||||||||||||||
| Рис . 3.37. | Рис . 3.38. | Рис . 3.39. | |||||||||||||||||||
Упражнение 3.19. Дан граф G с вершинами v 1 , v 2 . v 6 , ребрами e 1 = v 1 v 6 , e 2 = v 1 v 3 , e 3 = v 2 v 3 , e 4 = v 1 v 2 , e 5 = v 2 v 4 , e 6 = v 2 v 6 , e 7 = v 4 v 6 , e 8 = v 4 v 6 , e 9 = v 4 v 5 , e 10 = v 3 v 4 , e 11 = v 3 v 5 и весовым отображением ρ : ρ( e 1 ) = 1 , ρ( e 2 ) =1 , ρ( e 3 ) = 1 , ρ( e 4 ) = 3 , ρ( e 5 ) = 2 , ρ( e 6 ) = 2 , ρ( e 7 ) = 2 , ρ( e 8 ) = 1 , ρ( e 9 ) = 3 , ρ( e 10 ) = 2 , ρ( e 11 ) = 1 . Построить минимальный остов графа G и вычислить его вес . 4. Кодирование деревьев. Выделим в дереве какую — нибудь одну вершину , которую назовем корнем . Полученное дерево с выделенной вершиной называется корневым . Для задания ( с точностью до изоморфизма ) корневых деревьев используют бинарный код ( из 0 и 1), который мы определим индуктивно . PDF created with pdfFactory Pro trial version www.pdffactory.com
Определение. Бинарным кодом корневого дерева с одним ребром является
| последовательность ( 01 ) . Пусть деревья T 1 и T 2 | с корнями a и b соответственно ( рис . | |||||||||||||
| 3.40) имеют коды α % | % | с корнем с является код ( 0α % 1 ) , а кодом | ||||||||||||
| и β . Тогда кодом дерева T 3 | ||||||||||||||
| дерева T 4 с корнем | % | ) . | ||||||||||||
| c = a = b — код ( αβ % | ||||||||||||||
| T 1 | ||||||||||||||
| a | a | T 1 | T 2 | |||||||||||
| b | c=a=b | |||||||||||||
| c | ||||||||||||||
| T 1 | T 2 | T 3 | T 4 | |||||||||||
| Рис . 3.40. | ||||||||||||||
Пример 6. Построить бинарный код дерева , изображенного на рис . 3.41.
| (001011) | |||
| (01) | (01) | (01) | (01) |
| (01) | |||
| (010101) | (01) | ||
| (0101) | |||
| (00101011) | |||
| (01001011) | |||
| (0010010111) | |||
Рис . 3.41. ◄ Этапы построения кода отражены на рис . 3.41. Код дерева — ( 00010101100100101111 ) . ► Упражнение 3.20. Построить бинарный код дерева , изображенного на рис . 3.42. Справедливо следующее утверждение : для того чтобы последовательность нулей и единиц являлась кодом некоторого дерева , необходимо и достаточно , чтобы число нулей и единиц в последовательности было одинаковым , причем в любом начальном отрезке последовательности количество нулей было не меньше количества единиц .
| 7 | 1 | 3 |
| 2 | ||
| 5 | 4 | |
| 8 | 6 | |
| Корень дерева | 9 |
| Корень дерева |
Рис . 3.42. Рис . 3.43. Например , последовательность ( 0011101001 ) не может быть бинарным кодом дерева , поскольку в отрезке 00111 из пяти первых цифр этой последовательности единиц больше , чем нулей . Чтобы построить корневое дерево по коду из нулей и единиц , нужно разбить последовательность на пары 0 и 1, следуя правилу : первая попавшаяся в коде единица образует пару с предшествующим нулем ; каждая следующая единица образует пару с ближайшим слева неиспользованным нулем . Если образованные таким образом пары пометить снизу кода фигурными скобками , то каждая такая скобка будет соответствовать ребру графа . Пример 7. Построить дерево по коду ( 010010010111010011 ) . ◄Разобьем элементы последовательности на пары : 010010010111010011 < < < < < < и построим 1 2 1424 3 3 7 < 8 14244 5 3 9 6 дерево ( рис . 3.43). ► Упражнение 3.21. Построить дерево по коду ( 001000111011 ) . Для задания деревьев c занумерованными вершинами используют код из натуральных чисел ( код Прюфера ) . Код Прюфера для дерева с занумерованными вершинам строят следующим образом . Находят висячую вершину с наименьшим номером . Записывают номер смежной с ней вершины ( это начало кода ), после чего удаляют эту висячую вершину вместе с инцидентным ей ребром . Для полученного в результате данной операции дерева находят висячую вершину с наименьшим номером , записывают номер смежной с ней вершины ( это продолжение кода ), после чего удаляют эту висячую вершину вместе с инцидентным ей ребром . Так поступают до тех пор , пока не останется последнее ребро ( его вершины в код не включают ). Полученная в результате описанных действий PDF created with pdfFactory Pro trial version www.pdffactory.com
Источник