Формула Эйлера

Область, ограниченная ребрами в плоском графе, и не содержащая внутри себя вершин и ребер, называется гранью графа. Внешняя часть плоскости также образует грань. На рис. 4.47 изображен граф с 3 гранями.

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

Рис. 4.47

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

n–m+f=2, (4.6)

которое называется формулой Эйлера.

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

Из теоремы Эйлера вытекают следующие следствия.

Следствие 4.13.1. Число граней любой плоской укладки связного планарного графа постоянно и равно m–n+2.

Другими словами, число f не зависит от способа укладки этого графа на плоскости.

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

Формула Эйлера позволяет доказать непланарность некоторых графов.

Графом K₅ называется граф с 5 вершинами, в котором каждая пара вершин соединена ребром.

Теорема 4.13.2. Граф K₅ не планарен.

Доказательство. Допустим, что для графа K₅ существует планарная реализация. Так как граф K₅ связен, то для этой планарной реализации справедлива формула Эйлера n–m+f =2. Поскольку в графе K₅ имеем n=5 и m=10, то число всех граней должно равняться f=2–n+m=7. Пусть грани занумерованы 1, 2, ..., f и пусть при обходе i-ой грани по периметру (по ее краю) проходится m_i ребер. Так как при этом каждое ребро проходится дважды (оно является стороной для двух граней), то . Но в каждой грани не менее 3 сторон. Поэтому m_i³3 для всех i. Отсюда . Получаем 20 ³ 21 – противоречие. Значит, для графа K₅ не существует планарной реализации.

Графом K_3,3 называется граф с 6 вершинами a₁, a₂, a₃, b₁, b₂, b₃, в котором каждая вершина a_i соединена ребром с каждой вершиной b_j и нет других ребер.

С графом K_3,3 связана следующая известная задача о трех домах и трех колодцах. Есть 3 дома и 3 колодца, но хозяева домов в большой вражде. Можно ли так проложить дорожки от каждого дома к каждому колодцу, чтобы они нигде не пересекались? Ответ на этот вопрос дает следующая теорема.

Теорема 4.13.3. Граф K_3,3 не планарен.

Доказательство. Допустим, что для графа K_3,3 существует планарная реализация. Так как граф K_3,3 связен, то для этой планарной реализации справедлива формула Эйлера n–m+f = 2. Поскольку в графе K_3,3 имеем n=6 и m=9, то число всех граней должно равняться f=2–n+m=5. Так же, как в доказательстве предыдущей теоремы, получаем, что , где m_i - число сторон в i-ой грани. Но в графе K_3,3 нет циклов длины 3. Поэтому в каждой грани не менее 4 сторон. Следовательно, m_i³4 для всех i. Отсюда . Получаем 18 ³ 20 - противоречие. Значит, для графа K_3,3 не существует планарной реализации.

Критерии анализа планарности

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

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

Существует следующий критерий планарности.

Теорема 4.13.4. (Понтрягина-Куратовского). Для того чтобы граф G был планарным, необходимо и достаточно, чтобы он не содержал ни одного подграфа, гомеоморфного графам K₅ или K_3,3.

Эквивалентная форма критерия планарности описана в следующей теореме.

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

Под стягиванием понимается последовательное отождествление вершин, связанных ребрами.

Рассмотренные критерии планарности таковы, что если даже удалось установить планарность графа, то нет информации о том, как строить его укладку на плоскости. В то же время для решения практических задач недостаточно знать, что граф планарен, а необходимо построить его плоское изображение. Появились алгоритмы, которые не только проверяют граф на планарность, но и одновременно строят его плоскую укладку, если это возможно. Одним из таких алгоритмов является следующий [1].