§ 3. Планарные графы

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

3.1. Теоремы Эйлера и Куратовского.

Определение.

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

б) Карта G называется связной, если G связен. //

Пример 3.1.

1. . Изображение и соответствующая карта G показаны на рис. 7.7; Следовательно, G – планарный граф.

2 . Графы, изображенные на рис. 7.8.а и б обычно обозначают через и соответственно. Позднее мы рассмотрим доказательство того факта, что эти графы не являются планарными. //

Р ис. 7.7

Рис. 7.8

Карта делит на «области»; проиллюстрируем это в следующем примере.

Пример 3.2. Рассмотрим карту, изображенную на рис. 7.9. Она делит на четыре области; , и являются ограниченными областями, а – «неограниченная» область.

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

Теорема Эйлера. Для произвольной связной карты

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

Рис. 7.9 Рис. 7.10

1) Добавим новую вершину и присоединим ее к существующей карте.

2) Соединим две существующие вершины.

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

В первом случае добавим новую вершину так, как, например, это сделано на рис. 7.10. Этот процесс увеличивает на 1 и на 1, однако остается тем же самым, вследствие чего значение не изменяется.

Рис. 7.11 Рис. 7.12

Во втором случае соединим две вершины, как, например, на рис. 7.11. Тогда остается тем же самым, возрастает на 1, а уменьшается на 1; следовательно, значение опять остается неизменным.

Все карты могут быть получены из случая путём выполнения 1) и (или) 2); если необходимо, то процедура повторяется. Следовательно, так как при , а значение остаётся инвариантным при выполнении 1) и 2), то мы имеем для всех связанных карт.

Очевидно, что каждая область карты ограничена замкнутым маршрутом. Ниже привереды два простых результата (один касается ограничивающих замкнутых маршрутов). Этих результатов оказывается достаточно для доказательства того, что и не являются планарными.

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

П р и м е р 3.3. Для карты, изображённой на рис. 7.12. имеем граничный замкнутый маршрут для , а граничный замкнутый маршрут для . Следовательно, //

П р е д л о ж е н и е. Пусть планарный граф. Тогда

а)

б) если то

Доказательство оставляем читателю в качестве упражнения.

П р е д л о ж е н и е. Графы и не являются планарными.

Д о к а з а т е л ь с т в о.

Докажем, что не является планарным. Если – планарный граф, то из предыдущего результата следует, что Тогда для графа с и имеем , что неверно. Таким образом, предположение, что граф планарный, неверно.

Докажем теперь, что не является планарным. Предполагая противное, имеем

Однако в никакие три вершины не связаны одна с другой; следовательно, для всех . Из формулы Эйлера ; следовательно,

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

Графы и интересны тем, что они являются существенно «единственными» непланарными графами. Все другие непланарные графы имеют подграфы «подобные» или или . Перед тем как уточнить наше утверждение, необходимо ввести два определения.

О п р е д е л е н и е.

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

б) Граф называется стягиваемым к графу , если может быть получен из путём последовательности элементарных стягиваний.

П р и м е р 3.4. На рис. 7.13 изображены графы и , при этом стягивается к . //

Рис. 7.13

Т е о р е м а (Куратовский). Граф не является планарным тогда и только тогда, когда он не содержит подграфов, стягиваемых к или .

Доказательство этой теоремы лежит за пределами целей книги и поэтому опущено. //

Из теоремы Куратовского заключаем, что и являются существенно единственными не планарными графами. Алгоритмы, основанные на этой теореме, были придуманы для того, чтобы определить, является ли данный граф планарным или нет.