Грани плоского графа. Формула Эйлера

Планарностъ

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

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

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

имеют общих точек, кроме инцидентной им обоим вершины. Примеры плоских графов даны на рис. 36.1.

Любой граф, изоморфный плоскому графу, будем называть планарным. Граф К₄ , изображенный на рис. 36.2,является планарным, так как он изоморфен графам на рис. 36.1, б, в. На том же основании граф на рис. 36.3, а планарен, поскольку графы, представленные на рис. 36.3, а, б, изоморфны.

Очевидны следующие утверждения;

1) всякий подграф планарного графа планарен

2) граф планарен тогда и только тогда, когда каждая его связная компонента — планарный граф.

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

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

Будем говорить, что граф G укладывается в пространство L, если существует такое отображение вершин и ребер графа G соответственно в точки и жордановы кривые этого пространства, что различным вершинам соответствуют различные точки, а кривые, соответствующие различным ребрам, пересекаются только в инцидентных этим ребрам вершинах. Изображенный таким образом граф называется укладкой графа G в пространство L.

Теорема 36.1. Каждый граф укладывается в трехмерное пространство Е³.

Все вершины графа G помещаем в различные точки оси ОХ. Из пучка плоскостей, проходящих через эту ось, выберем \EG\ различных плоскостей. Далее, каждое ребро uv Î EG изображаем в соответствующей плоскости полуокружностью, проходящей через вершины u и v. Понятно, что в результате получаем укладку графа G в Е³, так как все ребра лежат в разных плоскостях и потому не пересекаются во внутренних точках.

Теорема 36.2. Граф укладывается на сфере тогда и только тогда, когда он планарен.

Для доказательства этой теоремы достаточно рассмотреть стереографическую проекцию (рис. 36.4). Пусть граф G уложен на сфере. Проведем плоскость Q, касательную к сфере, так, чтобы северный полюс N (точка, диаметрально противоположная точке касания) не лежал на ребре и не совпадал с вершиной графа G. Те­перь рассмотрим граф G', полученный стереографической проекцией графа G из точки N на плоскость Q. Посколь­ку существует биективное соответствие между точками сферы, отличными от N, и их стереографическими проек­циями, то граф G' плоский и изоморфен графу G. Следо­вательно, G — планарный граф.

Обратное утверждение доказывается аналогично с учетом установленной биекции.

Определения плоского и планарного графов, так же как и теоремы 36.1, 36.2 и многие другие утверждения

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

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

Задача о трех домах и трех колодцах. Имеются три дома 1, 2, 3 и три колодца 4, 5, 6 (рис. 36.5). Каждый хозяин пользуется любым из трех колодцев. В некоторый момент обитатели домов решили проложить дорожки до колодцев так, чтобы исключить встречи на дорожках, т. е. чтобы дорожки не пересекались. Возникает вопрос: возможно ли это, т. е. возможно ли построить плоскую укладку графа К_3,3? Все попытки нарисовать девять непересекающихся дорожек, соединяющих дома с колодцами, заканчиваются неудачей. При этом легко нарисовать семь непересекающихся дорожек, но девятая обязательно пересечет хотя бы одну из этих восьми. Оказывается, что неудачи не случайны. Ниже будет доказано, что граф К_3,3 не укладывается на плоскости, т. е. не является планарным.

На самом деле не только существуют непланарные графы, но верно утверждение, приводимое ниже без доказательства (см. [21]).

Утверждение 36.3. Почти все графы не являются, планарными.

Грани плоского графа. Формула Эйлера

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

графа. Границей грани будем считать множество вершин и ребер, принадлежащих этой грани.

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

Такая грань называется внешней, а остальные грани — внутренними.

Легко видеть, что всякую внутреннюю грань плоско­го графа G можно

преобразовать во внешнюю с помощью стереографической проекции.

Для этого, воспользовав­шись теоремой 36.1, уложим граф G на сфере так,

чтобы северный полюс оказался внутри выбранной грани. Далее рассмотрим стереографическую проекцию G' графа G на плоскость, касающуюся сферы в южном полюсе, т. е. в точке, диаметрально противоположной северному полюсу. Очевидно, что выбранная грань графа G станет при этом внешней в G', а внешняя грань графа G — внутренней гранью графа G', который изоморфен графу G. На рис. 37.2 представлен граф, получающийся из графа, изо­браженного на рис. 37.1, путем такого преобразования. При этом внутренняя грань 1 стала внешней.

Понятие грани естественным образом распространя­ется на псевдо- и мультиграфы (рис. 37.3).

Сформулируем несколько очевидных свойств плоских укладок графа, которые в дальнейшем будем неоднократ­но использовать, порой и не ссылаясь на них.

Свойство 1. Всякий планарный граф допускает такую плоскую укладку, в которой любая выбранная вершина (ребро) графа будет принадлежать внешней грани.

Свойство 2. Пусть граф G состоит из двух связ­ных компонент G₁ и G₂, являющихся плоскими графами,

и произвольным образом выбраны вершины v₁ Î VG₁ и v₂ Î VG₂. Тогда граф G₀, полученный из G слиянием вер­шин v₁ и v₂в вершину v, имеет плоскую укладку. При этом вершина v является точкой сочленения графа G? (рис. 37.4).

Аналогично можно «склеивать» два плоских графа и по ребру.

Свойство 3. Всякие две вершины, принадлежащие границе некоторой грани плоского графа, можно соеди-

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

Отметим, что это свойство является следствием известной теоремы Жордана о кривой.

Свойство 4. Для любого плоского графа каждая точка плоскости, не лежащая на ребре, входит только в одну грань, а каждая точка ребра, не являющаяся вершиной, входит только в одну грань, если это ребро яв­ляется мостом, и точно в две грани, если оно не мост.

Далее будем пользоваться следующими обозначениями: n, m, f—соответственно число вершин, ребер и гра­ней плоского графа.

Теорема Эйлера (1758 г.). Для всякого связного плоского графа верно равенство

n-m + f=2. (1)

Равенство (1) называется формулой Эйлера.

Пусть G — связный плоский n-вершинный граф. Рассмотрим некоторый остов Т этого графа. Очевидно, что дерево Т имеет одну грань (внешнюю) и n вершин. В то же время известно (см. теорему 13.1), что число ребер дерева Т равно n— 1. Поэтому для графа Т фор­мула (1) верна. Теперь будем поочередно добавлять к Т недостающие ребра графа G. При этом на каждом шаге число вершин, естественно, не меняется, а число ребер и число граней увеличивается на единицу на основании свойства 3. Следовательно, формула (1) будет верна для всякого графа, получающегося в результате таких опера­ций (шагов), а поэтому она верна и для графа G, ко­торым заканчивается вся эта процедура.

Из теоремы Эйлера вытекает ряд интересных след­ствий.

Прежде всего, рассмотрим в трехмерном пространстве выпуклый многогранник с n вершинами, m ребрами и I гранями. Очевидно, что спроектировав этот многогранник на описанную около него сферу, далее уложив его так, чтобы северный полюс находился внутри одной из гра­ней, и произведя затем стереографическую проекцию, по­лучим связный плоский граф. Поэтому справедливо

Следствие 37. 1. У всякого выпуклого многогран­ника сумма числа вершин n и числа граней f без числа ребер m равна двум: n + f — m = 2.

Доказательство именно этой формулы и было впервые опубликовано Л. Эйлером в 1758 г. в «Записках Петер­бургской академии наук».

Следствие 37.2. Число граней любой плоский ук­ладки связного планарного (n, т)-графа постоянно и равно m — n + 2.

Другими словами, число I является инвариантом пла­нарного (n, т) -графа, т. е. не зависит от способа укладки этого графа на плоскости.

Следствие 37.3. Для связного планарного (n,m) -графа т£3n -6 при n ³ 3.

Не теряя общности, будем считать, что G — плоский граф. Прежде всего заметим, что всякое ребро плоского графа либо разделяет две различные грани, ли­бо является мостом (см. свойство 4). Поскольку G — граф без петель и кратных ребер, то всякая грань ограничена по крайней мере тремя ребрами (исключение составляет лишь случай, когда G — дерево с тремя вершинами, но для такого графа неравенство Зn — 6 ³ т справедливо). Поэтому число 3 является оценкой снизу удвоенного чис­ла ребер графа G, т. е. 3f £ 2т. Отсюда, учитывая, что по формуле Эйлера f = т — n + 2, приходим к требуемомy неравенству.

Из этого следствия сразу же получаем

Утверждение 37.4. Граф К₅ не планарен.

Действительно, для графа К₅ n = 5, т = 10. По­тому неравенство Зn —6 ³ т превращается в неверное: ³ 10, т. е. граф К₅ не может быть планарным.

Утверждение 37.5. Граф Кз,з не планарен.

Для рассматриваемого графа n = 6, m =9. Поэтому, если бы он был планарным, то для любой его плоской кладки выполнялось бы f = 5 согласно следствию 37.2. В то же время всякая грань двудольного графа Кз,з должна быть ограничена по меньшей мере четырьмя ребрами, следовательно, 2m ³ 4f, т. е. 18 ³ 20. Полученное противоречие доказывает утверждение 37.5.

Мы особо останавливаемся на графах K₅ и К_3,3, поскольку, как мы увидим в § 39, эти графы являются мишальными непланарными графами и играют важную роль во многих критериях планарности. Из теоремы Эйлера вытекает также

Следствие 37.6. Если в связном плоском (n,т)- графе граница каждой грани является r-циклом, r ³ 3, m(r-2)=r(n-2).

Так как каждая грань графа ограничена r-циклом, каждое ребро принадлежит ровно

двум граням, т. е.=2m. Подставляя сюда f из формулы Эйлера, получаем искомый

результат.

Очевидно, что не всегда граница грани плоского графа является простым циклом (см.,

например, грань 2 на рис. 37.1). Однако для 2-связных графов это так. А именно верна

следующая

Теорема 37.7. Плоский граф двусвязен тогда и только тогда, когда границей всякой его грани является простой цикл.

Необходимость. Доказательство проведем от противного. Пусть существует плоский 2-связный граф G, в котором некоторая грань ограничена не простым циклом. Поскольку граф G содержит хотя бы один про­стой цикл, то существует такой максимальный 2-связный подграф Н графа G, что граница каждой его грани яв­ляется простым циклом. При этом Н ¹ G. По лемме 34.7 в G существует H-цепь. Эта простая цепь должна разби­вать некоторую грань плоского графа G на две грани. Очевидно, что каждая из этих граней ограничена простым циклом. Однако это противоречит выбору подграфа G.

Достаточность. Допустим, что плоский граф, каждая грань которого ограничена простым циклом, появляется 2-связным. Тогда граф имеет точку сочленения. Но это значит, что существует грань, ограниченная не­простым циклом.

Теорема 37.8. Связный граф планарен тогда и толь­ко тогда, когда каждый его блок планарен.

Необходимость очевидна.

Достаточность докажем индукцией по числу блоков k. Если k == 1, то утверждение очевидно. Пусть граф G со­стоит из k > 1 планарных блоков. Согласно утвержде­нию 34.6 существует хотя бы один концевой блок В имеющий точку сочленения v. Поскольку подграф G — — (В — v) содержит k — 1 блоков, то по предположению индукции он планарен. Следовательно, существует такая его плоская укладка, что вершина v находится на внеш­ней грани. Точно так же граф В имеет плоскую укладку с вершиной v на внешней грани. Поэтому объединение-(G — (В — v}) U B, изоморфное графу, имеет плоскую укладку на основании свойства 2.

Из теоремы 37.8 следует, в частности, что для выяс­нения вопросов, связанных с планарностью, достаточно рассматривать лишь 2-связные графы.