Дискретка / Учебники / Лекции Олейник / Р_3_3
Упр а жн е н ие 3 . 1 5 . Представить диаграммами все (с точностью до изоморфизма) деревья с шестью вершинами. Деревья обладают рядом характеристических свойств , по наличию или отсутствию каждого их которых в рассматриваемом графе 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 . 1 6 . Представить диаграммами все леса с тремя ребрами и шестью вершинами. 2. Остовы графа. Подграф G графа G называется о сто вн ым п о дгр а фо м , если множество его вершин совпадает с множеством вершин графа G . Остовом обыкновенного графа называется его остовный подграф, являющийся деревом. Пусть G V , E — связный граф. Если G содержит хотя бы один цикл, то удалив из графа G некоторое ребро этого цикла, мы уменьшим число циклов графа по крайней мере на единицу, сохранив при этом его связность. Ясно, что, последовательно разрушая циклы данного графа, можно прийти к остову графа. Поскольку дерево с V вершинами 140
имеет ровно V 1 ребро, то для получения остова нужно удалить из
| E | V | 1 ребро, т.е. число ребер, | ||||||||||||||||
| графа | равное цикломатическому | |||||||||||||||||
| числу ( G ) связного графа G . | ||||||||||||||||||
| Пусть теперь G V , E | — произвольный граф с k компонентами | |||||||||||||||||
| связности. Из каждой компоненты связности G i V i , E i | этого графа | |||||||||||||||||
| удалим | E i | V i | 1 ребро | так, чтобы | получился | остов этой | ||||||||||||
компоненты. В результате получим некоторый остовный подграф графа G . Подсчитаем общее число ребер, которое нам пришлось для этого
| V i | 1 , 1 i k , получим: | ||||||||||||
| удалить. Сложив равенства | E i | ||||||||||||
| 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 | ||
| e 3 | c | e 3 | c | ||
| d | d |
| G | G 1 |
| Рис. 3.25. | Рис. 3.26. |
141
| a | b | a | b |
| e 4 | e 2 | e 4 | e |
| e 6 | 2 | ||
| e | c | ||
| d | e 3 c | ||
| 3 | d | ||
| G 2 | G 3 |
| Рис. 3.27. | Рис. 3.28. |
Упр а жн е н ие 3 . 1 7 . Построить остовы графов 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 | 0 | |
| 0 | deg v 2 | 0 | |
| K G | A G , | ||
| 0 | 0 | deg v n | |
где A G — матрица смежности графа, соответствующая данному упорядочению вершин. Справедливы следующие утверждения: 1) алгебраические дополнения всех элементов матрицы Кирхгофа графа равны между собой; 2) число остовов в связном неодноэлементном обыкновенном графе равно алгебраическому дополнению любого элемента его матрицы Кирхгофа. Доказательство этих утверждений опустим. Пр и м ер 4 . Найдем число остовов в полном графе K 3 с помеченными вершинами и представим их диаграммами. ◄ Пометим вершины графа K 3 (рис. 3.29) и выпишем для полученного графа матрицу Кирхгофа: 142
| 2 | 0 | 0 | 0 | 1 | 1 | 2 | 1 | 1 | ||||||
| K ( K 3 ) | 0 | 2 | 0 | 1 | 0 | 1 | 1 | 2 1 . | ||||||
| 0 | 0 | 2 | 1 | 1 | 0 | 1 | 1 | 2 | ||||||
Найдем алгебраическое дополнение к элементу матрицы K , стоящему на пересечении первой строки и первого столбца (элемент взят нами произвольно):
| 1 | |||
| (1,1) | 1 1 | 2 | 3 . |
| A | ( 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 . 1 8 . Найти число остовов, а также сами остовы в помеченном графе K 2,2 . 3. Построение минимального остова. Взвешенным графом называется граф, на множестве ребер которого задано отображение : E [0; ) , приписывающее каждому ребру e неотрицательное число e .
| Число | e | называется весом ребра e , | число G ( e ) — |
| e E | |||
| весом графа G . | |||
| Остов T связного взвешенного графа G называют минимальным | |||
| остовом , | если | для любого остова T | выполнено неравенство |
| T T . | |||
Опишем алгоритм построения минимального остова в связном взвешенном графе, предложенный Дж. Краскалом в 1956 г. Пусть G — связный взвешенный граф. 143
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 | T 0 | с пустым множеством ребер (рис. 3.34); | |||||
| e 3 | 8 | с множеством ребер e 8 (рис. 3.35); | |||||
| e 1 | 1 | T 1 | |||||
| 8 | T 2 | с множеством ребер e 8 , e 1 (рис. 3.36); | |||||
| 2 e | e 5 7 e 7 | 3 | |||||
| 6 4 | 4 | T 3 | с множеством ребер e 8 , e 1 , e 6 (рис. 3.37); | ||||
| 2 | |||||||
| e 2 | e 6 | T 4 | смножеством ребер< e 8 , e 1 , e 6 , e 7 >(рис. 3.38); | ||||
| Рис. 3.33. | T 5 | с | множеством ребер e 8 , e 1 , e 6 , e 7 , e 4 | ||||
| (рис. 3.39). | |||||||
| Добавление к графу | T 5 | любого из оставшихся ребер графа G | |||||
ведет к образованию цикла. Таким образом, остовный подграф T 5 c 144
множеством ребер e 8 , e 1 , e 6 , e 7 , e 4 — минимальный остов; его вес равен ( T 5 ) 1 3 2 4 6 16 . ►
| e 3 | e 8 | e 3 | e 3 | ||||||||||||||
| e 1 | 1 | e 1 | |||||||||||||||
| 8 | 8 | 8 | |||||||||||||||
| 2 e | e 5 | 7 e 7 3 | 2 e | e 5 7 e 7 3 | e 5 7 e 7 3 | ||||||||||||
| 6 | 4 | 4 | 6 | 4 | 4 | 2 | 6 | 4 | 2 | ||||||||
| 2 | |||||||||||||||||
| e 2 | e 6 | e 2 | e 6 | e 2 | e 6 | ||||||||||||
| Рис. 3.34. | Рис. 3.35. | Рис. 3.36. | |||||||||||||||
| e 3 | e 3 | e 3 | |||||||||||||||
| 8 | 8 | 8 | |||||||||||||||
| e 5 | 7 e 7 3 | 4 | e 5 7 e 7 | 3 | 4 | e 5 7 e 7 | 3 | ||||||||||
| 6 | 4 | 6 | 6 | ||||||||||||||
| e 2 | e 2 | e 2 | |||||||||||||||
| Рис. 3.37. | Рис. 3.38. | Рис. 3.39. | |||||||||||||||
| Упр а жн е н ие 3 . 1 9 . | Дан | граф 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), который мы определим индуктивно. Определение. Бинарным к одом корневого дерева с одним ребром является последовательность 01 . Пусть деревья T 1 и T 2 с корнями a и b соответственно (рис. 3.40) имеют коды и . Тогда кодом дерева 145
| T 3 с корнем | с | является код | 0 1 , а | кодом | дерева 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 . 2 0 . Построить бинарный код дерева, изображенного на рис. 3.42. Справедливо следующее утверждение: для того чтобы последовательность нулей и единиц являлась кодом некоторого дерева, необходимо и достаточно, чтобы число нулей и единиц в последовательности было одинаковым, причем в любом начальном отрезке последовательности количество нулей было не меньше количества единиц . 146
| 1 | 3 | |||||||
| 7 | 2 | |||||||
| 5 | 4 | |||||||
| 8 | 6 | |||||||
| 9 | ||||||||
| корень дерева | корень дерева | |||||||
| Рис. 3.42. | Рис. 3.43. | |||||||
| Например, последовательность | 0011101001 не | может быть | ||||||
бинарным кодом дерева, поскольку в отрезке 00111 из пяти первых цифр этой последовательности единиц больше, чем нулей. Чтобы построить корневое дерево по коду из нулей и единиц , нужно разбить последовательность на пары 0 и 1, следуя правилу: первая попавшаяся в коде единица образует пару с предшествующим нулем; каждая следующая единица образует пару с ближайшим слева неиспользованным нулем. Если образованные таким образом пары пометить снизу кода фигурными скобками, то каждая такая скобка будет соответствовать ребру графа.
| Пр и м ер 7 . Построить дерево по коду 010010010111010011 . | |||||||
| ◄Разобьем | элементы | последовательности | на | пары: | |||
| 010 010 010111010 011 и построим дерево (рис. 3.43).► | |||||||
| 1 | 2 | 3 | 4 | 7 | 8 | ||
| 5 | 9 | ||||||
6 Упр а жн е н ие 3 . 2 1 . Построить дерево по коду 001000111011 . Для задания деревьев c занумерованными вершинами используют код из натуральных чисел (код Прюфера). Код Прюфера для дерева с занумерованными вершинам строят следующим образом. Находят висячую вершину с наименьшим номером. Записывают номер смежной с ней вершины (это начало кода), после чего удаляют эту висячую вершину вместе с инцидентным ей ребром. Для полученного в результате данной операции дерева находят висячую вершину с наименьшим номером, записывают номер смежной с ней вершины (это продолжение кода), после чего удаляют эту 147
висячую вершину вместе с инцидентным ей ребром. Так поступают до тех пор, пока не останется последнее ребро (его вершины в код не включают). Полученная в результате описанных действий последовательность и есть код Прюфера. Заметим, что длина этого кода на единицу меньше числа ребер и на две единицы меньше числа вершин дерева. Пр и м ер 8 . Построить код Прюфера для дерева, изображенного на рис. 3.44.
| ◄ | Применим | описанный | |||||
| 3 | 7 | выше алгоритм: | |||||
| 5 | 1 — й ша г . У исходного дерева | ||||||
| 1 | (см. рис. 3.44) висячая вершина с | ||||||
| наименьшим | номером | — это | 1. | ||||
| 6 | |||||||
| 2 | Записываем | смежную | с | ней | |||
| 4 | 8 вершину | 2 в | начало | кода — | 2. | ||
| Удаляем ребро с концами 1, 2 и | |||||||
| Рис. 3.44. | получаем дерево, изображенное на | ||||||
рис. 3.45, а . 2 — й ша г . У дерева на рис. 3.45, а висячая вершина с наименьшим номером — это 3. Записываем смежную с ней вершину 2 в конец строящегося кода — 22. Удаляем ребро с концами 3, 2 и получаем дерево, изображенное на рис. 3.45, б . 3 — й ша г . У дерева на рис. 3.45, б висячая вершина с наименьшим номером — это 2. Записываем смежную с ней вершину 4 в конец строящегося кода — 224. Удаляем ребро с концами 2, 4 и получаем дерево, изображенное на рис. 3.45, в . 4 — й ша г . У дерева на рис. 3.45, в висячая вершина с наименьшим номером — это 5. Записываем смежную с ней вершину 4 в конец строящегося кода — 2244. Удаляем ребро с концами 5, 4 и получаем дерево, изображенное на рис. 3.45, г . 5 — й ша г . У дерева на рис. 3.45, г висячая вершина с наименьшим номером — это 4. Записываем смежную с ней вершину 6 в конец строящегося кода — 22446. Удаляем ребро с концами 4, 6 и получаем дерево, изображенное на рис. 3.45, д . 6 — й ша г . У дерева на рис. 3.45, д висячая вершина с наименьшим номером — это 7. Записываем смежную с ней вершину 6 в конец строящегося кода — 224466. Удаляем ребро с концами 6, 7 и получаем дерево, изображенное на рис. 3.45, е . 148
Источник