Введение в прикладную комбинаторику, Кофман А. (984071), страница 28
Текст из файла (страница 28)
$ 36. Плоские р-графы Говорят, что р-граф плоский, если его можно представить на плоскости таким образом, что вершины изображаются различнымн точками, а ребра — простымн кривыми, которые могут 205 пересекаться лишь в вершинах. В этом случае также говорят, что граф «отображается на плоскость». 5(ожно говорить также о возможности отображения графа на другие поверхности (сферу, тор и т. и.), но мы будем рассматривать лишь отображения на плоскость.
Например, граф на рис. 153 плоский, а граф на рис, 154 — нет. Грани плоского р-графа. Область плоскости, ограниченная ребрами связного плоского р-графа и не содержащая внутри себя ни ребер, ни вершин, на- О ге зывается его гранью. Внешняя неограниченная грань называется бесконечной гранью.
Рис. 15 К Рис. 153. Например, р-граф на рие. 163 обладает девятью гранями. 1Я °, )9 где ~и — бесконечная грань. Некоторые важные теоремы о плоских р-графах. Приведем несколько простых теорем, доказательства которых читатель найдет в 181. 1) Для плоского р-графа с )Ч вершинами, М ребрами и Р гранями справедливо соотношение лг — М+ р *2. (88П) 2) Во всяком плоском 1-графе найдетоя вершина, степень которой не превосходит 5. 3) Всякий плоский 1-граф является 6-хроматическим. Возможно, каждый плоский 1-граф является даже 4-хроматическим, но это лишь предположение.
Двойственный граф плоского связного р-графа. Рассмотрим плоский связный р-граф бь в котором нет вершин степени, меньшей 2; поставим ему в соответствие некоторый плоский связный о-граф с"м называемый двойственным к 6ь Каждой грани г графа б~ сопоставим вершину У~ графа Ом каждому ребру йи в 6~ сопоставим ребро б в бм соединяющее вершины У„и У„соответствующие граням г и з, примыкающим к ребру йм 206 л / l l 7 Ю С / 1 / ! / ! ! ! l 207 Например (см.
рис. 155), граф 6я (пунктирные линии и кружки) двойствен графу 6! (сплошные линии и точки). Заметим, что г/ может как совпадать, так и не совпадать с р. Например, граф 6! на рис. 155 является З-графом, а бя является 2-графом. Использование слова «двойственный» оправдано тем, что если бя — двойственный граф к 6!, то 6! — двойственный граф к бя. Алгоритм построения плоского изображения '). Этот метод позволяет установить, является ли граф плоским. Заметим, что достаточно рассматривать 1-гра- А фы, так как любой р-граф сводится к 1-графу (если слить параллельные ребра в одно). Пусть задан частичный под- .А;- -А;С граф') 6,=(Е„О,) графа 6= ~~Е' <9' = (Е, О). Будем называть куском ! графа 6 относительно 6,: Е С' Е 1) компоненту связности 6! = = (Е! О!) подграфа 6'=(Е— — Е„О'), порожденного подмножеством вершин Š— Еп дополненную всеми ребрами, инцидент- Рис. 166.
ными вершинам из Е!, и всеми вершинами этих ребер, принадлежащими Е, (зти последние называются <контактными точками»); 2) а также ребро й9п О!, концы которого принадлежат Еь вместе с его концами. Алгоритм использует последовательный процесс присоединения к некоторому плоскому частичному подграфу 6! цепи )г!, оба конца котоРой (и только они) — веРшины 6!Я. Эта цепь разобьет одну из граней 6У на две. В качестве начального плоского графа Щ выбирают некоторый цикл графа 6. Чтобы перейти от подграфа 6Я! к 6!ае!. предварительно рассматривают все куски гв! графа 6 относительно 6!. Мы скажем, что грань Г» графа 6а! и кусок Р/ совместимы, если все его контактные точки принадлежат множеству вершин атой грани. Лля каждого куска определяем грани, которые с ннм совместимы.
Возможны три случая. ') Си. Де и укроп, М а ля г р а нж и Пер тю иве (П. /7его о погон, У, Ма!Краине, й. Р ег1п1ае1), Пгаркеа р1апа!геа, йеаоппа!ааапсе е1 ге. ргьяеп/аг!опа р1апа!геа 1оро!он!Чпеа, йетие Ггапсаме 6е йеснегске Орегаиоппе11е, № 30, 1-ег 1гпп, 1964, 33 — 47. г) Для неориентнронаннмх графов понятия подграфа и частичного графа определяются так же, как и а 6 26. 1. Некоторый кусок не совместим ни с какой гранью графа ОРы Тогда граф не плоский. 2.
Какой-либо кусок совместим с единственной гранью (к графа О';. Тогда выберем в этом куске цепь )сн такую, что оба ее конца (и только они) принадлежат ОР1. Дополняя 6', ребрами и вершинами этой цепи, получаем Ор4н проводя )а1 внутри грани ~». 3. Если каждый из кусков рз совместим по крайней мере с двумя гранями графа 6Р, то нетрудно показать1), что можно выбрать цепь )ст в любом из кусков и действовать как в случае 2. 5 а) а) су) су) 4 Рис. 156.
Рис. !57. П р и м е р, Проиллюстрируем этот алгоритм на примере графа О =(Е, О) на рис. 156. Шаг 1. Берем произвольный цикл, например йо — — (1, 2, 6, 5, 1), представляюший плоский граф 6Р~ (рис. 157, а). Грани 6;; А,— внешняя грань (1, 2, 6, 5, 1), Во — внутренняя грань (1, 2, 6, 5, 1). Куски графа 6 относительно 6РО Совместимые грани Контактные точки Вершины куска Кусок Р, Ра 6) (1, 2, 6) А, и Во Ас и Во (1, 3, 5, 6) (1, 2, 4, 6) ') См. сноску ') на стр. 207, 203 Шаг 2. Определяем Оув.
Все куски совместимы с двумя гранями (случай 3). Выбираем, например, цепь (1, 3, 5) из куска Р~ и проводим ее в грань Вс. Эта грань в бр~ заменяется двумя гранями: В,— внутренней к (1, 3, 5, !) и Ву — внутренней к (1, 2, 6, 5, 3, 1) (рис. 157, б). Куски (г' относительно 6~~. Куски (з, 6) (1, 2, 4, 6) (3, 6) (1, 2, 6) Вв 12 А, н В, Шаг 3. Определяем Ов~.
Кусок Рг совместим лишь с одной гранью Вр (случай 2). Цепь (3, 6) должна быть помещена в грань Ву, которую она разобьет на две грани: Ва — внутреннюю к (3, 5, 6, 3) и В, — внутреннюю к (1, 2, 6, 3, 1) (рис. 15?, в). Куски 6 относительно 6ав1 Совместимые грани Вершины куска Контантные точки Кусок гг Р, Ао н В, (1, 2, 6) (1, 2, 4, 6) Шаг 4. Определяем гу(. Кусок Р~' совместим с двумя гранями Ар и В, (случай 3).
Возьмем, например, цепь (1, 4, 2) и поместим ее в грань Ар. Получаем две новые грани; А~ — внешнюю к (1, 4, 2, 6, 5, 1) и Ау — внутреннюю к (1, 4, 2, 1) (рис. 157,г). Куски О относительно 644: Совместимые грани Контактные точки Вершины куска Кусок гг/ Р, А, (4, 6) Шаг 5. Определяем Я. Кусок Рг ' совместим лишь с одной гранью А~ (случай 2). Помещаем единственную цепь (4, 6) в А, и получаем новые грани: А, — внешнюю к (1, 4, 6, 5, 1) и Ае— внутреннюю к (2, 4, 6, 2).
Таким образом, получаем плоское изображение графа су. 209 й 37. Подмножество сочленения Гтт l ! !С Рис !58. 6 =(Е, О). Предлагается найти наименьшее подмножество со членения А, которое разделяет подмножества В!» Е! и В,:» Ез из Е. Иначе говоря, рассматривая симметрический граф 6 = (Е, Г) без петель, соответствующий 6, отыскивают такое множество А (если оно существует), что а) Е, с: В„А() В!= 3; б) Езс Вм А() Вз= !о! в) А)) В!() Вз=Е, В!ДВз= Я; (37.1) г) ГВ,!') Вз= О, ГВз() В,= Я; д) ) А) минимально. Например, если Е, = (С, 6) и Е, = (В, Р, т(), то А = (А, О, Е) является минимальным подмножеством сочленения (рис. 158).
Для отыскания минимального подмножества сочленения, соответствующего двум заданным подмножествам, можно использовать метод'), предложенный Мальгранжем н использующий понятия полной подматрицы и основной подматрицы. Полная подматрица. Основная подматрица. Покрытие. Полной подматри!!ей булевой матрицы называется ее подматрица, все элементы которой равны 1. ~) См. сноску на стр. !88. 2!О Пусть задан связный граф 6 =(Е, О); непустое подмножество А называется подмножеством сочленения, если подграф, по. рожденный множеством Š— А, не связан.
В случае, когда подмножество А сводится к единственной вершине, ее называют точкой сочленения. Например, подмножество А = (А, О, Е) является подмножеством сочленения неориентированного графа, порожденного множеством Е=(А, В, С, О, Е, Е, 6, Н]. Минимальное подмножество сочленения. Рассмотрим два подмножества Е! и Ез множества Е, порождающего граф Основной *) подматрицей называется полная подматрица, не содержащаяся ни в какой другой полной подматрнце.
Например, на рис. 159 представлены все основные подматрицы матрицы []М]!. Покрытием булевой матрицы называют множество полных подматриц, покрывающее все единичные элементы этой матрицы. Например, (]]М,][, ]]М,]], ]]М4[[, ]]Мб]], ]]Мб]], ]]Мг][, ]]Ма]!)— покрытие матрицы ]! М ]! (рис. ! 59).
а Ь с г( е 1м1 ь а «1 ь а е ь 1 Л 1 1 1 Л )м,1 1мб1 1 ма 1 ь в а с в[1 ~Д 1мн1 О А 1 В~~ 1м41о1в[") Рис. 159. Используя указанные ниже правила, можно получить все основ. ные подматрицы. *) В оригинале «ргепиеге». (При»с перев.) '*) Вмрогнденнан матрица (см. [36]) считаетсн полной. (Лра.ч перев.) 211 Предварительно рассмотрим алгоритм для нахождения всех основных подматриц заданной булевой матрицы, Пусть 1 — множество строк, а 3 — множество столбцов матрицы ]]М[!. Каждая полная подматрица определяется парой (1, Зе) подмножеств, где 1рс1, вес д. Введем две операции Если полная "*) подматрица []М,]! определяется (1о ег), а [[Мн]! определяется (1,, Ян), то ]]М|]][][]Мт]! ]]М']! определяется парой (1,[]1,, ЛгпЛ), ]! М, ]! П ]! М, ]! = [! М" ]! определяется парой (1, Д 1, Лг [] Л ). (37.2) ))М,))=А( 1 ( 1 ! 1) 1 (, ))М,)(=В) 1 ~ 1 ), с( е Ь с )) М,)) = С Я 1 ) 1 ~, )) М,() = В ! 1 ( 1 ) 1 ~.
Шаг 2 (правило 11). Найдем объединения и пересечения: 1з()1з=(А, В), .1зП.)з=Я, 1! () 1з = (А С) Л! П Лз = (Ь, з(, е), (37 А) которые дают новую подматрицу Ь з( е А )) Мз)) = С Рассматривая получаем 1! Ц 1, = (А, О), Л! П Л4= (Ь !') (37.5) А )) Мз)) = В (37.6) 1з () 1з = (В С) 1з()1 = (В, В), )зП 1з= 0 Лз П 14 = (с) (37.7) приводят к с В )) Мз))= 0 1 1 (37.8) Наконец, 1з () 1„= (С, В),,1 П,), = (Ь] (37.9) 2!2 Правило 1. Удаляем любую подматрнцу ))Мз)), содержащуюся в подматрице )) М!)) иэ покрытия С. Правило 11. Добавляем к С подматрицы, получаемые применением вышеуказанных операций ко всем парам матриц ))Мз() н ))М!)), оставшимся в покрытии (если при этом получается матрица, уже содержащаяся в С, то она не добавляется).
П р и м е р (рис. 159). Найдем основные подматрицы матрицы )) М)), выбирая покрытие. Шаг 1, Ь д е а с дают ! ! с Ц Мв Ц О (370 О) Пересечения 1, П1~ —— 0 для всех 1 и /, и вторую операцию из (37.2) применять излишне. Шаг 3 (правило 1). Выпишем новое покрытие: ( Ц М, Ц, Ц Мд Ц, Ц М4 Ц, Ц М, Ц, Ц Мв Ц, Ц М, Ц, Ц Мв Ц ) ' (37.1!) Ц МвЦ удалена, так как содержится в Ц М,Ц. Шаг 4 (правило П). Проводим подробно все выкладки: 1,014= (А, С), Л,ПЛв=(Ь, 42, г): дает Ц МвЦ, 1,014=(А, О), Л,ПЛ,=(Ь, Ц): дает ЦМ,Ц, 14017=(А В О) Л~ПЛт=0~ (37. 12) 14 0 14 = (А С О) ~ Л4 П Лв = (Ь).
Получаем новую подматрицу А ! ! 1 ЦМ„Ц=С (37.!3) 14014= (А, С, О), 1401,= (А, В, С, О), 1401в= (А, С, О), 1,01,=(А, В, О), 1в01в — — (А С, О), 2!3 Далее, 1,01,=(А, В, С1, 1д014= (А, В, О), 1д01,= (В, О], 1д 0 1в = (В, С, О), 140 14= (А, С, О), 1Д1,= (А, О), 140 1~ = (В, О), 140 14= (С~ О) ЛдПЛ4=0 Л4ПЛ4=0, Л,ПЛ, (с): дает ЦМ,Ц, ЛдПЛв=0 Л4ПЛ =(Ь): лает ЦМ,Ц, л4Плв=(ь,7): дает Цм,Ц, Л4ПЛд=(с): дает ЦМ,Ц, Л,ПЛ,=(Ь): дает ЦМвЦ содержащуюся в Ц Мд1, ЛвПЛ,=(Ь): дает ЦМ„Ц, Л,ПЛ,=0, Л,ПЛ, (Ь): дает ЦМ,Ц, 1б П Л7 = 0 Л,ПЛ,=(Ь): дает ЦМ,Ц, Лв() Лв=(Ь, А г): дает 1)МВ11, содержащуюся в 11 М,)1, 14 () л7 (ь с ~) дает 11 м4 11 Ь Лв()ЛВ (Ь, ?) дает 0~ 1 ) 1~, содержащуюся в 11 М, 11, Ь с 17 П 1В (0) ~ Л7() Лв (Ь, с)1 дает 0~ ! ( 1 ), содержащуюся в 11 М,)1, Шаг 5 (правило 1). Выписываем новое покрытие: (1)М,)1, 1(М711> 1)М411, 1)М,)1, 1)М,)1, 1)М,)1, 1)М,(1); (3?.15) 11 Мв 11 удалена, так как содержится в 11 Мд 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
