Алгоритмы - построение и анализ (1021735), страница 251
Текст из файла (страница 251)
На рис. Б.2а и рис. Б.2б вершина 2 является смежной с вершиной 1, поскольку ребро (1, 2) имеется в обоих графах. Вершина ! смежна с вершиной 2 только на рис. Б.2б. Степенью (беягее) вершины в неориентированном графе называется число ребер, соединяющих ее с другими вершинами.
Например, вершина 2 на рис. Б.2б имеет степень 2. Вершина, степень которой равна О (как, например, у вершины 4 на рис. Б.2б), называется изолированной (!зо!агеб). В ориентированном графе различают исходящую степень (ош-оейгее), которая равна количеству выходящих из вершины ребер, и входяьцую степень (!п-бейгее), которая равна количеству входящих в вершину ребер. Степень (бейгее) вершины в ориентированном графе равна сумме ее входящей и исходящей степеней. Так, на рис. Б.2а вершина 2 имеет входящую степень 2, исходящую — 3, так что степень данной вершины равна 5. Путь (маршрут) длины й от вершины и к вершине и' в графе С = (!г, Е) представляет собой последовательность (оо,щ,оз,...,оь) вершин, такую что и = оо, и' = оь и (ю; 1,о;) Е Е для 1 = 1,2,...,к. Длиной пути называется количество составляющих его ребер.
Путь содержит (соп!а!пз) вершины оо, о!, оз,..., оь и ребра (оо, о1), (ом оз),..., (оь ы оь). Всегда имеется путь нулевой длины из вершины в нее саму Если имеется путь р из вершины и в вершину и', то говорят, что вершина и' достижима (геасЬаЫе) из и по пути р, что иногда в ориентированном графе С записывается как и -» и'. Путь является простым (з!шр!е), если все вершины пути различны. Например, на рис. Б.2а путь (1, 2, 5, 4) является простым путем длины 3; путь (2, 5, 4, 5) простым не является.
Подпуть (зпЬра!Ь) пути р = (оо, щ,..., оь) представляет собой непрерывную подпоследовательность его вершин, т.е. для любых О < 1 < у < к последовательность вершин (о;, еч+1,..., о ) является подпутем р. В ориентированном графе путь (оо, о1,..., ьь) образует цикл (сус!е), если оо = = и, и путь содержит по крайней мере одно ребро. Цикл называется простым, если кроме того все вершины о1,оз,...,оь различны. Петля является циклом с длиной ! .
Два пути — (оо, о1,..., оь и по) и (ц~, о1~,..., оь, оо) — образуют один и тот же цикл, если существует такое целое у, что о,' = об+у! ь,ьв ь для 1 = О, 1,..., /с — 1 (один цикл получен из другого сдвигом). На рис. Б.2а путь Приложение Б. Множества и прочие художества 1215 (1,2,4,1) образует тот же цикл, что и пути (2,4,1, 2) и (4,1,2,4). Этот цикл простой, цикл (1, 2, 4, 5, 4, 1) таковым не является. Цикл (2, 2), образованный ребром (2, 2), представляет собой петлю.
Ориентированный граф, не содержащий петель, называется простым. В неориентированном графе путь (оо, сы..., оь) образует (нростой) цикл, если /с > 3, ео = оь и все вершины ос, оз,..., оь различны. Например, на рис. Б.2б путь (1, 2, 5, 1) является циклом. Граф без циклов называется ациклическим (асусйс). Неориентированный граф является связным (соппессед), если любая его вершина достижима из другой по некоторому пути. Для неориентированного графа отношение "быть достижимым из** является отношением эквивалентности на множестве вершин. Классы эквивалентности называются связными квмяонентаии (соппессед сошропепсз) графа.
Например, на рис. Б.2б имеются три связных компонента: (1,2,5), (3, 6) и (4). Каждая вершина в (1, 2, 5) достижима из другой вершины этого множества. Неориентированный граф считается связным тогда и только тогда, когда он состоит из единственного связного компонента. Ориентированный граф называется сильно связным (зсгопя1у соппессед), если любые его две вершины достижимы друг из друга. Любой ориентированный граф можно разбить на сильно связные каияоненты (зсгопя!у соппессес1 сошропепсз), которые определяются как классы эквивалентности отношения взаимной достижимости. Ориентированный граф считается сильно связным тогда и только тогда, югда он состоит из единственного сильно связного компонента Граф на рис.
Б.2а состоит из трех таких компонентов: (1, 2, 4, 5), (3) и (6). Все пары в множестве (1, 2, 4, 5) являются взаимно достижимыми. Вершины (3, 6) не образуют сильно связный юмпонент, поскольку из вершины 3 нельзя достичь вершины 6. Два графа С = ()г, Е) и С' = (У', Е') изоморфны (1зошогрЬ1с), если существует биекция г": У -+ Г, такая что (сс, ц) Е Е тогда и только тосда, югда (Г" (и), С' (ю)) Е Е'. Другими словами, мы можем перенумеровать вершины С, превратив их в вершины С', сохранив при этом ребра между вершинами в неизменном состоянии. На рис. Б.За показана пара изоморфных графов С и С' с множествами вершин У = (1, 2, 3,4, 5, 6) и Ъ" = (и, е, со, х, у, г) соответственно. Отображение Р на Г выглядит следующим образом: г (1) = и, г" (2) = о, 1 (3) = и, 1' (4) = х, 7" (5) = у, Г" (6) = г.
Графы на рис. Б.Зб неизоморфны. Хотя оба изображенных здесь графа имеют по 5 вершин и 7 ребер, граф в верхней части рисунка имеет вершину степени 4, которой нет у нижнего графа. Мы говорим, что граф С' = (Ъ", Е') является нодграфом (зпЬягарЬ) С = = Я Е), если 1г' С У и Е' С Е. Если в графе С = (1г Е) выбрано подмножество Ъ" С У, то подграфом графа С, порожденным (1попсео) множеством вершин Г, является граф С' = (Ъ", Е'), где Е' = ((и,с) Е Е: и,с Е У) . 1216 Часть Ч!П. Приложения: математические основы Рис. Б.З. Изоморфиые и иеизоморфиые графы Подграф, порожденный множеством вершин (1, 2,3,61 на рис.
Б.2а, показан на рис. Б.2в, он содержит следующее множество ребер: ((1, 2), (2, 2), (6, 3)). Для данного неориентированного графа С = (У, Е) его орненнгнрованная версия (йгес1ео чепйоп) представляет собой ориентированный граф С' = (К Е'), где (и, и) б Е' тогда и только тогда, когда (и, и) Е Е.
Другими словами, каждое неориентированное ребро (и,и) графа С заменяется в ориентированной версии двумя ориентированными ребрами (и,и) и (и,и). Для ориентированного графа С = (К Е) его неорнентнрованная версия (ипо1гес1ео чепйоп) представляет собой неориентированный граф С' = ($; Е'), где (и, и) е Е' тогда и только тогда, когда и ф и и (и, и) Е Е. Другими словами, неориентированная версия содержит ребра графа С "с удаленными стрелочками", причем петли из неориентированной версии убираются. Поскольку в неориентированном графе ребра (и, и) и (и, и) идентичны, неориентированная версия ориентированного графа содержит ребро только по разу, даже если в ориентированном графе между вершинами и и и имеются два ориентированных ребра (и, и) и (и, и). В ориентированном графе сосвдан (пе1яЬЬог) вершины и называется любая вершина, которая становится смежной с и в неориентированной версии, т.е. и является соседом и, если и ф и и либо (и, и) Е Е, либо (и, и) й Е.
В неориентированном графе смежные вершины являются соседями. Определенные виды графов имеют свои специальные названия. Полным (сошр1е1е) графом называется неориентированный граф, в котором каждая пара вершин образована смежными вершинами, т.е. который содержит все возможные ребра. Двудальным (Ь1рагйе) называется неориентированный граф С = (К Е), в котором множество Ъ' может быть разделено на два множества 1~~ и Уз, такие что из (и,и) е Е следует, что либо и Е 1'~ и и е чз, либо и й 1гз и и б 1~ы Приложение Б. Множества и прочие художества 1217 Ациклический неориентированный граф называется лесам (Гогов!), а связный ацнклический неориентнрованный граф — (свободным) деревам (1гее !гее). Имеется еще два варианта графов, с которыми вы можете встретиться. Это мулыииграф (пш!1!Бгарй), который похож на неориентированный граф, но может содержать как петли, так и по несколько ребер между вершинами.
Гилерграф (!зурегйгар!з) также похож на неориентированный граф, но он содержит гилерребра, которые могут соединять произвольное количество вершин. Многие алгоритмы, разработанные для обычных ориентированных и неориентированных графов, могут быть обобщены для работы с такими графоподобными структурами. Сжатием (соп1гасбоп) неориентированного графа С = (У, Е) по ребру е = = (и, и) называется граф С' = (У', Е'), где У' = У вЂ” (и, и) ! ! (х) (х — новая вершина).
Множество ребер Е' образуется из Е путем удаления ребра (и,и). Кроме того, для каждой вершины ш, инцидентной к и или и, удаляются ребра (и, ш) и (и, ы) (если они имеются в Е) и добавляется новое ребро (х, ш). Упражнения Б.4-1. На приеме каждый гость подсчитывает, сюлью рукопожатий он сделал. По окончании приема вычисляется сумма рукопожатий каждого из гостей. Покажите, что полученная сумма четна, доказав следующую лемму а рукалажаюаилх: если С = (У, Е) — неориентированный граф, то сумма степеней всех вершин равна удвоенному числу ребер 2 „у г!еягее (и) = = 2)Е(.
Б.4-2. Покажите, что если ориентированный или неориентированный граф содержит путь из вершины и в вершину и, то в нем есть простой путь между и и и. Покажите, что если в ориентированном графе есть цикл, то в ием есть простой цикл. Б.4-3. Покажите, что для любого связного неориентированного графа С = = (У, Е) выполняется соотношение !Е! > )У! — 1.
Б.4-4. Проверьте, что отношение "быть достижимым из" в неориентированном графе является отношением эквивалентности на множестве вершин графа. Какие из трех свойств отношения эквивалентности выполняются для отношения "быть достижимым из" в ориентированном графе? Б.4-5. Изобразите неориентированную версию графа на рис. Б.2а и ориентированную версию графа на рис. Б.26. * Б.4-6. Покажите, что гиперграф можно представить как двудольный граф, в котором отношение смежности соответствует отношению инцидентности в гиперграфе. (Указание: одно множество вершин двудольного графа должно соответствовать вершинам гиперграфа, а второе множество— гиперребрам.) Часть ЧН1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
