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

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

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

На рис. 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-связные графы.