Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 272
Текст из файла (страница 272)
Два Пути (ОО Щ е2 ОЬ-М но) и (ОО О(1Н2 ~Ь вЂ” и ОО) образуют один и тот же цикл, если существует такое целое 2, что О,' = О!;+ ! П„а ь для ! = О, 1,..., )с — 1 (один цикл получен из другого сдвигом). На рис. Б.2, (а) путь (1, 2, 4, 1) образует тот же цикл, что и пути (2, 4, 1, 2) и (4, 1, 2, 4). Этот цикл простой, но цикл (1, 2, 4, 5, 4, 1) таковым не является. Цикл (2, 2), образованный ребром (2, 2), представляет собой петлю. Ориентированный граф, не содержащий петель, называется простым. В неориентированном графе путь (оо, Ом..., еь) образует цика, если lс > О, но = гь и все ребра этого пути различны; цикл является простым, если вершины щ, оз,..., га различны. Например, на рис.
Б.2, (б) путь (1,2,5,1) представляет собой простой цикл. Граф, в котором нет простых циклов, называется ац имли ческим. Неорнентированный граф является связным (соппесгег!), если каждая его вершина достижима из всех прочих вершин. Связные компоненты неориентированного графа представляют собой классы эквивалентности вершин относительно достижимости (отношения "быть достижимым из"). Граф на рис.Б.2,(б) имеет три связных компонента: (1, 2, 5), (3, 6) н (4). Каждая вершина в (1, 2, 5) достижима из другой вершины этого множества. Неориентированный граф является связным тогда и только тогда, когда он состоит из единственного связного компонента. Ребра связного компонента инцидентны только вершинам этого компонента; другими словами, ребро (и, О) является ребром связного компонентг~ только если и и, и е являются вершинами этого компонента.
Ориентированный граф называется сильно связным (зпопй!у солпесгед), если любые его две вершины достижимы друг из друга. Любой ориентированный граф можно разбить на сильно связные компоненты (зпопя)у соппесгег! сошропепгз), которые определяются как классы эквивалентности отношения "являются взаимно достижимыми". Ориентированный граф считается сильно связным тогда и только тогда, когда он состоит нз единственного сильно связного компонента.
Граф парис. Б.2,(а) состоит из трех таких компонентов: (1, 2,4,5), (3) н (6). Все пары в множестве (1,2,4,5) являются взаимно достижимыми. Вершины (3,6) не образуют сильно связный компонент, поскольку из вершины 3 нельзя достичь вершины 6. Два графа, С = ((~,Е) и С' = (Г, Е'), изаиор4аны (ВопюгрЬ!с), если существует биекция г"; $' — ~ Г, такая, что (н, О) б Е тогда и только тогда, когда (2(п),!(О)) Е Е'. Другими словами, мы можем перенумеровать вершины С, превратив их в вершины С', но сохранив при этом ребра между вершина- 1774 Часть Г«дб Привозееиияг математические осиоеы б" )Ч)-" ( б) «Ф",' — — ',т,) (Р (6) (в) Рнс. В.З. (а) Пара нзоморфных графов. Вершины верхнего графа отображаются на вершины нюкнего графа следующим образом: Д1) = и,у(2) = и,г"(3) = ю, Д4) = х, ДЬ) = р,у"(б) = с.
(б) два графа, не являющихся изоморфными, посжшьку верхний граф имеет вершину степени 4, которой нет у нижнего графа ми в неизменном состоянии. На рис. Б.З, (а) показана пара изоморфных графов С и С' с множествами вершин (« = (1,2,3,4,5,6) и («г = (и,с,ш,х,р,х) соответственно. Отображение 1«на (««выглядит следуклцим образом: 7 (1) = и, У(2) = п, 7(3) = го, У(4) = х, У(5) = у, У(6) = х. Графы на рис.Б.З,(б) неизоморфны.
Хотя оба изображенных здесь графа имеют по 5 вершин и 7 ребер, граф в верхней части рисунка имеет вершину степени 4, которой нет у нижнего графа. Мы говорим, что граф С' = (1««, Е') является иодграфам (зпЪйгарЬ) графа С = (1«, Е), если («' С Ь' и Е' С Е. Если в графе С = (1«Е) выбрано подмножество 1«' С 1«, то подграфом графа С, ворон)сданным (шдпсед) множеством вершин («', является граф С' = ((«г, Е'), где Е' = ((и, о) Е Е: и, и б 1«') Подграф, порожденный множеством вершин (1, 2, 3, 6) на рис. Б.2, (а), показан на рис.
Б2, (в), и содержит следующее множество ребер: ((1, 2), (2, 2), (6, 3)). Для данного неориентированного графа С = ((«,Е) его ориеняавроеанывя версия (бйгес1еб уегзгоп) представляет собой ориентированный граф С' = (К Ее), где (и, о) б Е' тогда и только тоща, когда (и, о) Е Е. Другими словами, каждое неориентированное ребро (и, о) графа С заменяется в ориентированной версии двумя ориентированными ребрами — (и, и) и (и, и). Для ориентированного грифа С = (1«, Е) его иеорыентироваииая версия (нпсйгес(ед инга)оп) представляет собой неориентированный граф С' = ((«, Е'), где (н, о) е Е' тогда и только тогда, когда и ф и и (и, и) б Е.
Другими словами, неориентированная версия содержит ребра графа С "с удаленными стрелочками", причем петли из неориентированной версии убираются. Поскольку в неориентированном графе ребра (и, и) и (п,и) идентичны, неориентированная версия ориентированного графа содержит ребро толью по разу, даже если в ориентированном графе между вершинами и и о имеются два ориентированных ребра — (и, п) и (и, и). В ориентированном графе Ирнпахенне Е Мнажеоява и нрннне нуднжеонва 1225 С = (Ъ", Е) соседом (пе)йЬЬог) вершины и называется любая вершина, которая становится смежной с и в неориентированной версии, т.е. и является соседом и, если и ф и и либо (и, и) Е Е, либо (и,и) Е Е. В неориентированном графе вершины являются соседями, если они смежные. Некоторые виды графов имеют свои специальные названия.
Палиым (согпр!еГе) графом называется неориентированный граф, в котором каждая пара вершин образована смежными вершинами, т.е. который содержит все возможные ребра. Деудольным (Ь|ршт!ге) называется неориентированный граф С = (Ъ; Е), в ютором множество 1" может быть разделено на два множества, )гг и (гз, такие, что из (и, и) Е Е следует, что либо и й ! г и и й Уз, либо и Е $'з и и Е $'г. Ациклический неориентированный граф называется лесом (ГОгезг), а связный ациклический неориентированный граф — (сеободиым) деревам (ггее !гее) (см.
раздел Б.5). Имеется еще два варианта графов, с которыми вы можете встретиться. Это мультаграф (пш!ййгарЬ), который похож на неориентированный граф, но может содержать как петли, так и по нескольку ребер между вершинами. Гаиерграф (Ьурегйгарй) также похож на неориентированный граф, но содержит гаиерребра, юторые могут соединять произвольное количество вершин. Многие алгоритмы, разработанные для обычных ориентированных и неориентированных графов, могут быть обобщены для работы с такими графоподобными структурами. Сжатием (сопггасбоп) неориентированного графа С = (К Е) по ребру е = (и,и) называется граф С' = (Г,Е'), где Г = !" — (и,и) !2 (х) (х — новая вершина). Множество ребер Е' образуется из Е путем удаления ребра (и, и), и, кроме того, для каждой вершины и, инцидентной к и или и, удаляются ребра (и, ю) и (и, и) (если они имеются в Е) и добавляется новое ребро — (х, ш).
По сути, и и и "сжимаются" в одну вершину. Упражнения Б.4.1 На приеме каждый гость подсчитывает, околыш рукопожатий он сделал. По окончании приема вычисляется сумма рукопожатий каждого из гостей. Покажите, что полученная сумма четна, доказав следующую лемму о рукопожатиях: если С = (К Е) — неориентированный граф, то сумма степеней всех вершин равна удвоенному числу ребер декгее(и) = 2 ~Е( не У Б.4.2 Покажите, что если ориентированный или неориентированный граф содержит путь из вершины и в вершину и, то в нем есть простой путь между и и и.
Покажите, что если в ориентированном графе есть цикл, то в нем есть простой цикл. Б.4.3 Покажите, что для любого связного неориентированного графа С = (у', Е) выполняется соотношение ~Е( > !!2! — 1. )22б Часть РЯ(. Приволсенил: математические осноем Б.4.4 Покажите, что отношение "быть достижимым из" в неориентированном графе является отношением эквивалентности на множестве вершин графа. Какие из трех свойств отношения эквивалентности выполняются для отношения "быть достижимым из" в ориентированном графе? Б.4.
5 Изобразите неориентированную версию (рафа, показанного на рис. Б.2, (а), и ориентированную версию графа, показанного на рис. Б.2, (6). Б.4.6 * Покажите, что гнперграф можно представить как двудольный граф, в котором отношение смежности соответствует отношению инцидентности в гиперграфе. (Указание( одно множество вершин двудольного графа должно соответствовать вершинам гиперграфа, а другое множество — гиперребрам.) Б.5. Деревья Как и слово "граф", слово "дерево" употребляется в нескольких родственных смыслах.
Здесь представлены основные определения и математические свойства некоторых видов деревьев. Вопросы представления деревьев в памяти компьютера рассматриваются в разделах 10.4 и 22.1. Б.5,1. Свободные деревья Как уже говорилось в разделе Б.4, свободные деревья (Ггее (гее), или деревья без выделенного корня, представляют собой связный ациклический неориентированный граф. Прилагательное "свободный" зачастую опускается, когда речь идет о графе, являюшемся деревом. Если неориентнрованный граф ацикличный, но, возможно, несвязный, то он является лесам. Многие алгоритмы, разработанные для деревьев, могут работать и с лесом. Пример свободного дерева показан на рис. Б.4,(а), а леса — на рис.
Б.4,(б). Лес на рис. Б.4,(б) не является деревом в си- (в) (б) (в) Рис. Б.4. (а) Свободное дерево. (б) Лес. (в) Граф, содержащий дилл, а новому нс лтлиощийсл нн деревом, ни лесом. Приложение д Множества и лрочие художеслнш игу лу того, что представляющий его граф не является связным. Граф на рис. Б.4, (в) связный, но содержит цикл, а потому не может быть ни деревом, ни лесом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
