Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 44
Текст из файла (страница 44)
264 ГЛАВА 6. Графы, ориентороеенные графы и деревья Обратим внимание, что, хотя согласно определению ориентированного графа он может иметь петли, до настояшего момента не рассматривалась ситуация, когда из вершины а в вершину Ь может выходить более чем одно ребро. Ориентированный граф с более чем одним ребром из одной вершины в другую называется мультиграфом, или, более точно, ориентированным мультиграфом. Если каждое ребро помечено, будем говорить, что это размеченный ориентированный, или просто размеченный граф, с пониманием того, что это ориентированный граф.
Поскольку в действительности не имеет смысла иметь два ребра из вершины а в вершину Ь, если нет возможности их отличать, обычно их каким-то образом нумеруют. Формально размеченный граф можно определить следуюшим образом. Графически ребро е = (а,1,Ь) размеченного графа обозначается, как на рис. 6.26, или, как на рис. 6.27, если ребро — петля.
— ° ь а Рис. 6.26 Рис. 6.27 Графы, представленные на рис. 6.28 и 6.29, являются примерами типичных размеченных графов, называемых автоматами. ® ®-'®-о Рис. 6.29 К этим вопросам мы вернемся в главе 17. РДЗДЕЛ б.2. Ориентированные графы 255 ОПРЕДЕЛЕНИЕ 6.32. Ориентированный граф С'($", Е') называется ориентированным аодграфом ориентированного графа С(К Е), обозначается С'(Ъ", Е') -с С(К Е), если $" С И и Е' С Е. Таким образом, каждая вершина в С' является вершиной в С и каждое ориентированное ребро в С' является ориентированным ребром в С. Понятие ориентированного пути в ориентированном графе вводится по аналогии с понятием пути в графе.
Разница лишь в том, что, перемешаясь вдоль ориентированного пути, двигаться нужно в направлении, задаваемом ориентацией ребер. ОПРЕДЕЛЕНИЕ 6.33. Ориентированный путь из а в Ь задается последовательностью вершин поп!огиз...!!„, где а = оо, Ь = п„и (и, ып,) для 1 < 1 < и — ориентированное ребро. Длиной ориентированного пути называется количество ориентированных ребер, входяших в путь. ПРИМЕР 6.34. Для графа С, изображенного на рис.
6.30, ' ~Гг Рис. б.ЗО графы на рис. 6.31 и 6.32 являются подграфами. Ориентированные пути в С включают уоо1!!2цг о1о2~4 н ооозо4. ° ! ~!! ° ! ° > ° 4 ° '! Рис. б.32 Рис. б.б! Теперь для заданного ориентированного графа С будет построен неориентированный граф С' такой, что каждое ориентированное ребро С (исключая петли) станет неориентированным ребром графа С'. Пусть для каждого ориентированного графа С(Ъ', Е) Е' = Š— ((и, о): о 6 1'), так что С'($;Е') — ориентированный подграф графа С(К Е), в котором удалены петли. Пусть  — симметричное замыкание множества Е', так что если (а,Ь) 6 Е', то (а,Ь), (Ь,а) е )т, а Е' — множество ребер, представляюших отношение В. В таком случае граф С'(К,Е') называется соотнесенным графом 266 ГЛАВА б.
Графы, ориентироеанные графы и деревья ориентированного графа С(К, Е). Упрощая формулировку, можно сказать, что множество ребер Е' неориентированного графа С'(Ъ; Е') можно определить таким образом: 1а, Ь) а Е' тогда и только тогда, когда для различных вершин а и Ь ребро (а, Ь) б С или (Ь,а) е С. ПРИМЕР 6.36. Для ориентированного графа на рис. 6.30 соотнесенным будет граф, показанный на рис. 6.33. У, "з Рис, б.зз Ориентированный граф является связным, поскольку его соотнесенный граф связный. Рассматриваемый граф однако не является сильно связным, поскольку из и1 в из не существует ориентированного пути.
П ° УПРАЖНЕНИЯ 1. Найдите вершины и ориентированные ребра для приведенных ниже орграфов. Для каждой вершины определите степень входа и степень выхода. Имеются ли здесь источники и стоки? а) б) а Ь РАЗДЕЛ б.2. Ороентироеанные графы 257 г) в) с) 2. Найдите вершины и ориентированные ребра для приведенных ниже орграфов. Для каждой вершины определите степень входа и степень выхода.
Имеются ли здесь источники и стоки? б) а) М г) в) 3. Для каждого графа из предыдушего упражнения постройте четыре подграфа. 4. Найдите вершины и ориентированные ребра для приведенных ниже орграфов. Для каждой вершины определите степень входа и степень выхода. Имеются ли здесь источники и стоки? а) б) 288 ГЛАВА б. Графы, ориентированные графы и деревья г) в) ° + ° ~ ° ) б.
Для каждого графа из предыдущего упражнения постройте четыре подграфа. 6. Определите простой ориентированный путь. 7. Определите ориентированный цикл. 8. Определите простой ориентированный цикл. 9. Который из приведенных ниже орграфов является связным? Какой из них является сильно связным? б) а) — ь у ') г) в) 1О. Для каждого графа из предыдущего упражнения найдите, если возможно, ориентированный путь длины 2, ориентированный путь длины 3, ориентированный путь длины 4 и ориентированный путь длины 5.
Приведите пример пути максимальной длины. Какой самый длинный простой цикл (если таковой существует) может быть построен? 11. Который из приведенных ниже орграфов является связным? Какой из них является сильно связным? б) а) ° д~ ° е в~ — — -ву' РлзДеп 6.3. Деревья 259 г) в) ('м Зе ~ев 12. Для каждого графа из предыдущего упражнения найдите, если возможно, ориентированный путь длины 2, ориентированный путь длины 3, ориентированный путь длины 4 и ориентированный путь длины 5. Приведите пример пути максимальной длины.
Какой самый длинный простой цикл (если таковой существует) может быть построен? 6.3. ДЕРЕВЬЯ Когда Джойс Килмер (Зоусе К!!гпег, 1886-1918) писал: "Нет, не увижу, это ясно, поэмы дерева прекрасней", — вряд ли он имел в виду деревья, которые мы будем рассматривать. Разрешим, однако, наши сомнения в пользу автора этих строк. Дерево — это граф без циклов.
Лес — это граф, компоненты которого являются деревьями (почему бы и нет!). Понятие дерева широко используется во многих областях математики и информатики. Например, они используются как инструмент при вычислениях, как удобный способ хранения данных, способ сортировки или поиска данных. Некоторые из этих приложений будут рассмотрены в последующих разделах. Дерево и названо деревом, поскольку, будучи нарисованным, выглядит как дерево, только перевернутое "вверх ногами". Граф, изображенный на рис. 6.34, является примером дерева. Рис. 6.34 В одной из последующих глав будет показано, что это дерево можно использовать для демонстрации результатов трехкратного подбрасывания монеты.
Граф на рис. 6.35 не является деревом, поскольку содержит цикл. Граф на рис. 6.36— это лес. Рис. б.ЗЗ Рис. б.Зб 260 ГЛАВА б. Графы, оривнтироввнныв грифы и деревья Достаточно развитое генеалогическое дерево образует дерево. Если начать с конкретной (хорошо известной) личности и провести ребра между каждым из родителей и каждым сыном или дочерью, это сформирует дерево. При построении генеалогического дерева, однако, необходимо быть очень осторожным, чтобы браки между дальними родственниками не образовывали циклов. Другим примером дерева может служить организационный устав.
Дерево на рис. 6.37 — типичное частичное организационное дерево для университета. В этом разделе, тем не менее, деревья будем рассматривать как графы. Ректор Проректор по административно- хозяиственной части Проректор ло учебной работе Декан ло Декан по Декан ло бизнес-циклу педагогике гуманитарным и точным дисциплинам Заи. по Зам. по Зам. ло коммерческой строительству студенческим деятельности и эксплуатации вопросам зданий Зав. Зав.
кафедрой кафедрой математики и обигественнык информатики наук ! Методист 1 Преподаватели Зам, по Зав. научной кафедрой работе прикладного искусства Рис. б.З7 Ориентированное дерево Т представляет собой свободный от петель ориентированный граф, соотнесенный граф которого является деревом; так что если существует путь от вершины а к вершине 6, то он единственный. Сначала заметим, что если в ориентированном дереве имеется ребро (а, Ь), тогда не существует ребро (Ь, а), в противном случае путь аЬа был бы циклом, и путь из а в Ь не был бы единственным. Таким образом, множество Е, которое для дерева представляет собой как множество ребер, так и отношение, обладает таким свойством, что если (а,6) е Е, то (Ь,а) ф Е.
Такое отношение называется асимметричным. Возвращаясь к (неориентированным) деревьям, сначала отметим, что если дерево имеет хотя бы одно ребро, оно имеет хотя бы две вершины со степенью 1. Чтобы убедиться в этом, рассмотрим для заданного дерева Т возможные пути. Если у дерева и вершин, тогда длина пути не может превысить и — 1, так как каждую вершину можно использовать только один раз. В противном случае получились бы циклы, а у дерева нет циклов. Поэтому существует максимальный путь, который нельзя продлить, чтобы получить более длинный путь. Предположим, что путь начинается в вершине а и заканчивается в вершине 6.
Как а, так и Ь РАЗЛЕП б.а. Деревья 261 должны иметь степень 1, поскольку в противном случае путь можно было бы продолжить. Но это противоречит тому, что путь максимальный. Вершины степени 1 называются листьями. Другие вершины называются внутренними вершинами. Максимальный путь не обязательно совпадает с самым длинным путем в дереве. Например, в дереве на рис. 6.38 путь еоезез является максимальным путем. Вершины ез, е4, ез, ев и ет представляют собой листья. Р .
бЗВ Деревья обладают одним весьма интересным свойством, которое мы сейчас докажем. ТЕОРЕМА 6.37. Для любых двух вершин а и Ь дерева Т существует единственный путь из а в Ь. ДОКАЗАТЕЛЬСТВО. Для доказательства используется тот факт, что контрапозиция утверждения логически эквивалентна самому утверждению. Поэтому предположим, что для некоторых вершин а и 6 дерева Т путь из а в Ь не является единственным, и покажем, что в таком случае Т не будет деревом. Допустим, что существуют два различных пути: еоегез.
е„длины п и еое',ез . е' длины пт, где а = по и 6 = и„= и„',. В каждом пути должна существовать первая вершина, начиная с которой соответствующие вершины не совпадают, скажем е, ф е,', и в каждом из путей должна существовать точка, начиная с которой вершины Р ! / У Ф опять одни и те же, скажем, е = оь. Тогда тн гтчеььге,+з ..о еьиь,иь зир; является циклом, поэтому граф Т не является деревом. На основании следующей теоремы можно убедиться в том, что верна также и обратная теорема.
Поэтому дерево можно определить как граф, в котором между двумя его вершинами имеется только один путь. ТЕОРЕМА 6.38. Если для любых двух вершин графа С существует единственный путь из вершины а в вершину Ь, тогда С вЂ” дерево. ДОКАЗАТЕЛЬСТВО. Опять покажем справедливость теоремы, доказывая контра- позицию исходного утверждения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
