В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 30
Текст из файла (страница 30)
Прн этом па последнем шаге, объединив графы Рьг, ...,,-1 и Р„получаем граф в Р1 з „, внешняя грань которого со- держит (поскольку ~Р,~ ~ 3) нес смежные вершины с ш Ь'Р, з, 1 и б~ 7Р„с,бФ(а, Ь) (ряс. 39.4), т. е. Р1з, „а, следовательно, и 6 не является плоской триангуляцис ей.
'3 Вернемся к графу С, для котороРис. 39А го х(С)=2, ~С~ >4. Если среди графов Сп Сз, ..., С„, полученных с помощью преобразования Л, есть граф С„длн которого х(6;) = 2, ~6;~ ~ 4,то к нему вновь можно применить преобразование А и т. д. до тех пор,пока это преобразование будет возможным. Поэтому справедливо Утверяздепие 39.3. Пусть х(6)= 2, !61 > 4. Тогда в результате лгногократкого прилсенения преобразования А к графу С будет получено такое семейство графов 133 С„С,..., Св, что для любого с = 1,,Ч либо С;=Кз, либо х(6',)) 3. Поскольку Кз — плапарпый граф, то пз теоремы 39.1 и утверждения 39.3 следует, что вопрос о планарности 2-связных графов свелся к вопросу о плапарности 3-связных графов.
Прежде чем формулпровать критерий плапарпостп 3-сзязпых графов, докажем лемму. Лемма 39.4, Пусть н(6)=2, сС~ ~4. Пусть, далее, С„Сг,..., ф— графы, получессссьсе в результате преобразования А, и аб — ребро этих графов, ссе принадлежащее графу 6. Тогда для лсобого с=1, т существует Сс-ссепь графа 6, соединшощая вершины а и Ь, с. Поскольку н(6»)> 2 для любого 1с = 1, с, то по теореме 34.1 ребро аб припадложит некоторому простому циклу графа С,.
Прп любом к' ть с часть этого цикла, по содержащая ребра ау, и служит искомой С,-цепью. 0 Плоский граф назовем выпуклылс прялсолинейссьсзс графом, если границей каждой его грани является выпуклый многоугольник. Напомпим, что многоугольник называется выпуклым, если оп целиком расположен по одну сторопу от любой прямой, на которой лежат сторона мпогоуголышка, и никакие две его стороны пе лескат па одной прямой.
Теорема 39.5. Ясли граф З-связссый, то он либо изозсорфен вьстсуклоссу пр зсолиссейссозсу графу, либо содержит подграф, голсеожорфный Кс или Кзз. 1> Доказательство проведем ипдукцпей по числу и вершин графа. Для и 4 утверясдепие теоремы верно, так как граф Кс изоморфеп выпуклому прямолинейному графу (см. рис. 36.1, б), а других 3-связпых четырехвершпяпых графов не существует. Пусть С вЂ” 3-связный граф, ~ 6 ~ и ~ 5 и для всех графов с мепьппсм числом вершин теорема верна. Согласно следствию 34.9 в графе С есть такое ребро х ио, что граф С„, получегшый из С в результате стягивания этого ребра, является 3-связным.
Пусть С„содержит подграф Н, гомеоморфпый Кз (ркс. 39.5, а). Покажем, что тогда граф 6 содержит подграф, гомооморфпый Кз плп Кзз. Это очевидно в случае, ссогда 1Х ке содержит вершины х, полученной в результате стягпвашся ребра х, илп содержит ее в качество вершины степени 2. Пусть теперь степень капсдой из вершин а, Ь, с, Ы, х в Н равна четырем. Тогда вершппа х соединена простыми пепересекаю- И» сбЗ щнмися цепями Гь Гг, Гз, Х4 с вершипамн а, Ь, с, с( соответственно.
В графо С этим цепям соответствуют непересекающиеся простые цепи 1ь 1г, 1з, 1е соединяющие каждую из вершин а, Ь, с, и( с одпон из вершин и или и. Если одна из этих вершки, например и, принадлежит трем или четырем цепям, то в С существует подграф, гомеоморфпый Кз (рис. 39.5, б). А если каждая из с ь ь с п ь с с а с Рис. 39.5 вершин и и и принадлежит ровно двум цепям, то в С существует подграф, гомооморфпый Кзз (рис.
39.5, в, з). Апалогпчно можно показать, что если С„содержит подграф, гомеоморфпый Кзз, то и С содержит подграф, гомеоморфный Кз,з. Пусть теперь в С„нет подграфов, гомеоморфных графам Кз или Кз 3 ° По индуктивному предположению существует выпуклый прямолинейный граф С„, изоморфпый графу С„. Тогда ф— х — 2-связпыйг плоский граф, каггсдая грань которого, по теореме 37.7, ограничена простым циклом. Как обычно, через Ага(о) обозначим окружение вершипы о в графе С. Пусть С вЂ” простой цикл, ограничивающий грань графа ф— У, которая содержит Ас~ (х).
164 Веригины из 7Р,(н)~и делят цикл С па простые цепи Ео =(ан ..., аз), Ц =(ам ..., аз), ..., Ед =(а„..., а~). (1) Далее рассмотрим отдельно два случая. Случай 1. Все вершины нз Хе(и)Ъ принадлежат одной нз цепей (1). Тогда, удалив из 6„все ребра вида (х, Ь), где Ь Ф а; (1= 1, х), получим граф 6', изоморфпыи графу 6 — и.
Ребрами графа 6' являются отрезки, и все его грани, кроме, возможно, грани, содержащей вершины из У,(и), будут выпуклыми многоугольниками. Пусть вершина х пр~гпадлежит внутренней грани графа 6„. Очевидно, что всякий выпуклый многоугольник обладает следующим свойством: для любой его вершины а Ь г Зз зз Рвс. 39.6 существует такая ее окрестность, в которой можно поромощать эту воршппу (прп неподвижных остальпьзх), не нарушая выпуклости многоугольнтпза. Поэтому в графе 6„сугцествует такая окрестзюсть 0(х) точки х, что прн перемещении х в 0(х) будет сохраняться выпуклость всех многоугольников, находящихся впутри цикла С. Будем считать, что вершины из У,(и) ~и находятся па цепи Ц и разбивают ее па части: (ан ..., Ь~), (Ьн ... ..., Ьз), ..., (Ь|-и ..., Ь,), (Ь„..., а,).
Обозначим через Т точки плоскости, лежащие внутри кривой (цикла) (х, Ьн..., Ьм ..., Ьь х). Из определения выпуклого многоугольника следует, что, поместив вершину и в любую точку области 0(х) й Т и соединив и со всеми верпшиамп нз Ж,(и) (считая х = о), получим выпуклый прямолинейный граф, изоморфнын графу 6 (рпс. Зэ'.6). Подобным образом поступаем н тогда, когда воршина х принадлежит внешней грани графа 6. (Е1а рнс. 33.7 а, б 165 изобран<сп случай, когда вершипа и припадлеясит впутрскпей грани графа 6', а па рис.
39.7 е, г — впсшпей.) С л у чай 2. Не существует цспп (1), содержащей все вершины из множества Ка(и) ~и. В этой ситуации а а, г ег Лг Ряс. 39.7 мпожесгво всех ребер, ппцпдептных и п ь', польза изобразить без пересечений. Б самом деле, если ЛХ = ~ ()Уе(и) ~о) П(Хте(е) ~и) ~ ~ 3, т. е. число вершин цикла С, смежных и с и, и с о, не меньше трех, то в 6 существует подграф, гомеоморфпый графу Кг (рис. 39.8).
Если пге ЛХ( 2, то в 6 есть подграф, гомеоморфпый графу Кг,г. На рпс. 39.9 — 39.11 изображепы случаи, когда ЛХ = 2, 1, 0 соответственно.< Следствие 396 (теорема Поп тря гик а — Куратовского). Граф планареи тогда и только тогда, когда оп пе содержит подграфое, гомеоморфиых графам К5 или ХХЗ 3. С. Осталось доказать достато шасть условий теоремьь Пусть в графе 6 пот подграфов, гомсоморфпых Кг илп ЕХгг.
Гслп 6 — 3-связпый граф, то по теореме 39.5 оп плапареп. 166 Пусть к(6)= 2, )6) ~ 5. Далее доказательство проведем от противного. Предположим, что граф С пе плапарпый. Тогда в результате многократного применения к нему преобразования Л (см. утверждение 30.3) получим семейство графов Сп Сз, ..., Сю среди которых согласно теореме 39.1 имеется 3-связпыи граф С„пе являющийся планарпым.
В силу теоремы 39.5 в 6; есть подграф К, гомеоморфпый Кз или Кз з. Если все ребра графа К принадлежат С, то К вЂ” подграф графа 6, т. е. получено противоречие. Если же некоторое ребро аЬ~ЕК пе входит Рпс. 39.12 в С, то по лемме 30.4 существует Ссцепь графа 6, соединяющая вершины а и Ь. Нетрудно показать, что 6;-цепи, соответствующие разли'шым таким ребрам, пе имезот общих вершин, кроме, возможно, концевых. Заменив каждое такое ребро соответствующей С,-цепью, получим подграф графа 6, гомсоморфпый графу К. Вновь имеем противоречие.
< В качестве иллюстрации рассмотрим граф Петерсена. Он содернгит подграф, гомеоморфпый графу Кз,з(рис. 39Л2, где (а„аз, аз) и (Ьп Ьз, Ьз) — доли). Следовательно, этот граф не является планарпым. Следствие 39.7 (К. Вагнер, 1936 г.). Для любого планарного графа существует плоская укладка, в которой все ребра изображены в виде отрезков прямых линий. > Пусть 6 — связный плапарпый граф, имеющий пе менее чотырох вершин. На основании следствия 38.2 граф 6 является остовным подграфом плоской триангуляции Т, которая согласно следствию 30.2 есть 3-связный граф. Поэтому в силу теоремы 30.5 сущоствуст прямолинейпьш граф 7, пзоморфпый графу Т. Очсшздпо, что исходный граф 6 получается из Т путем удаления раисе добавленных к 6 ребер. < 168 Помимо критерия Понтрягина — Куратовского есть и другие критерии планарности графа.
11рнведем некоторые нз пил без доказательств. Теорема 39.8 (К. Пагпер, 1937 г.). Граф планарен тогда и только тогда, когда в нем пет под«рафов, стягиваемых к графам Кз или Кз,з. Поскольку граф Петерсена очевидным образом стягивается к Кз (для этого ну»кпо стянуть пять ребер, соединязощил вершины внутреннего и внешнего циклов), то пепланарпость графа Петерсена с помощью критерия Вагнера доказывается совсем просто.
Отметим здесь, что стягивая любое ребро планарпого графа, получаем вновь плапарпый граф. Очевидно, что все ацикличоские графы плапарны. Поэтому вполне естественна формулировка критерия планарности, исключающая этот тривиальный случай. Таким критерием является следующая Т е о р е и а 39.9 (С. Ыаклейп, 1937 г.) . Граф планарен тогда и только тогда, когда в каждом его петривиальном блоке есть такой базис циклов Сн Сз, ..., С, и такой один дополнительный цикл Сг, что любое ребро блока принадлеисит ровно двум иг этих й+ 1 циклов. 5 40.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
