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

А б

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

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

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

Примеры плоских графов (рис. 4.45).

Рис. 4.45. Плоские графы

Любой граф, изоморфный плоскому графу, будем называть планарным. Граф на рис. 4.46 является планарным, так как он изоморфен графу на рис. 4.45.б.

Рис.4.46

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

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

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

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

Область, ограниченная ребрами в плоском графе, и не содержащая внутри себя вершин и ребер, называется гранью графа. Внешняя часть плоскости также образует грань. На рис. 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 £3 n -6 при n ³3.

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

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

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

Доказательство. Допустим, что для графа K ₅ существует планарная реализация. Так как граф K ₅ связен, то для этой планарной реализации справедлива формула Эйлера m – n + 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 не существует планарной реализации.

Дата добавления: 2014-12-27