В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 32
Текст из файла (страница 32)
На основании утверждения 40.5 граф Св — абстрактно двойственный кС. ч1 Оказывается, пе всякий граф пмоет абстрактно двойственный граф. Утверждение 40.12. Граф Кзз пе илчеет абстрактно двойственного графа. !э Доказательство проведем от противного. Допустим, что граф Кзз имеет двойственный граф С. Поскольку Кзз имеет лишь 4-циклы и б-циклы, то граф 6 не имеет разрезов с менее чем четырьмя ребрами. Поэтому ч)ело > ~ 4 для всякой верпчипы о ш '>тС. Л нз того, что граф Кз,з не имеет разрезов, состоящих из двух ребер, следует, что в графе С нет 2-циклов, т.
е. он пе содержит кратных ребер. Следовательно, !6! ~5. Суммируя все полученное и принимая во внимание лемму о рукопожатиях, выводим, что !Е6! ~ 10. Но !ЕС! = !ЕКз,з! = 9. Полученное противоречие доказывает утверждение 40.12. '1 Утверждение 40.13, Граф Кз не имеет абстрактно двойственного графа. чэ Допустим, что граф К> имеет двойственный граф С. Так как граф Кз пе имеет циклов длины один или два, то степень каждой вершины графа С пе менее 3. В то же время иэ того, что граф Кз имеет лппчь разрезы, состоящие пз 4 пли б ребер, следует, что все простые циклы графа С имеют четную длину, т.
е. С вЂ” двудольпый граф. Гели бы было ',6! -. б, то получилось бы !ЕС! ~ 9, по !ЕС! = !ЕКг! =10. Итак, !С! ~ 7. Поэтому граф С должен иметь по крайней мере 1/2Х7ХЗ)10 ребер. Однако это противоречит условию )ЕС! = 10. < 174 Теперь мы монсем доказать еще один критерий планарпости графов. Теорема 40.14 (Х. Уитни, 1932 г.). Граф нланарен тогда и только тогда, когди он засеет аоетрактно двойственный граф, > Необходимость установлена теоремой 40.11. Достаточность докажем, показав, что пеплапарный граф С пе имеет абстрактно двойственного.
Согласно теореме По~тратила — Иуратовского граф 6 содержит подграф 11, гомеоморфпый Кз з или Кз, Если бы граф С имел абстрактно двойственный граф, то по следствию 40.9 и подграф Н имел бы абстрактно двойственный граф. Е1о согласно следствию 40.10 зто означало бы, что граф Кз,з нли Кз должен был иметь абстрактно двойственный. Однако это противоречит утверясдениям 40.12 и 40.13. Поэтому граф С не имеет абстрактно двойственного графа. з Из теорем 40.14 и 40.7 и утверждения 40.6 получаем Следствпе 40.15. Следусосцие утвергкдессия гквивалентссьз: 1) граф С планарен; 2) матроид циклов М(С) кографичен; 3) лсатроид разрезов М*(С) графичен.
$41. Алгоритм укладки графа на плоскости Рассмотрепные в предыдущих параграфах критерии плапарпости таковы, что если дансе удалось установить плапарность графа, то нет информации о том, как строить его укладку на плоскости. В то ясе время при решении практических задач, о которых говорилось в начале этой главы, недостаточно знать, что граф планарен, а необходимо, как правило, построить его плоское изобрансепие.
Все это вызвало появление алгоритмов, которые пе только проверяют граф па плапарность, но и одновременно строят его плоскую укладку, если это возможно. Один из таких алгоритмов (алгоритм 7) рассмотрим в этом параграфе. Алгоритм 7 укладки графа 6 представляет собой процесс стоследовательпого присоединения к некоторому уложенному подграфу с графа б новой цепи, оба конца которой принадлежат с . Тем самым зта цепь разбивает одну из граней графа с7 па две. При этом в качестве пачалыгого плоского графа бс выбирается любой простой 175 цикл графа 6.
Процесс продолнсается до тех пор, пока пе будет построен плоский граф, нзоморфпый графу 6, или присоединение некоторой цепи окажотся невозможным. В последнем случае граф 6 пе является плапарным. Поскольку связпып граф плапарен тогда и только тогда, когда планарны все его бгсоки (теорема 37.8), а граф Кг планарен, то будем предполагать не теряя общности, что укладываемын граф 2-связеп. Вводом ряд определений. Пустс построена некоторая укладка подграфа 6 графа 6. Сегментом Я относительно 6 (слссогда просто сеглсектом) будем называть подграф графа 6 одного из следующих двух видов: 1) ребро е= иоснЕ6 такое, что еФЕ6, и, оси Ю; 2) связную компоненту графа 6 — 6, дополненную всеми ребрами графа 6, инцидептпыми вершинам взятой компоненты, и концами этих ребер.
Очевидно, что в случае, когда граф 6 плапарпый, всякий сегмент, как подграф графа 6, планарен, а в случае, когда 6 пе является плапарпым, сегмент может быть как планарпым, так и не плапарпым. Вершину о сегмента Я относительно 6 будем называть контактной, если оси 'т'6. Так как в графе 6 пет точек сочленения, то легко доказать, что в случае, когда граф 6 является 2-связным, каждый сегмент содержит пе менее двух контактных вершин. Па рис. 41.1 изображены граф 6, его улонсенный подграф 6 и все сегменты относительно 6.
Поптактпые вершины сегментов обведены кружками. Поскольку граф 6 плоский, то он разбивает плоскость на грани. Допустимой гранью для сегмента Я относительно 0 называется грань Г графа 6, содержащая все контактные вершины сегмента Я. Через Г(Я) будем обозначать множество допустимых граней для Я. Монсет оназаться, что Г (Я) = Ы. Простую цепь Ь сегмента Я, соединяющую дзе различные контактные вершины и пе содержащую других контактных вершин, назовем се-сгепью. Очевидно, что всякая сг-цепь, принадлежащая сегменту, может быть уложена в лсобую грань, допустимусо для этого сегмента.
Два сегмента Яс и Яг относительно 6 назовем конфликтующими, если 1) О = Г (Яс) П Г (Яг) еь 8, 2) существуют две сг-цепи Ь1 ~н Яь Хгя Яг, которые без пересечений нельзя уложить одновременно пи в какую грань Г~в о. В противном случае будем говорить, что сегменты не конфликтуют. 176 Для графа, изображенного на рис. 47.1, копфликтующими явля>отея, например, сегменты Я> и Ь2, Бз и Я4, Я2 И Яб. Вернемся к обсуждению алгоритма 7. Итак, на первом п>аге этого алгоритма уложим произвольный простой цикл графа С. Пусть, далее, С вЂ” построенная па предыдущем шаге укладка некоторого подграфа графа 1".
Для каждого Ы 11> 11 3 4 5 и г 1 г 5 н 1 2.- л 5 5 6 В 1 6 6 5, 5„5, 5е Рис. 41.1 сегмента относительно с" находим множество допустимых граней. Теперь могут представиться только следующие три случая. 1. Существует сегмент, для которого нет допустимой грани. Как мы покажем в дальнейшем, граф 6 в этом случае не планареп. 2. Для некоторого сегмента Я существует единственная допустимая грань Г. Тогда очередной шаг состоит в расположении любой а-цепи сегмента Я в грани Г.
При этом, как у>ко отмее>алось, бб-цепь разбивает грань Г на две грани. 3. Г1о) > 2 для всякого сегмента Я. Тогда появляется несколько вариантов продолжения построения укладки графа, поскольку любой сегмент можно размещать в любую допустимую для этого сегмента грань. Поэтому возникают опасения, что неудачный выбор сегмента и гра- 177 21 в. л, кмеличее и лв. ни может помешать процессу построения укладки на следующих шагах и плоская укладка планарпого графа пе будет построена. Зто могло бы привести пас к певорпому зак;почспшо о том, что плапарпый граф ношшпареп.
В дальпс3йпем мы покажом, что в этом случае для продолзкепия алгоритма 7 молспо выбирать и-цепь в любом сегменте и помещать ее в любую допустимую грань. Теперь формально опнптсм алгоритм 7, а затем займемся его обоснованием. Алгоритм 7. О. Выберем некоторый простой цикл С графа С и улонзизз его на плоскости; положим б = С. 1. Найдем грани графа с' и сегменты относительно б. Если множество сегментов пусто, то перейдем к и.
7. 2. Для каждого сегмента Б определим множество Г(Я). 3. Если существует сегмент Я, для которого Г(Я)= = И, то граф 6 пеплапареп. Нопец. Иначе перейдем к п. 4. 4. Если существует сегмент Я, для которого имеется единственная допустимая грань Г, то перейдем к п. 6. Иначе — к п. 5.
5. Длн некоторого согмопта Я (Г(Я)) 1) выбираем произвольную допустимую грань Г. 6. Поместим произвольную а-цепь Е ш Я в грань Г; заменим 0 па С 33 Ь и перейдем к п. 1. 7. Построена укладка С графа С на плоскости. Конец. Шагом алгоритма 7 будем считать присоединение к з' и-цепи х. Дальнейшее изложение посвящено обоснованию алгоритма 7.
Сначала докажем, что для планарпого графа алгоритм 7 строит плоскую укладку графа. Для этого нам понадобятся две леммы. Л е м м а 41.1. Если коку)ликтующие сегменты Я~ и Бз относительно С таковы, зто 3Г(Я~) 3 ) 2, 3Г(Яз) 3 ) 2, то Г(Я~)= Г(Яз), 3Г(5~) 3 = 2. 3> Сначала доканзем, что Г(Ь|) = Г(Ьз). Допустим противное. Тогда по условию леммы существуют три различных грани: Г~ыГ(Я~), Гз~вГ(Яз), Гз~нО=Г(Я,)6 П Г(Яз) Ф 8. Поэтому всякая зс-цепь Е~ — Я~ укладывается в Гь а всякая а-цепь Ез снЯз укладывается в Гз. Но ато значит, что всякая пара и-цепей Е~ — Яь Ез — Яз одновременно укладывается впе Гз, Тогда опи укладываются и внутри грани Гз.
Но это протпворе шт тому, что Б| и Яз — конфликтующие сегменты. 178 Итак, Г(Я~) = Г(Яг) = О. От противного легко показать, что ~0) = 2. Пусть ~0~ ~ 3. Тогда существует по крайней мерв три различных грани Гн Гм Гз~п О. Поэтому, повторяя предыдущие рассуждения,получаем противоречие. 7 Построим вспомогательный граф Я(6) по следующему правилу: каждому сегменту относительно С поставим в соответствие вершину графа Я(С), причем будем считать, что две вершины смежны тогда н только тогда, когда соответствующие л им сегменты конфликтующие. На рис. 41.2 изображен вспомогательный граф Я(С), соответству1ощий сегментам ранее рассмотренного л в графа 6 (рис.
41.1) относительно С. рис. 402 Прп этом вершины графа Я(С) обозначены так же, как и соответствующие пм сегменты. Частичной укладкой планарпого графа С называется такой граф, которьш можно получить из какой-либо укладки графа С на плоскости путем удаления некоторых ребер и вершин. Тем самым во всякую частичную укладку планарпого графа С монзно улонситт оставшуюся часть, т. е. недостающие вершины и ребра графа С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
