В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 29
Текст из файла (страница 29)
> Так как каждая грань графа ограпичена т-циклом, то кая'дое ребро принадлежит ровно двум граням, т. е. (т = 2т. Подставляя сюда / из формулы Эйлера, получаем искомый результат. Э Очевидно, что не всегда граница грани плоского графа является простым циклом (см., например, грань 2 на рпс. 37 1) . Однако для 2-связных графов это так.
А именно, верна следующая Т е о р е м а 37.7. Плоский граф двусвяген тогда и только тогда, когда границей всякой его грани является простой цикл. 156 > Необходимость. Доказательство проведем от противного. Пусть существует плоский 2-связный граф. С, в котором некоторая грань ограничена не простым циклом. Поскольку граф 6 содержит хотя бы один простой цикл, то существует такой максимальный 2-связный подграф Н графа 6, что граница каждой его ьграпи является простым циклом.
При этом Нта 6. По лемме 34.7 в С существует Н-цепь. Эта простая цепь должна разбивать некоторую грань плоского графа Н на две грани. Очевидно, что каждая из этих граней ограничена простым циклом. Однако это противоречит выбору подграфа Н. Д о с т а т о ч н о с т ь. Допустим, что плоский граф, каждая грань которого ограничена простым циклом, не является 2-связным. Тогда граф имеет точку сочленения. Но это значит, что существует грапь, ограниченная не простым циклом. 0 Теорема 37.8. Связный граф планарен тогда и только тоеда, когда каждый его блок планарен.
> Необходимость очевидна. Достаточность докажем индукцией по числу блоков к. Если й 1, то утверждение очевидно. Пусть граф С состоит из й ) 1 планарных блоков. Согласно утверждению 34.6 существует хотя бы один концевой блок В, имеющий точку сочленения о. Поскольку подграф 6— — ( — о) содержит й — 1 блоков, то по предположению индукции он планарен.
Следовательно, существует такая его плоская укладка, что вершина о находится на впешней грани, Точно так же граф В имеет плоскую укладку с вершиной о на внешней граня. Поэтому объединение (6 — ( — о)) 0 В, изоморфное графу С, имеет плоскую укладку па основании свойства 2. 0 Из теоремы 37.8 следует, в частности, что для выяснения вопросов, связанных с планарностью, достаточно рассматривать лишь 2-связные графы. 4 38. Плоские триангуляции В этом параграфе изучается особый класс графов— плоские триангуляции. Такие графы интересны тем, что всякий планарный граф порядка и изоморфен подграфу некоторой плоской триангуляции с и вершинами. Грань плоского графа, ограниченную треугольником (З-циклом), также будем называть треугольником, Связный плоский граф называется плоской триангуляцией, если каждая его грань (в том числе и внешняя) 157 является треугольником. Тем самым, плоская триангуляция содержит не менее трех вершин.
Максимальным плоским 1планарньм) графом называется и-вершинный 1п ~ 3) граф, который перестает быть плоским (планарным) при добавлении любого ребра. На рис. 381 приведены максимальный и не макспмальйый плоские графы. Разумеется, что от добавления Ряс. 38.1 кратных ребер планарность графа не нарушается. Однако мы условились рассматривать лишь простые графы. Теорема 38,1, Граф является максимальным плоским графом тогда и только тогда, когда он представляет собой плоскую триангуляцию, > Необходимость.
Пусть С вЂ” максимальный плоский граф. Прежде всего заметим, что граф С является 2-связным. Поэтому по теореме 37.7 всякая грань Г такого графа, не являющаяся треугольником, ограничена простым циклом 1оь ои ом он ..., о~), содержащим пе менее четырех вершин. Так как С вЂ” плоский граф, то он не может одновременно содержать ребра о1ог и ого4 (ведь зти ребра должны быть изображены вне грани Г, см.
рис. 38.2). Предположим, Г например, что щог Ф КС. Тогда после добавления ребра огиз в грань Г граф С остается плоским, что "г противоречит его максимальности 1рис. 38.2). Достаточность. Пусть С— Рпс. 88.8 плоская триангуляция. Так как С— связный граф, то очевидно, что всякое ребро, после добавления которого граф С остается плоским, должно разбивать некоторую грань графа С на две грани.
Однако в плоской триангуляции всякая грань— треугольник и, следовательно, разбить ее на две путем добавления ребра невозможно. < Теорема 38.1 дает следующее важное О л е д с т в и е 38.2, Всякий плоский граф является остовным подграфом некоторой плоской триангуляции. 158 Иными словами, каждый плоский граф можно дополнить ребрами так, что он станет плоской триангуляцией. Из теоремы 38.1 и следствия 37.6 (при г = 3) вытекает Следствие 38.3. Для всякого максимального планарного (и, пг)-графа пг = Зп — 6.
Утверждение 38.4. Если ч ело вершин плоской триангуляции не меньше четырех, то степень каждой вершины не менее трех. с Возьмем произвольную вершину ш Пусть ш— смежная с ней вершина. Ребро ош .принадлежит двум граням — треугольникам (о, ш, и|) и (о, ш, из), причем и| ть им так как число вершин графа не меньше четырех. Таким образом, о смежна по крайней мере с тремя вершинами ш, иь их < У тв е р ж де н не 38.5. Всякий планарный граф с и ~ 4 вершинами имеет по крайней мере 4 вершины со степенями, не превосходящими 5. ~> Без потери общности будем считать граф С плоским.
Добавляя ребра, сделаем граф С максимальным плоским графом С, каждая вершина которого в силу утверждения 38.4 имеет степень не меньше 3. Поэтому, принимая во внимание следствие 38.3 и лемму о рукопожатиях (утверждение 5.1), получаем 2(Зп — 6) = 2т = Зп, + 4п, + 5п, + ... ~) ) )3(п, + и, + пв) + 6 лг пз. 1лв где и — число вершин графа С', ш — число его ребер, а и, — число вершин степени ~ в этом графе. Отсюда, учитыкая, что и = .„ и,, легко получаем з>з пз + пз + пз ) 4, т. е. в графе С', а тем более в графе С, имеется по крайней мере 4 вершины со степенями, не превышающими 5. <.
4 39. Критерии планарности Имеется несколько критериев планарности графа. Мы рассмотрим характеризации плапарности графов, данные Л. С. Понтрягиным, К. Куратовским, К. Вагнером и С. Маклейном. Следует заметить, что практическая проверка условий, которыми ниже характеризуются планарные графы, не всегда является простой. Однако разрабо- 159 таны эффективные алгоритмы, позволяющие длн любого заданного графа или найти его плоскую укладку, илн установить, что граф непланарен. Один из таких алгоритмов приведен в 9 41. Для того чтобы сформулировать широко известный критерий Понтрягина — Куратовского, введем понятие гомеоморфизма графов.
Нам понадобится операция подразбиения ребра е= аЬ графа. Она состоит в следующем; из графа удаляется ребро е н добавляются два новых ребра е< = ао, ез = оЬ, где о — новая вершина. Два графа называются го<кеоз<орфными, если оба онп могут быть получены пз одного и того же графа подразбиением его ребер. Ркс.
39.1 На рнс. 39.1 изображены гомео- морфяые графы. Если граф планарный, то очевидно, что любой граф, гомеоморфпый ему, такжо является плапарным. Исторически первым критерием планарностн графов является следующий критерий, доказанный Л. С. Понтрягиным (1927 г.) н К. Куратовскнм (1930 г.) независимо друг от друга. Теорема Понтрягина — Кур ат овско го. Граф планарен тогда и только тогда, когда он не содержит подграфое, гол<еол<орф<<ых Кз или Кз,з. Тем самым можно утверждать, что многие графы пеплапарны и независимо от того, как окк изображены па плоскости, некоторые нх ребра обязательно пересекаются.
Необходимость условий теоремы уже доказана, поскольку доказана попланарность графов Кз п Кз з ~следствия 37.4 и 37.5) . Для доказательства достаточности требуются новые понятия п теоремы. Попутно будет доказано, что всякий планарный граф можно улоя<нть па плоскости так, что каждое его ребро будет отрезком прямой. Ранее было показано (сз<. теорему 37.8), что граф планареп тогда и только тогда, когда планарпы его двусвязные компоненты.
Оказывается, будет достаточно, если мы, касаясь вопросов, связанных с плоской укладкой 2-связного графа С, рассмотрим лишь 3-связные графы, полученные из С специальным образом. Пусть к(С) = 2, ~С~ ~ 4. Из определения двусвязности вытекает существование вершки а, Ь аа ИС, таких что 160 граф Н = С вЂ” а — Ь пе связин. Рассмотрнм следусощее преобразование А графа 6. Пусть Нь Нг, ..., Н,— связные компоненты графа Н. Для каждой такой компоненты Н, рассмотрим граф Сь порождеиньш и С мпогссеством УГГ, 0 а 0 Ъ и дополненный ребром аЬ, если аЬ Ф ФЕС.
В результате преобразования А получаем семейство графов 6с, Сг, ..., С„причем ~Сс! > 3, х(6,)~ 2 (с 1, т) (рис. 39.2). Теорема 39.1. Пусть х(6)=2, ~С~ )4. Граф 6 планарен тогда и только тогда, когда плассарен каждый граф Сс, полученный в результате преобразования А. > Необходимость. Если 6 — планариый граф, то любой его подграф, в том числе Сс = 6(УСс), плапарен. Если Сс содержит ребро аЬ, то Сс = Сь В противном а ь ь; Рис. 39.2 случае по лемме 34.7 в 6 существует Сснцепь 1,, соединяющая вершины а и Ь. Подграф Сс 0 П планареп, по оп гомеоморфен графу Сс. Достаточность.
Пусть все графы 6с, Сг, ..., С„ плаиарпы. Пусть Рс, Рг, ..., Р, — соответствующие нм плоские укладки, у которых ребро аЬ лежит па внешней грани. Будем последовательно объединять графы Рь Рг, ..., Р,. Сначала построим такую укладку объединения Рс г графов Рс и Рг, в которых имеется общее ребро аЬ, что граф Рг лежит иа внешней грани графа Рс. Затем изобразим Рс г так, чтобы ребро аЬ оказалось иа внешней грани, и используя прежний прием, построим объединение Рслз графов Рс г и Рг (рис. 39.3) п т. д., пока пе объединим все графы Рь Рг, ..., Р,. Полученный в резуль- 11 в и кмелняег и лг.
161 тате плоский граф Р~ з,, может отличаться от исходного графа С только ребром аЬ. '3 С л е д от в не 39.2. Всякая плоская триангуляуия, имеющая более трех вершил, 3-связка. с' Доказательство проведем от противного. Предположим, что С вЂ” плоская триангуляция н х(С)=2. Пусть ~сг зсаз Рис. 39.3 а и Ь вЂ” такие вершины, что граф С вЂ” а — Ь пе связеп. Совершив преобразование з1 графа С, получим, согласно теореме 39.1, планарпые графы Сп Сз, ..., С,. Пусть Рь Рз, ..., Р, — соответствующие им плоскпе укладки, в которых ребро аЬ лежит на внешней грани. Объединим их последовательно, как это делалось прл доказательстве теоремы 39.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
