Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 252
Текст из файла (страница 252)
Б.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. Приложения: математические основы 1218 Б.5 Деревья Как и слово "граф", слово "дерево*' также употребляется в несюльких родственных смыслах. Здесь представлены основные определения и математические свойства неюторых видов деревьев.
Вопросы представления деревьев в памяти компьютера рассматриваются в разделах 10.4 и 22.1. Б.5.1 Свободные деревья Как уже говорилось в разделе Б.4, свободные деревья (Ггее ггее), или деревья без выделенного корня, представляют собой связный ациклический неориентированный граф. Прилагательное "свободный" зачастую опускается, когда мы говорим о графе, являющемся деревом. Многие разработанные для деревьев алгоритмы могут работать и с лесом. Пример дерева показан на рис.
Б.4а, леса— на рис. Б.4б. Лес не является деревом в силу того, что представляющий его граф не является связным. Граф на рис. Б.4в содержит цикл, а потому не может быть ни деревом, ни лесом. В следующей теореме указано несколько важных свойств деревьев. Теорема Б.2 (Свойства свободных деревьев). Пусть С = (1г, Е) — неориентированный граф. Тогда следующие утверждения равносильны.
1. С вЂ” свободное дерево. 2. Любые две вершины С соединяются при помощи единственного простого пути. 3. С вЂ” связный граф, но при удалении из Е любого ребра перестает быть таковым. 4. С вЂ” связный граф, и )Е! = ٠— 1. 5. С вЂ” ациклический граф, и )Е~ = ٠— 1. б. С вЂ” ациклический граф, но при добавлении любого ребра в Е получается граф, содержащий цикл. б) Рис. Б.4. Примеры дерева, леса и графа, который ие является деревом или лесом из- за наличия цикла Приложение Б. Множества и прочие художества 1219 к! Рис.
Б.5. Иллюстрация к доказательству теоремы Б.2 Доказательство. (1)=ь(2). Поскольку дерево является связным, для любых двух вершин С имеется как минимум один соединяющий их простой путь. Пусть и и ц — вершины, соединенные двумя простыми путями р1 и рз, как показано на рис. Б.5. Пусть ш — вершина, в которой пути впервые расходятся, т.е. следующие за ю вершины на путях р1 и рз, соответственно, х и у, причем х ~ У. Пусть я — первая вершина, в которой пути вновь сходятся, т.е.
я — первая после и вершина на пути рп которая также принадлежит пути рз. Пусть р' — подпугь р1 от зц через х до г, а р" — подпуть рз от и через у до г. Пути р' и р" не имеют общих точек, кроме конечных. Тогда путь, образованный объединением р' и пути, обратного к р", образует цикл. Это противоречит нашему предположению о том, что С является деревом. Таким образом, если С вЂ” дерево„то между вершинами не может быть больше одного соединяющего их простого пути.
(2)=ь(3). Если любые две вершины С соединяются единственным простым путем, то С вЂ” связный граф. Пусть (и, ц) — ребро из Е. Это ребро представляет собой путь от и до ц, а значит, это единственный путь от и до ц. Если мы удалим из графа путь (и, ц), пути от и до и не будет, а граф перестанет быть связным. (3)=ь(4). По условию граф С является связным, а из упражнения Б.4-3 нам известно, что )Е( > ٠— 1. Докажем по индукции, что )Е! < ٠— 1. Связный граф с одной или двумя вершинами имеет ребер на одно меньше, чем вершин. Предположим, что С имеет и > 3 вершин и что для меньшего числа вершин выполнение условия ~Е~ < )Ц вЂ” 1 доказано.
Удаление произвольного ребра из С разделяет граф на /с > 2 связных компонентов (на самом деле /с = 2). Каждый компонент удовлетворяет условию (3) теоремы, т.к. в противном случае этому условию не удовлетворяет само дерево С. Тогда, по индукции, количество ребер во всех компонентах не превышает ~Ц вЂ” /с < (Ц вЂ” 2. Добавление удаленного ребра дает нам неравенство )Е! < ٠— 1. (4)=ь(5). Предположим, что граф С является связным и что )Е~ = (Ц вЂ” 1. Мы должны показать, что граф С ациклический.
Предположим, что граф содержит цикл, состоящий из и вершин цы цз,..., ць', без потери общности можно считать, что это простой цикл. Пусть Сь = (Уь Еь) — подграф С, состоящий из данного Часть ЧП1. Приложения: математические основы 1220 цикла. Заметим, что )Ъ~! = ~Еь~ = й. Если )с < Щ, то должна существовать веРшина пь+з Е 1г — )гь смежнаЯ с некотоРой веРшиной о; Е 1гам что следУет из связности С. Определим подграф Сь+з = Я+ы Еььг) графа С как подграф, У которого 1я+з = Ъа 0 (пя+з) и Еь+з — — Еь 0((о;,ил+1)). Заметим, что (Ъ~+г~ = = ~Ел+1~ = )с+ 1. Если ге + 1 < Щ, мы можем продолжить наше построение, аналогично определяя Сь+з и т.д.
до тех пор, пока не получим С„= Я„Е„), такой что и = Щ, Ъ'„= У и )Е„! = ))г„! = Щ. Поскольку ф— подграф С, Е„С С Е, следовательно, )Ц > )Ъ'), что противоречит предположению )Е) = ~Ц вЂ” 1. Следовательно, граф С ациклический.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
