Теорема Понтрягина — Куратовского

Граф планарен тогда и только тогда, когда он не содер­жит подграфов, гомеоморфных К₅ или К_3,3.

Тем самым можно утверждать, что многие графы непланарны и независимо от того, как они изображены на плоскости, некоторые их ребра обязательно пересекаются.

Необходимость условий теоремы уже доказана, по­скольку доказана непланарность графов К₅ и Кз,з (след­ствия 37.4 и 37.5). Для доказательства достаточности требуются новые понятия и теоремы. Попутно будет до­казано, что всякий планарный граф можно уложить на плоскости так, что каждое его ребро будет отрезком прямой.

Ранее было показано (см. теорему 37.8), что граф планарен тогда и только тогда, когда планарны его двусвязные компоненты. Оказывается, будет достаточно, ес­ли мы, касаясь вопросов, связанных с плоской укладкой 2-связного графа G, рассмотрим лишь 3-связные графы, полученные из G специальным образом.

Пусть x(G) = 2|G.| ³ 4. Из определения двусвязности вытекает существование вершин а, b Î VG, таких что граф Н = G — а — b не связен. Рассмотрим следующее преобразование А графа G. Пусть h₁, h₂,..., H_r — связные компоненты графа Н. Для каждой такой компо­ненты Hi рассмотрим граф Gi, порожденный в G мно­жеством V U Hi, a Ub и дополненный ребром ab, если аb Ï EG. В результате преобразования А получаем семей­ство графов g₁, g₂,..., G_r, причем |Gi| ³ 3, х(Gi) ³ 2 (i = l, r) (рис. 39.2).

Теорема 39.1. Пусть х(G) = 2, |G| ³ 4. Граф G планарен тогда и только тогда, когда планарен каждый граф Gi, полученный в результате преобразования А.

Необходимость. Если G — планарный граф, то любой его подграф, в том числе G₀i = G(VGi), плана­рен. Если Gi содержит ребро аb, то Gi = G_0i. В противном

случае по лемме 34.7 в G существуетG₀i-цепь L, соединя­ющая вершины а и b. Подграф Gi₀ U L планарен, но он гомеоморфен графу G_i.

Достаточность. Пусть все графы g₁, G₂,..., G_r планарны. Пусть Р₁, Р₂,..., Р_r— соответствующие им плоские укладки, у которых ребро ab лежит на внешней грани. Будем последовательно объединять графы Р₁, p₂,..., Рr. Сначала построим такую укладку объедине­ния Р_1,2 графов Р₁ и P₂, в которых имеется общее ребро ab, что граф Р₂ лежит на внешней грани графа Р₁. Затем изобразим P_1,2 так, чтобы ребро ab оказалось на внешней грани, и используя прежний прием, построим объедине­ние P_1,.2,3 графов P_1,2и P_з (рис. 39.3) и т. д., пока не объ­единим все графы p₁, Р₂,..., Р_г. Полученный в результат - не плоский граф p_{1,2 …….r} может отличаться от исходного графа G только ребром аb.

Следствие 39.2. Всякая плоская триангуляция, имеющая более трех вершин, 3-связна.

Доказательство проведем от противного. Предположим, что G — плоская триангуляция и x(G)=2. Пусть а

и b —- такие вершины, что граф G — а — b не связен. Cовершив преобразование А графа G, получим, согласно Теореме 39.1, планарные графы G ₁, G ₂,..., G_r. Пусть p₁, p₂,..., р_r — соответствующие им плоские укладки, в которых ребро аb лежит на внешней грани. Объединим их последовательно, как это делалось при доказательстве теоремы 39.1. При этом на последнемшаге,объединив

графы PP_1,2 ….,_r-1 и Рr, получаем граф P_1,2,..., r, внешняя грань которого со­держит (поскольку Pi ³ 3) несмежные вершины с Î VP_{l, 2.... r}__t и d Î VPr, c,d Ï {a, b} (рис. 39.4), т. е. P_{1,2………r,} а, следовательно, и G не является плоской триангуляци­ей. Вернемся к графу G, для которо­го x(G)= 2, |G|>4. Если среди графов g₁, g₂,..., Gr полученных помощью преобразования А, есть граф Gi, для которого (Gi)= 2, |Gi| ³ 4,то к нему вновь можно применить преoбразование G и

т. д. до тех пор, пока это преобразование будет возможным. Поэтому справедливо

Утверждение 39.3. Пусть x(G)=2, |G| ³ 4. Тогда в результате многократного применения преобразова ния А к графу G будет получено такое семейство графов G_i G₂,.. …G_R,что для любого i = 1, R либо Gi=K₃, либо х (G_i) ³ 3.

Поскольку Кз — планарный граф, то из теоремы 39.1 и утверждения 39.3 следует, что вопрос о планарности 2-связных графов свелся к вопросу о планарности 3-связных графов.

Прежде чем формулировать критерий планарности 3-связных графов, докажем лемму.

Лемма39.4.

Пусть x(G)= 2, |G| ³ 4. Пусть, да­лее, g₁, g₂,..., G_r — графы, полученные в результате пре­-
образования А,и Аb — ребро этих графов, не принадлежащее графу G. Тогда для любого i = 1, r существует Сi -цепь графа G, соединяющая вершины а и b.

Поскольку x(G_k) ³ 2 для любого k = 1, r, то по теореме 34.1 ребро аb принадлежит некоторому простому циклу графа G_k. При любом k ¹ i часть этого цикла, не содержащая ребра ab, и служит искомойG_i,-цепью.

Плоский граф назовем выпуклым прямолинейным графом, если границей каждой его грани является выпуклый многоугольник. Напомним, что многоугольник называет­ся выпуклым, если он целиком расположен по одну сто­рону от любой прямой, на которой лежит сторона много­угольника, и никакие две его стороны не лежат на одной прямой.

Теорема 39.5. Если граф 3-связный, то он либо изоморфен выпуклому прямолинейному графу, либо со­держит подграф, гомеоморфный К₅ или К_3,3

Доказательство проведем индукцией по числу n вершин графа. Для n = 4 утверждение теоремы верно, так как граф К₄ изоморфен выпуклому прямолинейному графу (см. рис. 36.1, б), а других 3-связных четырех вершинных графов не существует.

Пусть G — 3-связный граф, |G|=n ³ 5 и для всех графов с меньшим числом вершин теорема верна. Соглас­но следствию 34.9 в графе G есть такое ребро x = uv, что граф G_x, полученный из G в результате стягивания этого ребра, является 3-связным. Пусть G_x содержит под­граф Н, гомеоморфный K₅ (рис. 39.5, а). Покажем, что тогда граф G содержит подграф, гомеоморфный К₅ или Kз,з. Это очевидно в случае, когда Н не содержит верши­ны x₀, полученной в результате стягивания ребра х, или содержит ее в качестве вершины степени 2. Пусть теперь степень каждой из вершин а, b, с, d, х₀ в Н равна четы­рем. Тогда вершина х₀ соединена простыми непересекающимися цепями L₁, L₂,.L₃, L₄ с вершинами а, b, с, d cоответственно. В графе G этим цепям соответствуют пе­ресекающиеся простые цепи L₁, L₂,.L₃, L₄, соединяющие каждую из вершин а, b, с, d с одной из вершин и и v. Если одна из этих вершин, например и, принадлежит трем или четырем цепям, то в G существует подграф, гомеоморфный К₅ (рис. 39.5, б). А если каждая из

вершин u и v принадлежит ровно двум цепям, то в G существует подграф, гомеоморфный Кз,з (рис. 39.5, в, г).

Аналогично можно показать, что если G_x содержит подграф, гомеоморфный Кз.з, то и G содержит подграф, гомеоморфный Кз,з.

Пусть теперь в G_x нет подграфов, гомеоморфных графы К₅ или.Кз.з. По индуктивному предположению существует выпуклый прямолинейный граф G_0х, изоморфный графу G_x. Тогда G_0x—x₀ — 2-связный плоский граф, каждая грань которого, по теореме 37.7, ограничена простым циклом.

Как обычно, через N_G(v) обозначим окружение вершины v в графе G. Пусть С — простой цикл, ограничивающий грань графа G_0х — х₀, которая содержит N_G0x(х₀). Вершины из n_g(v)\u делят цикл С на простые цепи

L₁ =(a₁..., a₂), L₂ =(a₂,..., а₃),..., L_k = (a_k,..., a₁ ). (1)

Далее рассмотрим отдельно два случая.

Случай 1. Все вершины из N_G(u)\v принадлежат одной из цепей (1). Тогда, удалив из G_0x все ребра вида (x₀, b), где b ¹ a_i (i = 1, k), получим граф G', изоморф­ный графу G — u. Ребрами графа G' являются отрезки, и все его грани, кроме, возможно, грани, содержащей вершины из N_G(u), будут выпуклыми многоугольниками.

Пусть вершина х₀ принадлежит внутренней грани гра­фа G_0x.

Очевидно, что всякий выпуклый многоугольник обладает следующим свойством: для любой его вершины существует такая ее окрестность, в которой можно пере­мещать эту вершину (при неподвижных остальных), не нарушая выпуклости многоугольника. Поэтому в графе G_0х существует такая окрестность 0(х₀) точки х₀, что при перемещении х₀ в 0(х₀) будет сохраняться выпуклость всех многоугольников, находящихся внутри цикла С.

Будем считать, что вершины из N_G(u)\v находятся па цепи L_k и разбивают ее на части: (а₁,..., b₁), (b₁,......, b₂),..., (b_l-i,..., b_l), (b_l,,..., a_k). Обозначим через Т точки плоскости, лежащие внутри кривой (цикла) (х₀, b₁,..., b₂,..., b_l х₀). Из определения выпуклого многоугольника следует, что, поместив вершину и в лю­бую точку области О (х₀) объединяя с Т и соединив и со всеми вер­шинами из N_G(u) (считая x₀ =v), получим выпуклый прямолинейный граф, изоморфный графу G (рис. 39.6). Подобным образом поступаем и тогда, когда вершина х₀ принадлежит внешней грани графа G_0x. (На рис. 39.7 а, б изображен случай, когда вершина и принадлежит внут­ренней грани графа G', а на рис. 39.7 в, г — внешней.) Случай 2. Не существует цепи (1), содержащей все вершины из множества N_G(u)\v. В этой ситуации

множество всех ребер, инцидентных и и v, нельзя изобра­зить без пересечений. В самом деле, если

М= \ (N_G(u)\v) Ç (N_G(v)\u)\ ³ 3,

т. е. число вершин цикла С, смежных и с u, и с v, не меньше трех, то в G существует подграф, гомеоморфный графу К₅ (рис. 39.8). Если же М £ 2, то в G есть подграф, гомеоморфный графу Кз,з. На рис.39.9—39.11 изображены случаи, ког­да М = 2, 1, 0 соответственно

Следствие 39.6 (теорема Понтрягина — Куратовского). Граф планарен тогда и

только тогда, когда он не содержит подграфов, гомеоморфных графам К₅ или Кз,з.

Осталось доказать достаточность условий теоремы.

Пусть в графе G нет подграфов, гомеоморфных К₅ или Кз,з- если G — 3-связный граф, то по теореме 39.5 он планарен.

Пусть x (G) =2, |G| ³ 5. Далее доказательство проведём от противного. Предположим, что граф G не планарный. Тогда в результате многократного применения к не ­преобразования А (см. утверждение 39.3) получим семейство графов G₁, G₂,……., G_R, среди которых согласно теореме 39.1 имеется 3-связный граф gне являющийся тарным. В силу теоремы 39.5 в G_t есть подграф К, геоморфный К₅ или Кз,з. Если все ребра графа К Î G, то К — подграф графа G, т. е. получено противоречие. Если же некоторое ребро аb Î ЕК не входит

G, то по лемме 39.4 существует Gi-цепь графа G, соединяющая вершины а и b. Нетрудно показать, что Gi-цепи, cоответствующие различным таким ребрам, не имеющих вершин, кроме, возможно, концевых. Заменив каждое такое ребро соответствующей Gi-цепью, получим подграф графа G, гомеоморфный графу К. Вновь имеем проворечие.

В качестве иллюстрации рассмотрим граф Петерсена(содержит подграф, гомеоморфный графу Кз,з(рис. 39.12, {a₁,a₂,a₃} и {b₁,b₂,b₃} — доли). Следовательно, этот граф не является планарным.

Следствий 39.7 (К. Вагнер, 1936 г.). Для любого планарного графа существует плоская укладка, в ко­торой все ребра изображены в виде отрезков прямых линий.

Пусть G — связный планарный граф, имеющий не более четырех вершин. На основании следствия 38.2 граф G является остовным подграфом плоской триангурации Т, которая согласно следствию 39.2 есть 3-связный граф. Поэтому в силу теоремы 39.5 существует прямолинейный граф Т₀, изоморфный графу Т. Очевидно, что исходный граф G получается из Т путем удаления ранее избавленных к G ребер.

Помимо критерия Понтрягина — Куратовского есть и другие критерии планарности графа. Приведем некоторые из них без доказательств.

Теорема 39.8 (К. Вагнер, 1937 г.). Граф планарен тогда и только тогда, когда в нем нет подграфов, стяги­ваемых к графам К₅ или Кз,з.

Поскольку граф Петерсена очевидным образом стяги­вается к К₅ (для этого нужно стянуть пять ребер, соеди­няющих вершины внутреннего и внешнего циклов), то непланарность графа Петерсена с помощью критерия Вагнера доказывается совсем просто.

Отметим здесь, что стягивая любое ребро планарного графа, получаем вновь планарный граф.

Очевидно, что все ациклические графы планарны. Поэтому вполне естественна формулировка критерия пла­нарности, исключающая этот тривиальный случай. Та­ким критерием является следующая

Теорема 39.9 (С. Маклейн, 1937 г.). Граф планарен тогда и только тогда, когда в каждом его нетривиаль­ном блоке есть такой базис циклов С₁, С₂,..., C_k и такой один дополнительный цикл Со, что любое ребро блока принадлежит ровно двум из этих k + 1 циклов.

§ 40. Двойственность и планарность

Целью этого параграфа является получение еще од­ного критерия планарности графа, основанного на поня­тии двойственности.

Условимся, что всюду в этом параграфе слово «граф» означает «псевдограф». Кроме того, видоизменим здесь использованную выше (см. § 3) операцию стягивания ребра е = uv ÎEG, под которой теперь будем понимать удаление ребра е и отождествление вершин и и v в но­вую вершину, инцидентную тем ребрам графа G, которые были инцидентны вершинам и и v, за исключением реб­ра е (рис. 40.1). Тем самым теперь появляющиеся при стягивании ребра кратные ребра не отождествляются, как ранее.

Для плоского графа G построим новый плоский граф G*, который назовем геометрически двойственным к G. Для этого внутри каждой грани Ti графа G выберем по одной точке V*i. Эти точки — вершины будущего графа G*. Далее, каждому ребру е Î EG поставим в соответствие жорданову кривую е*, которая пересекает лишь одно реб­ро е графа G и соединяет вершины v *_i, лежащие в гранях, границы которых содержат ребро е (таких граней может быть две или одна). Кривые е* — ребра графа G*. Очевидно, что ребра графа G* можно провести так, чтобы они не пересекались. На рис. 40.2 сплошной линией изображен граф G, а пунктирной — граф G*. Заметим, что петлю в G* порождает всякий мост в G, а кратные

ребра появляются в G* тогда и только тогда, когда две грани графа G имеют более одного общего ребра.

Из этого построения очевидно, что граф G*, геометри­чески двойственный к плоскому графу G, определяется однозначно с точностью до изоморфизма, причем граф G*

всегда связен. Последнее утверждение легко доказать индукцией по числу вершин графа G* (т. е. по числу гра­ней графа G) путем стягивания ребра е* графа G*, что, очевидно, соответствует удалению ребра е в графе G. При этом, если ребро е — граница двух граней, то упомянутые операции приводят к уменьшению числа вершин графа G* (числа граней графа G) на единицу. Применяя формулу Эйлера, легко получить Утверждение 40.1. Если G — плоский связный (n, т)-граф с f гранями, a G* — (n*, т*)-граф, геометрисески двойственный к нему, с I* гранями, то n* = f, n* = m, f* = n.

Поскольку граф G* — плоский, то можно построить граф, геометрически двойственный к G*, который естественно обозначить через G**. Связь между графами G и G** устанавливает следующая теорема.

Теорема 40.2. Если G — плоский связный граф, то граф G** изоморфен графу G.

Из утверждения 40.1 следует, что n** —f* = n, где n**=\G**\. Следовательно, каждая грань графа G* со­держит одну вершину графа G (G**). Поэтому построе­ние, при помощи которого граф G* получен из G, можно обратить, т. е. получить G из G*.

Граф, двойственный к планарному графу, определяет­ся следующим образом: рассмотрим любую укладку это­го графа и построим геометрически двойственный граф. Здесь уместно отметить, что планарный граф, допускаю­щий несколько укладок на плоскости, может иметь не изоморфные двойственные графы (см. упр. 25).

Теорема 40.3. Пусть G —планарный граф, G* — граф, геометрически двойственный к G. Подмножество ребер из G образует простой цикл в G тогда и только тогда, когда соответствующее множество ребер из G* об­разует разрез в G*.

Для доказательства этой теоремы потребуется одна очевидная лемма.

Лемма 40.4. Пусть Н — связный граф, множество VH вершин которого разбито на два подмножества V₁ и V₂. Множество ребер

является разрезом тогда и только тогда, когда графы H(V₁) u H(V₂) связны.

Доказательство теоремы 40.3. Не исклю­чая общности, будем считать, что G — плоский граф.

Пусть С — простой цикл в G. Тогда он ограничивает одну или несколько внутренних граней графа G, т. е. ог­раничивает часть плоскости, содержащую непустое мно­жество W вершин графа G*. Поэтому ребра из G*, пере­секающие ребра цикла С, образуют множество М в G*, удаление которого разделяет связный граф G* на два подграфа с множествами вершин W и VG*\W (рис. 40.3). Индукцией по числу вершин легко доказать связность каждого из этих подграфов. Следовательно, на основании леммы 40.4 М — разрез в графе G*.

Путем обращения приведенного выше рассуждения до­казывается обратное утверждение о том, что разрезу в G* соответствует простой цикл в G.

Теорема 40.3 естественным образом приводит к следующему комбинаторному определению двойственности графов, которое обобщает геометрическую двойственность позволяет сформулировать еще один критерий планарности графов.

Граф G* называется абстрактно двойственным к графом G, если между множествами EG и EG* существуетбиcекция, обладающая тем свойством, что подмножество ребер из G обра­зует простой цикл в G тогда и только тогда, когда соответствующее ему подмножество ребер из G* об­разует разрез в G*.

На рис. 40.4 изображены граф и абстрактно двойственный к нему граф. Соответствующие ребра обо­значены одной и той же буквой. Другой пример графов G и G* при­веден на рис. 40.5.

Понятие абстрактной двойственности обобщает понятиe геометрической двойственности, так как согласно теореме 40.3 справедливо

Утверждение 40.5. Граф, геометрически двойственный к плоскому графу, является абстрактно двойстнным к нему.

Непосредственно из определения вытекает следующее утверждение.

Утверждение 40.6. Граф Н является абстрактно двойственным к графу G тогда и только тогда, когда ма-

троид M(G) циклов графа G изоморфен матроиду М*(G) разрезов графа Н.

Теорема 40.7. Если граф G* — абстрактно двойственный к G, то G — граф, абстрактно двойственный к G*.

Отметим, что здесь, в отличие от теоремы 40.2, не требуется связность графа G.

На основании утверждения 40.6 матроид M(G) изо­морфен матроиду M*(G*). Поэтому в силу следствия 20.2 матроиды M*(G) и M**(G*) также изоморфны. Но M**(G*) = M(G*). Следовательно, матроид M(G*} цик­лов графа G* изоморфен матроиду M*(G) разрезов гра-

фа G, т. е. на основании утверждения 40.6 граф G явля­ется абстрактно двойственным к G*.

Таким образом, учитывая теорему 40.7, графы G и G* можно называть двойственными.

На вопрос о том, каждый ли подграф графа, имеюще­го двойственный граф, обладает двойственным графом, отвечает

Теорема 40.8. Пусть G и G* — двойственные графы, е = V₁V₂ Î EG, е* = v*₁v*₂ — соответствующее ребро гра­фа G*. Если Н—граф, полученный из графа G удале­нием ребра е, а Р — граф, полученный стягиванием реб­ра е* в G*, то Н и Р — двойственные графы, причем би­екция между множествами ЕН и ЕР остается такой же, как и между EG и EG*.

Любой простой цикл С графа Н = G — е является простым циклом и в графе G. Поэтому соответствующее множество ребер С* — разрез в G*, разделяющий мно­жество вершин VG* на два множества У₁ и V₂. По­скольку е* Ï С*, то вершины v₁* и v₂ *находятся одновре­менно либо вV₁*, либо в V*₂. Поэтому С* — разрез и в Р. Итак, каждому простому циклу графа Н соответству­ет разрез графа Р.

Пусть теперь С* — разрез в Р. Так как е*Ï С*, то С* — разрез и в G*. Поэтому С — простой цикл графа G. Поскольку е Ï С, то С — простой цикл и в G. Следова­тельно, всякому разрезу в Р соответствует простой цикл в G.

Принимая во внимание, что всякий подграф H графа G можно получить из G удалением ребер, не принадле­жащих подграфу G, из теоремы 40.8 выводим

Следствие 40.9. Если граф имеет абстрактно двойственный граф, то всякий его подграф также имеет абстрактно двойственный граф.

Поскольку на основании теоремы 40.7 двум ребрам графа G, инцидентным вершине степени 2 (т. е. разрезу, опpеляющему эту вершину), соответствуют два кратных ребра (2-цикл) графа G*, то получаем еще одно следствиe теоремы 40.8.

Следствие 40.10. Если граф G имеет абстрактно двойственный граф, то любой граф, гомеоморфный графу также имеет абстрактно двойственный.

Теорема 40.11. Всякий планарный граф имеет абстрактно -двойственный к себе граф.

Для доказательства достаточно рассмотреть любую плоскую укладку G исходного планарного графа и граф геометрически двойственный к G. На основании

утверждения 40.5 граф G* — абстрактно-двойственный G. Оказывается, не всякий граф имеет абстрактно двойственный граф.

Утверждение 40.12. Граф Кз,з не имеет абстракт двойственного графа.

Доказательство проведем от противного. Допустим, граф Кз,з имеет двойственный граф G. Поскольку имеет лишь 4-циклы и 6-циклы, то граф G не имеет резов с менее чем четырьмя ребрами. Поэтому deg v ³ 4 для всякой вершины v Î VG. А из того, что граф Кз.з
не имеет разрезов, состоящих из двух ребер, следует, что графе G нет 2-циклов, т. е. он не содержит кратных ребер. Следовательно, \G\ ³ 5. Суммируя все полученное и
принимая во внимание лемму о рукопожатиях, выводим, \EG\ ³ 10. Но \EG\ = \ЕК₃,з\ = 9. Полученное противоречие доказывает утверждение 40.12. Утверждение 40.13. Граф К₅ не имеет абстрактно двойственного графа.

Допустим, что граф К₅ имеет двойственный графG. Так как граф К₅ не имеет циклов длины один или два, то степень каждой вершины графа G не менее 3. В то время из того, что граф К₅ имеет лишь разрезы, состоящие из 4 или 6 ребер, следует, что все простые циклы графа G имеют четную длину, т. е. G — двудольный граф. Если бы было \G\ £6, то получилось бы \EG\ £9, EG\ = \ЕК₅\ = 10. Итак, \G\ ³ 7. Поэтому граф G должен иметь по крайней мере 1/2 X 7 X 3 > 10 ребер.irq это противоречит условию \EG\ = 10.

Теперь мы можем доказать еще один критерий планарности графов.

Теорема 40.14 (X. Уитни, 1932 г.). Граф планарен тогда и только тогда когда он имеет абстрактно двой­ственный граф.

Необходимость установлена теоремой 40.11.

Достаточность докажем, показав, что непланарный граф G не имеет абстрактно двойственного. Согласно тео­реме Понтрягина — Куратовского граф G содержит под­граф Н, гомеоморфный Кз,з или К₅. Если бы граф G имел абстрактно двойственный граф, то по следствию 40.9 и подграф Н имел бы абстрактно двойственный граф. Но согласно следствию 40.10 это означало бы, что граф К₃,₃ или К₅ должен был иметь абстрактно двойствен­ный. Однако это противоречит утверждениям 40.12 и 40.13. Поэтому граф G не имеет абстрактно двойственно­го графа.

Из теорем 40.14 и 40.7 и утверждения 40.6 получаем

Следствие 40.15. Следующие утверждения эквива­лентны:

1) граф G планарен;

2) матроид циклов M(G) кографичен;

3) матроид разрезов М* (G) графичен.