основы теории графов. Основы теории графов - I. Основы теории графов I
 Скачать 342.84 Kb.
|
|
Основы теории графов - I 1 Основные понятия теории графов 1.1. Начнем данный параграф с определения неориентированных и ориентированных графов. 1.1.1. Формальное и достаточно общее определение неориентированного графа таково. Определение 1.1. Неориентированным графом G называется тройка G = (V, E, I), состоящая из (1) (конечного) множества вершин V = V (G), например, V = {1, 2, 3, 4}, (2) (конечного) множества ребер E = E(G), например, E = {a, b, c, d, e, f, g, h}, (3) а также отображения I : E → V 2 , сопоставляющего любому ребру e ∈ E неупорядоченную пару вершин {x, y} ∈ V 2 , которую это ребро соединяет. Вершины x и y называются концевыми вершинами ребра e. При этом говорят, что ребро e инцидентно своим концевым вершинам. В принципе, возможен случай x = y. Ребро e ∈ E, соответствующее паре {x, x}, называется обычно петлей. Кроме того, в общем случае у нас могут быть несколько различных ребер, соединяющих одну и ту же пару вершин {x, y}. Такие ребра называют кратными ребрами и говорят, что они образуют мультиребро графа G. Если пара вершин {x, y} соединена между собой единственным ребром, то такое ребро иногда называют простым ребром графа. Пример 1.2. Зададим отображение I в виде следующей таблицы: E a b c d e f g h V 2 {1, 3} {2, 4} {1, 3} {3, 4} {3, 4} {1, 2} {3, 4} {2, 2} Ей соответствует граф G, изображенный на рис.1. В этом графе ребра f и b являются простыми, ребра a и c образуют мультиребро, соединяющее вершины 1 и 3, а ребро h представляет собой петлю. 1.1.2. С понятием инцидентности тесно связано важное понятие степени вершины графа G. Определение 1.3. В неориентированном графе G степенью deg(x) или валентностью вер- шины x называется количество ребер, инцидентных x. Считается, что петля дает вклад, равный двум, в степень любой вершины. Вершина, степень которой равна нулю, называется изолирован- ной. Если все вершины в графе G имеют одинаковую степень, то граф G называют регулярным. 1 2 3 4 h a c b f d e g Рис. 1: Пример графа на четырех вершинах Так, вершина 1 на рис.1 имеет степень, равную трем, а вершина 2 — степень, равную четырем. Следующее утверждение часто называют первой теоремой теории графов. Теорема 1.4. В неориентированном графе G сумма степеней всех вершин равна удвоенному количеству всех ребер графа: X x∈V (G) deg(x) = 2|E(G)|. (1) Доказательство практически очевидно — любое ребро дает вклад, равный двум, в стоящую слева сумму. Следствие 1.5. Количество вершин в графе G, имеющих нечетную степень, четно. 1.1.3. Чаще всего на практике встречаются так называемые простые графы. Определение 1.6. Граф G называется простым, если он не содержит петель и мультиребер. Граф, не являющийся простым, часто называют мультиграфом. 1 2 3 4 Рис. 2: Пример простого графа на четырех вершинах В качестве примера рассмотрим изображенный на рис. 2 простой граф G, построенный на четырех вершинах и имеющий два ребра. Видно, что в таком графе мы можем не вводить какое- то дополнительное специальное обозначение для ребер — любое ребро однозначно задается парой вершин, которые оно соединяет. Как следствие, для описания простого графа G нам достаточно задать множество V его вершин, а также множество E его ребер в виде некоторого подмножества множества всевозможных неупорядоченных пар множества вершин. Так, для графа G на рис. 2 мы имеем V = {1, 2, 3, 4}, E = {{1, 2}, {1, 4}} . Итак, с формальной точки зрения любой простой неориентированный граф G, построенный на n вершинах, можно рассматривать как некоторое подмножество множества V (2) всех двухэле- ментных подмножеств множества V (G) его вершин: G ⊆ V (2) Если же говорить менее формально, то простой граф — это граф, построенный на n вершинах, любая пара которых может быть соединена или не соединена ребром. 1 2 3 4 Рис. 3: Пример полного графа на четырех вершинах Разберем некоторые важные примеры простых графов. В качестве первого примера рассмот- рим так называемый полный граф K n (рис. 3), в котором любая вершина соединена со всеми оставшимися вершинами графа. Такой граф отвечает всему множеству V (2) двухэлементных подмножеств множества n вершин. Пустому подмножеству множества V (2) отвечает так назы- ваемый пустой граф, то есть граф, состоящий из n изолированных вершин (рис. 4). 1 2 3 4 Рис. 4: Пример пустого графа на четырех вершинах Пустой граф является дополнением к полному графу K n (и обозначается он как ¯ K n ) в смысле следующего определения. 1 2 3 4 (a) G 1 2 3 4 (b) ¯ G Рис. 5 Определение 1.7. Граф ¯ G называется дополнением к графу G, если множества вершин этих двух графов совпадают, а множество ребер графа ¯ G дополняет множество ребер E(G) исходного графа G до полного графа K n На рис. 5 в качестве примера приведены два графа, построенные на четырех вершинах — граф G и граф ¯ G. Граф ¯ G из графа G можно получить, например, так: взять полный граф K 4 , построенный на том же количестве вершин, что и графы G и ¯ G, и удалить из него ребра, принадлежащие графу G. Полученный в результате этой операции граф ¯ G и будет являться дополнением к графу G в смысле данного выше определения. 1.2. Наряду с неориентированными, в теории графов также изучаются и так называемые ори- ентированные графы (или орграфы). 1.2.1. Начнем с мы вновь с достаточно формального и общего определения ориентированного мультиграфа D. Определение 1.8. Если в тройке D = (V, E, I), в которой V есть множество вершин, а E — множество ребер, отображение I ставит в соответ- ствие любому ребру e упорядоченную пару вершин (x, y) ∈ V × V , то такая тройка называется ориентированным графом (или орграфом). В таком случае говорят, что ребро e выходит из вершины x и входит в вершину y. На рисунке такое ребро помечается стрелкой, указывающей направление данного ребра. 1 2 3 a b c Рис. 6: Пример ориентированного графа В качестве примера на рис. 6 показан ориентированный граф D, построенный на множестве вершин V = {1, 2, 3} и имеющий три ребра. Ребро a выходит из вершины 1 и входит в вершину 2 (то есть отвечает упорядоченной паре (1, 2)), а ребра b и c исходят из вершины 2 и приходят в вершину 3 (то есть им соответствует упорядоченная пара (2, 3) вершин графа D). Таким образом, орграф D на рис. 6 задается тройкой (V, E, I), в которой множество V вершин и множество E ребер имеют вид V = {1, 2, 3}, E = {a, b, c}, а отображение I : E → V × V задается таблицей вида E a b c V × V (1, 2) (2, 3) (2, 3) 1.2.2. В орграфе различают исходящую (outdeg(x)) и входящую (indeg(x)) степень любой вер- шины x ∈ V (D), а также просто степень, равную сумме входящей и исходящей степеней. Так, в графе, изображенном на рис. 6, вершина 2 имеет входящую степень, равную единице, и ис- ходящую степень, равную двойке. 1.2.3. Как и для неориентированного графа, важным частным случаем орграфа является про- стой орграф. Определение 1.9. Орграф D называется простым, если он не содержит петель, а также ребер с одинаковыми упорядоченными парами вершин. 1 2 3 a b c Рис. 7: Пример простого ориентированного графа Упорядоченность вершин в этом определении важна. Так, граф из рис. 6 простым не является — в нем ребра b и c отвечают одной и той же упорядоченной паре (2, 3) вершин. Изображенный же на рис. 7 граф D 0 является простым. Несмотря на то, что в этом графе по-прежнему имеются два ребра, соединяющих вершины 2 и 3, направлены эти ребра в разные стороны. Иными словами, эти ребра отвечают различным упорядоченным парам вершин — ребро b отвечает упорядоченной паре (2, 3), а ребро c — упорядоченной паре (3, 2). 1.3. Следующим важным понятием в теории графов является понятие смежности вершин. 1.3.1. Начнем с определения смежных вершин в неориентированном графе G. Определение 1.10. Говорят, что в неориентированном графе G вершина y смежна с вершиной x, если в этом графе существует ребро {x, y}. На множестве вершин V смежность задает некоторое отношение. Для неориентированного гра- фа G это отношение является симметричным: если вершина x смежна с вершиной y, то и вершина y смежна с вершиной x. 1.3.2. Для орентированного графа ситуация несколько сложнее. Определение 1.11. Говорят, что в ориентированном графе D вершина y смежна с вершиной x, если в этом графе существует ребро (x, y), исходящее из вершины x и входящее в вершину y (см.рис. 8,a). x y (a) x y (b) Рис. 8 Сразу заметим, что если существует ребро (x, y) и не существует ребро (y, x), то вершина y смежна с вершиной x, а вот x вершиной, смежной с y, уже не является. Вершина x будет смеж- ной с y только в случае, когда в орграфе D существует ребро (y, x) (рис. 8,b). Иными словами, в ориентированном графе D отношение смежности на множестве V вершин симметричным не является. 1.4. Для хранения графа в памяти компьютера как правило используются две структуры, тесно связанные с понятием смежности — матрица смежности и список смежности. 1.4.1. Матрица смежности — это матрица M a размерами n × n, любой элемент a ij которой описывает количество ребер, идущих из вершины i в вершину j. Так, для примера 1.2 соответ- ствующая графу G матрица смежности имеет следующий вид: M a = 0 1 2 0 1 1 0 1 2 0 0 3 0 1 3 0 Для ориентированного графа D, показанного на рис. 6, матрица смежности равна M a = 0 1 0 0 0 2 0 0 0 Заметим, что для неориентированного графа матрица смежности всегда симметрична. В случае простого графа или орграфа все диагональные элементы a ii = 0, а элементы, не лежащие на диагонали, равны единице в случае, если существует ребро, идущее из вершины i в вершину j, и нулю в случае, если такового ребра не существует. 1.4.2. Список смежности — это линейный массив L a размера n, каждый элемент a i которого содержит список (мультимножество) вершин, смежных с вершиной i. Для примера 1.2 соответ- ствующий список имеет следующий вид: 1 : смежными с вершиной 1 являются вершины 2, 3, 3; 2 : смежными с вершиной 2 являются вершины 1, 2, 4; 3 : смежными с вершиной 3 являются вершины 1, 1, 4, 4, 4; 4 : смежными с вершиной 4 являются вершины 2, 3, 3, 3. Для ориентированного графа, показанного на рис. 6, список смежности записывается так: 1 : смежными с вершиной 1 являются вершины 2 2 : смежными с вершиной 2 являются вершины 3, 3 3 : смежными с вершиной 3 являются вершины − 1.5. Давайте теперь поймем, сколько же существует различных графов, построенных на n вершинах. 1.5.1. Сразу заметим, что в случае мультиграфов мы наряду с количеством вершин должны также фиксировать и количество ребер. Действительно, любые две вершины мультиграфа со- единить произвольным количеством ребер, поэтому количество мультиграфов, построенных на n вершинах, без ограничения на количество ребер может быть сколь угодно большим. Поэтому мы ограничимся пока что задачей подсчета простых графов. 1.5.2. Количество g n простых неориентированных графов достаточно легко сосчитать, исполь- зуя формальное определение простого графа как некоторого подмножества множества V (2) Действительно, количество всех двухэлементных подмножеств n-элементного множества вер- шин (то есть мощность множества V (2) ) равно |V (2) | = n 2 . Нас же интересует множество Σ всех подмножеств V (2) . Количество элементов в этом множестве, как известно, равно |Σ| = 2 |V (2) | = 2( n 2 ). Следовательно, количество g n всех простых графов на n вершинах равняется 2( n 2 ). 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 Рис. 9: Восемь простых графах на трех вершинах Например, существует ровно g 3 = 2( 3 2 ) = 2 3 = 8 различных простых графов, построенных на трех вершинах (смотри рис.9). 1.5.3. Столь же просто подсчитать количество различных простых орграфов. Действительно, всего существует n(n − 1) упорядоченных пар отличных друг от друга вершин. Как следствие, количество различных простых орграфов, построенных на n вершинах, равно 2 n(n−1) 1.6. Вернемся к основным определениям теории графов и введем очень важное понятие подгра- фа графа G. Заодно мы введем две очень важные операции над графами — операцию удаления ребра и операцию удаления вершины в графе G. 1.6.1. Начнем с формального определения подграфа H графа G. Определение 1.12. Подграфом графа G называется граф H, для которого выполнены следу- ющие три условия: 1. V (H) ⊂ V (G); 2. E(H) ⊂ E(G); 3. любое ребро e ∈ E(H), соединяющее пару вершин x и y в H, должно соединять ту же самую пару вершин в графе G. 1.6.2. В качестве примера рассмотрим графы G и H, изображенные на рис.10,a,b. Утверждает- ся, что граф H является подграфом графа G. Действительно, множество вершин графа H есть подмножество вершин графа G, множество ребер E(H) есть подмножество множества E(G). Теперь, выберем любое ребро графа H — например, ребро c, соединяющее вершины 2 и 6 графа H. Это же самое ребро соединяет те же самые вершины 2 и 6 в графе G. И это верно для всех ребер e ∈ E(H). Следовательно, граф H действительно является подграфом графа G. 1.6.3. Данное выше определение можно сделать несколько более конструктивным, если ввести две основные операции над графами — операцию удаления ребра и операцию удаления верши- ны. Оказывается, любой подграф H графа G — это граф, полученный из исходного графа G с помощью этих двух операций. Начнем с более простой операции удаления ребра e. При такой операции множество вершин графа G не меняется, а из множества ребер удаляется элемент e ∈ E(G). Полученный в ре- зультате этой операции граф обозначается G\e. Очевидно, что он является подграфом графа G. В приведенном выше примере мы в графе G удалили, например, ребра a, d и e. Перейдем теперь к чуть более сложной операции удаления вершины. Предположим, что мы хотим удалить в графе G вершину x. Если эта вершина является изолированной, то нам ничего больше делать не нужно. Если же этой вершине инцидентны какие-то ребра, то мы обязаны будем также вместе с вершиной x удалить и их. Действительно, ранее эти ребра вели в вершину x. Вести в никуда ребра не могут, так что нам вместе с вершиной x приходится удалять и все ребра, инцидентные данной вершине. Так, в примере мы удалили в графе G вершину 5. Вместе с ней мы вынуждены были удалить два инцидентных ей ребра — ребра i и g. Полученный в результате удаления вершины x граф обозначается обычно G − x. Очевидно, что и он является подграфом исходного графа G. В более общем случае S ∈ V (G) мы с помощью операции удаления вершин из подмножества S получаем подграф G − S, в котором по сравнению с исходным графом G удалены все вершины подмножества S вместе со всеми ребрами, инцидентными этим вершинам. 1.6.4. Как мы уже заметили, любой подграф графа G получается из G последовательным выполнением двух операций — удаления вершин и удаления ребер. Естественным кажется рас- смотреть два частных случая этой ситуации. Первый — это случай, когда мы в графе G удаляем только ребра, а второй — когда в G мы удаляем только вершины. Если мы при получении из графа G подграфа H используем лишь операцию удаления ребер, то мы получаем подграф, множество вершин которого совпадает с множеством V (G) вершин исходного графа. Такой подграф называется остовным подграфом (spanning subgraph) графа G (смотри рис.10,c). Второй частный случай — когда мы в графе G удаляем одну или несколько вершин. В резуль- тате такой операции мы получаем подграф H, индуцированным подмножеством оставшихся вершин графа G. Иными словами, подграфом H графа G, индуцированным подмножеством вершин S, называется граф, полученный из G удалением всех вершин, не принадлежащих мно- жеству S, вместе со всеми инцидентными этим вершинам ребрами (смотри рис.10,d). a b c d e f g (a) Исходный граф G a b d e g (b) Произвольный подграф H графа G a b c d e f g (c) Остовный подграф графа G a b d e f (d) Подграф H графа G, индуцированный множеством вершин {a, b, d, e, f } Рис. 10: Пример графа и его подграфов 2 Связность в графах 2.1. Следующее важное понятие, которое нам предстоит изучить — это понятие связности. 2.1.1. Прежде чем это понятие вводить, нам понадобится несколько дополнительных опреде- лений. Определение 2.1. Маршрутом (walk) в графе G из вершины x 0 в вершину x k называется чередующаяся последовательность x 0 , e 1 , x 1 , e 2 , x 2 , . . . , x k−1 , e k , x k вершин x i ∈ V (не обязательно различных) и ребер e i ∈ E, соединяющих вершины x i−1 и x i Говорят, что такой маршрут имеет длину k. Маршрут называется замкнутым, если x 0 = x k Пример 2.2. Последовательность вершин и ребер вида 1, a, 7, d, 2, c, 1, a, 7, j, 6 представляет собой маршрут в графе G, представленном на рис. 11,a. 1 2 3 4 5 6 7 a c d b e f g h i j (a) 1 2 3 4 5 6 7 a c d e f g h i j (b) Рис. 11 В случае простого графа любой маршрут полностью определяется последовательностью x 0 , x 1 , x 2 , . . . , x k−1 , x k , вершин x i ∈ V (G), любые два последовательных элемента x i−1 , x i которой являются смежными вершинами (т.е. соединены между собой ребром e i = {x i−1 , x i } ∈ E(G)). Пример 2.3. Подправим граф, изображенный на рис. 11,a, удалив одно из двух ребер, соеди- няющих вершины 1 и 7. В результате получим граф, показанный на рис. 11,b, в котором тот же самый маршрут можно задать так: 1, 7, 2, 1, 7, 6. Определение 2.4. Если все ребра e 1 , . . . , e k в маршруте различны, то такой маршрут назы- вается путем (path) из вершины x 0 в вершину x k . Если также и все вершины в данном пути различны, то такой путь называется простым. Пример 2.5. Маршрут вида 3, 4, 5, 3, 6 является путем в графе, изображенном на рис. 11,b, а маршрут вида 1, 2, 3, 6 является в этом графе простым путем. Определение 2.6. В случае, когда в пути в графе начальная и конечная вершины совпадают (x 0 = x k ), путь называется циклом. Путь называется простым циклом в случае, когда в нем совпадают только вершины x 0 и x k Пример 2.7. Путь 3, 5, 4, 3 в графе, показанном на рис. 11,a, является простым циклом. Путь вида 4, 5, 3, 6, 7, 2, 3, 4 в этом графе простым циклом не является — вершина 3 в таком цикле встречается два раза. Определение 2.8. Количество ребер в пути (цикла) называется длиной пути (цикла). 2.1.2. Теперь мы готовы определить понятие связных графов. Начнем с определения связности в неориентированных графах. 1 2 3 4 5 6 7 8 Рис. 12 Определение 2.9. Если вершины x, y ∈ V неориентированного графа G соединены хотя бы одним путем, то такие вершины называются связанными. Пример 2.10. Рассмотрим неориентированный граф G, изображенный на рис. 12. В этом графе вершины 1 и 3 являются связанными — они соединены между собой, например, путем 1, 2, 3. Вершины 1 и 8 в графе G связанными не являются. Несложно проверить, что связанность задает на множестве V вершин неориентированного гра- фа G отношение эквивалентности. Действительно, любая вершина связана сама с собой, если вершина x связана с вершиной y, то и вершина y связана с вершиной x. Наконец, если вер- шина x связана с вершиной y, а вершина y связана с вершиной z, то вершины x и z также оказываются связанными. Как и любое отношение эквивалентности, отношение связанности разбивает все множество вершин графа на классы эквивалентности, называющиеся компонентами связности графа. В рассмотренном на рис. 12 графе G мы имеем два класса эквивалентности, один из которых состоит из подмножества вершин {1, 2, 3, 4, 5}, а второй — из подмножества вершин {6, 7, 8}. Каждое из этих подмножеств вершин индуцирует некоторый связный подграф графа G. Определение 2.11. В случае, когда в графе G существует лишь одна компонента связности, то есть в случае, когда любые две вершины x, y графа соединены хотя бы одним путем, граф называется связным. В противном случае граф называется несвязным. 2.1.3. Понятие связности в орграфе несколько сложнее, чем в неориентированном графе. Определение 2.12. Вершины x и y орграфа D называются связанными, если в D существуют хотя бы один путь из x в y и хотя бы один путь из y в x. 1 2 3 4 5 Рис. 13 Пример 2.13. Рассмотрим орграф D, изображенный на рис 13. В этом графе вершины 2 и 5 являются связанными: существует путь 2, 1, 5, соединяющий вершину 2 с вершиной 5, а также путь 5, 2, соединяющий вершину 5 с вершиной 2. Вершины 2 и 3 в этом графе связанными не являются — из вершины 2 мы в вершину 3 сможем пройти по ребру (2, 3), а вот из вершины 3 в вершину 2 мы уже попасть не сможем. Определение 2.14. Орграф D называется сильно связным, если любые две его вершины являются связанными. Пример 2.15. Орграф D, изображенный на рис. 13, сильно связным не является. Примером сильно связного графа является его подграф, индуцированный вершинами {1, 2, 5}. Иногда наряду с этим понятием для орграфа вводят понятие слабой связности. Определение 2.16. Орграф D называется слабо связным, если соответствующий ему неори- ентированный граф G, получающийся заменой всех ориентированных ребер на неориентиро- ванные, является связным. Пример 2.17. Орграф D, изображенный на рис. 13, является, очевидно, слабо связным гра- фом. 2.1.4. Как и в случае неориентированного графа, в орграфе D отношение связанности является отношением эквивалентности. Как следствие, множество всех вершин V (D) орграфа D разби- вается с помощью этого отношения эквивалентности на классы попарно связанных вершин, которые называются компонентами сильной связности. Пример 2.18. Рассмотрим орграф D, изображенный на рис. 13. В нем имеются три компо- ненты сильной связности — подмножество вершин {1, 2, 5}, вершина 3 и вершина 4. Заметим, что в неориентированном графе между различными компонентами связности ребер не существует. В орграфе, как мы с вами видим, такие ребра могут существовать, однако направ- лены все они лишь от одной компоненты связности к другой. Именно, справедливо следующее достаточно очевидное утверждение. Лемма 2.19. Пусть H 1 , H 2 есть две различные компоненты сильной связности графа D, и пусть существует ребро e ∈ E(D) из H 1 в H 2 . Тогда ребра из H 2 в H 1 отсутствуют. Доказательство. Действительно, если ребро из H 2 в H 1 существует, то любые две вершины в множестве H 1 ∪ H 2 вершин оказываются связанными. Иными словами, H 1 ∪ H 2 представляет собой компоненту сильной связности графа D, что противоречит предположению о том, что H 1 и H 2 есть две различные компоненты сильной связности. Как следствие, по любому орграфу D можно построить так называемый граф C(D) компонент сильной связности графа D, вершинами которого будут компоненты сильной связности графа D, а ребрами — ребра графа D, направленные из одной компоненты сильной связности D к другой. {1, 2, 5} 3 4 Рис. 14: Граф компонент сильной связности На рис.14 показан граф C(D) компонент сильной связности орграфа D, изображенного на рис. 13. Он состоит из трех вершин и трех ребер. Основное свойство графа C(D) компонент сильной связности состоит в том, что в таком графе нет циклов. Теорема 2.20. В орграфе C(D) циклы отсутствуют, то есть он, как еще говорят, пред- ставляет собой ациклический орграф (DAG — directed acyclic graph). Доказательство. Если бы в таком графе существовал цикл вида H 1 → H 2 → . . . → H n → H 1 , то любые две вершины в объединении H 1 ∪ H 2 ∪ . . . ∪ H k оказались бы связанными. Действительно, внутри каждой компоненты H i мы, по определению сильной связности, можем попасть из любой вершины в любую вершину H i . Вершины же из разных компонент H i и H j мы также можем всегда связать с помощью пути, идущего из H i в H j , а также пути, соединяющего компоненты H j и H i Рис. 15: Орграф D и граф компонент сильной связности графа D 3 Деревья и их основные свойства 3.1. Одним из самых важных понятий теории графов является понятие дерева. Определение 3.1. Деревом называется простой связный граф без циклов. Произвольный (не обязательно связный) простой граф без циклов называется лесом. 1 2 3 4 5 8 6 7 9 10 11 12 Рис. 16 На рис. 16 в качестве примера изображено дерево T , построенное на двенадцати вершинах. 3.1.1. Приступим к изучению простейших свойств деревьев. Определение 3.2. Вершина графа, имеющая единичную степень, называется листом. В дереве на рис. 16 вершины 1, 3, 6, 7, 10, 11 и 12 являются листьями. Лемма 3.3. У любого дерева T , построенного на n > 2 вершинах, имеется как минимум два листа. x 0 x 1 x 2 x k−1 x k P (a) x 0 x 1 x 2 x k−1 x k P x k+1 (b) Рис. 17 Доказательство. Рассмотрим произвольный простой путь P = (x 0 , x 1 , . . . , x k ) максимальной дли- ны в T (рис. 17,a). Покажем, что концы этого пути – вершины x 0 и x k – обязаны быть листьями. Предположим, что это не так, то есть предположим, например, что из вершины x k исходят два или более ребра. Одно из них — это ребро {x k−1 , x k }. Любое другое исходящее из x k ребро e не может соединять x k ни с какой другой из оставшихся вершин пути P — в противном случае мы бы получили в графе цикл. Следовательно, ребро e соединяет x k с какой-то новой вершиной x k+1 графа T (рис. 17,b). Но в таком случае мы получаем в графе T простой путь (x 0 , x 1 , . . . , x k , x k+1 ), длина которого на единицу больше длины пути P . А это, в свою очередь, противоречит тому, что путь P является максимальным. 3.1.2. Из доказанной леммы достаточно легко следует одно из основных свойств дерева T . Теорема 3.4. В дереве T , построенном на n вершинах, имеется ровно (n − 1) ребро: |E| = |V | − 1 = n − 1. Доказательство проведем индукцией по количеству n вершин в графе. База индукции очевидна — дерево, состоящее из n = 1 вершины, не имеет ни одного ребра. Предположим теперь, что утверждение доказано для деревьев, построенных на n вершинах, и покажем, что оно остается верным для произвольного дерева с (n + 1)-й вершиной. Действительно, по доказанной выше лемме 3.3 у любого такого дерева имеется хотя бы один лист x. Удалим теперь этот лист x вместе с инцидентным ему ребром e. Полученный в резуль- тате такой операции граф T 0 останется, очевидно, связным, и дополнительных циклов в нем также не появится. Следовательно, граф T 0 является деревом, построенным на n вершинах. Но у такого дерева по индукционному предположению имеется (n − 1) ребро. Следовательно, у исходного дерева T имеется ровно n ребер. Достаточно очевидно и обратное утверждение. Теорема 3.5. Любой простой связный граф G, построенный на n вершинах и имеющий (n−1) ребро, является деревом. Доказательство. Действительно, выберем в графе G любую вершину и покрасим ее, например, в красный цвет. Затем начнем последовательно выполнять следующие действия: будем выбирать в G произвольную неокрашенную вершину x, смежную с одной из уже окрашенных вершин y, и красить ее в красный цвет. Одновременно с этим будем окрашивать в тот же цвет и ребро, соединившее x с окрашенной вершиной y графа G. Отметим теперь следующий важный момент: в процессе выполнения этих действий мы каждый раз к уже окрашенным вершинам добавляем какую-то новую вершину графа. Раз эта вершина отлична от старых вершин графа, то в получающемся на каждом шаге окрашенном подграфе графа G циклы появиться не могут. Заметим теперь, что за (n − 1) шаг мы окрасим таким образом все вершины и ребра графа G. Следовательно, в графе G циклы также отсутствуют, то есть он является деревом. Следствие 3.6. Всякий связный граф, построенный на n вершинах, имеет как минимум (n − − 1) ребро. Доказательство. Рассмотрим произвольный связный граф. Если такой граф не является дере- вом, то у него имеется хотя бы один цикл. В этом цикле мы всегда можем удалить одно ребро, и граф при этом останется связным. Будем продолжать этот процесс до тех пор, пока в графе не останется ни одного цикла. В результате получим простой связный граф без циклов, то есть дерево. Количество ребер у дерева равно (n − 1). Следовательно, у исходного графа имеется как минимум (n − 1) ребро. Замечание 3.7. Данное следствие другими словами можно переформулировать и так: у вся- кого связного графа существует остовное дерево. Получить это дерево можно, либо удаляя лишние ребра, либо (что более рационально) используя алгоритм, использованный при доказа- тельстве теоремы 3.5. Этот алгоритм, называемый поиском в глубину, очень часто используется в разнообразных приложениях, связанных с теорией графов. Так, например, с помощью этого алгоритма можно найти все компоненты связности неори- ентированного графа. Делается это так: вначале мы полагаем, что каждая вершина в графе неокрашена (или не пройдена алгоритмом, v.visited=false), а число компонент связности графа равно нулю. Затем в цикле мы перебираем все вершины графа. На каждом шаге цикла прове- ряем, окрашена ли текущая вершина. Если нет, то мы вызываем для нее процедуру поиска в глубину. В этой процедуре мы окрашиваем текущую вершину (v.visited=true), просматриваем список смежных с ней вершин, и в случае, если в этом списке обнаруживается неокрашенная вершина, рекурсивно вызываем для нее процедуру поиска в глубину. Каждый раз, когда мы вы- ходим из процедуры во внешний цикл, мы увеличиваем количество связных компонент графа на единицу. 3.1.3. Отметим в заключение еще одно важное свойство дерева — оно является минимально связным графом. Определение 3.8. Простой связный граф называется минимально связным, если удаление любого ребра приводит к нарушению связности графа. Теорема 3.9. Граф T является деревом тогда и только тогда, когда он является минимально связным графом. Доказательство практически очевидно. Действительно, предположим, что в произвольном ми- нимально связном графе T имеется цикл. Тогда мы можем удалить одно из ребер этого цикла, и получающийся в результате такой операции граф останется связным. Получили противоречие с тем, что T — минимально связный граф. Следовательно, любой минимально связный граф есть граф без циклов, то есть дерево. Предположим теперь, что в дереве T существует ребро e = {x, y}, после удаления которого граф остается связным. Последнее, в частности, означает, что в полученном после удаления ребра графе T 0 существует простой путь P , связывающий вершины x и y. Но тогда, добавляя к графу T 0 ребро {x, y}, мы получаем цикл P ∪ {x, y} в исходном графе T . А это противоречит тому, что T является деревом. Следствие 3.10. Граф T является деревом тогда и только тогда, когда для любых двух его вершин существует единственный простой путь, соединяющий эти вершины. Доказательство. Пусть в T для любой пары вершин существует единственный соединяющий их простой путь. Тогда T является минимально связным графом. Действительно, предположим, что мы можем удалить какое-то ребро e = {x, y}, и получающийся в результате такой операции граф остается связным. Но тогда в исходном графе T , помимо ребра {x, y}, существует и еще один простой путь, соединяющий вершины x и y, что невозможно. Обратно, пусть T является деревом, и пусть в нем существуют два различных простых пути P и Q, соединяющих какие-то две вершины x и y. Рассмотрим в P ребра, не принадлежащие Q, а в Q — ребра, не принадлежащие P . Объединение таких ребер образует, очевидно, один или несколько циклов, что противоречит тому, что T является деревом. |