Плоские и планарные графы

              Из формулы Эйлера можно вывести разные другие формулы. Из них наиболее часто применяется следующая формула.

              Теорема 2.3. Пусть G — планарный граф без изолированных вершин, vi — число его вершин, из которых выходит i рёбер, fj — число граней, ограниченных  рёбрами (с учетом их кратностей).

Тогда где s — число компонент связности графа G.

              Доказательство.   Ясно, что (каждое ребро имеет ровно два конца и  принадлежит ровно двум граням). Кроме того, и Поэтому из формулы Эйлера следует, что где s — число компонент связности графа G.             

              Следствие.   Если все грани 4-угольные, то 3v1+2v2+v38. Часто используется также следующее неравенство

3.      Критерии планарности

Имеется несколько критериев планарности графа. Мы рассмотрим характеризации планарности графов, данные G. С. Понтрягиным, К. Куратовским, К. Вагнером и С. Наклейном. Следует заметить, что практическая про­верка условий, которыми ниже характеризуются планарные графы, не всегда является простой. Однако разработаны эффективные алгоритмы, позволяющие для любого заданного графа или найти его плоскую укладку, или установить, что граф непланарен. Один из таких алгорит­мов приведен в § 41.

Для того чтобы сформулировать широко известный критерий Понтрягина — Куратовского, введем понятие гомеоморфизма графов. Нам понадобится операция под­разбиения ребра е = аb графа. Она состоит в следующем:

из графа удаляется ребро е и добавляются два новых ребра е1 = аv, e2 = vb, где v — новая вершина.

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

На рис. 39.1 изображены гомеоморфные графы.

Если граф планарный, то очевидно, что любой граф,

гомеоморфный ему, также является планарным.

Исторически первым критерием планарности графов является следующий критерий, доказанный Л. С. Понтрягиным (1927 г.) и К. Куратовским (1930 г.) независимо друг от друга.

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

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

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

Необходимость доказана, по­скольку доказана непланарность графов К5 и Кз,з (теорема 1.3.). Для доказательства достаточности требуются новые понятия и теоремы. Будет достаточно, ес­ли мы, касаясь вопросов, связанных с плоской укладкой 2-связного графа G, рассмотрим лишь 3-связные графы, полученные из G специальным образом.

Пусть x(G) = 2|G.|  4. Из определения двусвязности вытекает существование вершин а, b  VG, таких что граф Н = G — а — b не связен. Рассмотрим следующее преобразование А графа G. Пусть h1, h2, ..., Hr — связные компоненты графа Н. Для каждой такой компо­ненты Hi рассмотрим граф Gi, порожденный в G мно­жеством V U Hi , a Ub и дополненный ребром ab, если аb  EG. В результате преобразования А получаем семей­ство графов g1, g2, ..., Gr, причем |Gi|  3, х(Gi)  2 (i = l, r) (рис. 39.2).

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

Необходимость. Если G — планарный граф, то любой его подграф, в том числе G0i = G(VGi), плана­рен. Если Gi содержит ребро аb, то Gi = G0i. В противном случае по лемме 34.7 в G существуетG0i-цепь L, соединя­ющая вершины а и b. Подграф Gi0 U L планарен, но он гомеоморфен графу Gi.

Достаточность. Пусть все графы g1, G2, ..., Gr планарны. Пусть Р1, Р2 , ..., Рr— соответствующие им плоские укладки, у которых ребро ab лежит на внешней грани. Будем последовательно объединять графы Р1, p2, ..., Рr. Сначала построим такую укладку объедине­ния Р1,2 графов Р1 и P2, в которых имеется общее ребро ab, что граф Р2 лежит на внешней грани графа Р1. Затем изобразим P1,2 так, чтобы ребро ab оказалось на внешней грани, и используя прежний прием, построим объедине­ние P1,.2,3 графов P1,2и Pз (рис. 39.3) и т. д., пока не объ­единим все графы p1, Р2, ..., Рг. Полученный в результат - не плоский граф p1,2 …….r может отличаться от исходного графа G только ребром аb.

Утверждение 3.1.1. Пусть x(G)=2, |G|  4. Тогда в результате многократного применения преобразова              ния А к графу G будет получено такое семейство графов              Gi  G2, .. …GR ,что для любого i = 1, R либо Gi=K3, либо х (Gi)  3.

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

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

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

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

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

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

Пусть G — 3-связный граф, |G|=n  5 и для всех графов с меньшим числом вершин теорема верна, тогда в графе G есть такое ребро x = uv, что граф Gx, полученный из G в результате стягивания этого ребра, является 3-связным. Пусть Gx содержит под­граф Н, гомеоморфный K5 (рис. 39.5, а). Покажем, что тогда граф G содержит подграф, гомеоморфный К5 или Kз,з. Это очевидно в случае, когда Н не содержит верши­ны x0, полученной в результате стягивания ребра х, или содержит ее в качестве вершины степени 2. Пусть теперь степень каждой из вершин а, b, с, d, х0 в Н равна четы­рем. Тогда вершина х0 соединена простыми непересекающимися цепями L1, L2, .L3, L4 с вершинами а, b, с, d cоответственно. В графе G этим цепям соответствуют пе­ресекающиеся простые цепи L1, L2, .L3, L4, соединяющие каждую из вершин а, b, с, d с одной из вершин и и v. Если одна из этих вершин, например и, принадлежит трем или четырем цепям, то в G существует подграф, гомеоморфный К5 (рис. 39.5, б).  А если каждая из вершин u и v принадлежит ровно двум цепям, то в G существует подграф, гомеоморфный Кз,з (рис. 39.5, в, г).

Пусть теперь в Gx нет подграфов, гомеоморфных графы К5 или .Кз.з. По индуктивному предположению существует выпуклый прямолинейный граф G0х, изоморфный графу Gx. Тогда G0x—x0 — 2-связный плоский граф, каждая грань которого ограничена простым циклом.

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

L1 =(a1 ..., a2),  L2 =(a2, ..., а3), ..., Lk = (ak, ..., a1 ).                                    (1)

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

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

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

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

Будем считать, что вершины из NG(u)\v находятся па цепи Lk и разбивают ее на части: (а1, ..., b1), (b1, ... ..., b2), ..., (bl-i, ..., bl), (bl,, ..., ak). Обозначим через Т точки плоскости, лежащие внутри кривой (цикла) (х0, b1, ..., b2, ..., bl х0). Поместив вершину и в лю­бую точку области О (х0) объединяя с Т и соединив и со всеми вер­шинами из NG(u) (считая x0 =v), получим выпуклый прямолинейный граф, изоморфный графу G (рис. 39.6). Подобным образом поступаем и тогда, когда вершина х0 принадлежит внешней грани графа G0x. (На рис. 39.7 а, б изображен случай, когда вершина и принадлежит внут­ренней грани графа G', а на рис. 39.7 в, г — внешней.)

     Случай 2. Не существует цепи (1), содержащей все вершины  из  множества  NG(u)\v.  В  этой  ситуации множество всех ребер, инцидентных и и v, нельзя изобра­зить без пересечений. В самом деле, если

М= \ (NG(u)\v)  (NG(v)\u)\  3,

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

Осталось доказать достаточность условий теоремы. Пусть в графе G нет подграфов, гомеоморфных К5 или Кз,з- если G — 3-связный граф, тогда он планарен. Пусть x (G) =2, |G|  5. Далее доказательство проведём от противного. Предположим, что граф G не планарный. Тогда в результате многократного применения к не ­преобразования А получим семейство графов G1, G2,……., GR, среди которых имеется 3-связный граф G. В Gt есть подграф К, геоморфный К5 или Кз,з. Если все ребра графа К  G, то К — подграф графа G, т. е. получено противоречие. Если же некоторое ребро аb  ЕК не входит G, то по лемме существует Gi-цепь графа G, соединяющая вершины а и b. Нетрудно показать, что Gi-цепи, cоответствующие различным таким ребрам, не имеющих вершин, кроме, возможно, концевых. Заменив каждое такое ребро соответствующей Gi-цепью, получим подграф графа G, гомеоморфный графу К. Вновь имеем проворечие.

В качестве иллюстрации рассмотрим граф Петерсена(содержит подграф, гомеоморфный графу Кз,з(рис. 39.12, {a1,a2,a3} и {b1,b2,b3} — доли). Следовательно, этот граф не является планарным.

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

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

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

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

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

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

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

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

Условимся, что всюду в этом пункте слово «граф» означает «псевдограф». Кроме того, видоизменим здесь использованную выше операцию стягивания ребра е = 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) на единицу. Применяя формулу Эйлера, легко получить