Эйлерова характеристика. Плоские графы.

 

Определение 1: Пусть задан набор отрезков гладких кривых на плоскости, причем выполнны следующие условия:

1) отрезки и не имеют общих точек, кроме, быть может, концевых (в частности , не самопересекается, хотя набор может быть замкнутым);

2) граф изоморфен , где граф определен равенством: . Здесь — это множество концевых точек отрезков на плоскости, .

Тогда набор называется плоской реализацией графа .

Рис. 15

 

Разумеется, не каждый граф допускает плоскую реализацию. Например, графы, изображенный на рис. 15, как будет доказано ниже, не допускают плоской реализации.

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

Определение 2: Граф называется плоским, если он допускает плоскую реализацию.

Дадим теперь определение наложения двух плоских реализации графов.

Определение 3: Пусть — плоская реализация графа , а — плоская реализация графа . Пусть — части, на которые кривые набора делят отрезок ; определены аналогично. Набор

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

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

Определение 4:Эйлеровой характеристикой связного плоского графа называется число

,

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

Теорема 1 (теорема Эйлера): Для любого плоского связного графа справедливо равенство: .

Доказательству этой теоремы предпошлем доказательство двух лемм.

Лемма 1: Пусть связный плоский граф получен из связного плоского графа наложением на последний ребра с несовпадающими концами. Тогда справедливо соотношение: .

Доказательство: Из условия, очевидно, что пересечение графа и ребра не пусто (иначе не мог бы быть связным). Пусть , — концы отрезка , а — точки пересечения и , рассмотрим несколько случаев.

Случай 1. Ни одна из точек , , не совпадает ни с одной вершиной графа . Очевидно, что число вершин в графе равно . Если на граф наложить отрезок , то число ребер увеличится на два, а число областей не изменится (рис. 16, а). При последовательном наложении отрезков число ребер увеличивается на два, а число областей — на единицу (рис. 16, б). При добавлении же отрезка число ребер увеличивается на единицу, а число областей не изменяется (рис. 16, в). Это рассуждение показывает, что числа ребер и областей графа равны: .

Рис. 16

Складывая эти равенства, получаем утверждение леммы.

Случай 2. Некоторые из точек являются вершинами графа . Пусть число таких точек . Тогда справедливо равенство:

.

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

В результате сложения получаем утверждение леммы.

При разборе случаев 1 и 2 предполагалось, что точки и не принадлежат графу . Если, например, точка принадлежит графу , то доказательство можно свести к уже разобранному случаю следующим образом.

Добавим к отрезку малый кусок так, чтобы он пересекался с только в точке (рис. 17). Нетрудно видеть, что эйлерова характеристика не изменилась, так как .

При этом задача сводится к уже разобранной ситуации. Подобным образом поступим и с концом в том случае, если .

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

Рис. 17

Рис. 18

 

Лемма 2: Пусть связный граф получен наложением графа на граф , тогда: .

Доказательство. Проведем доказательство методом индукции по числу ребер графа . Базисом индукции является лемма 1. Проведем индукционный шаг. Различаем два случая.

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

Случай 2. Граф пересекается с графом по одному ребру . Если граф — не дерево, то в нем есть цикл. Удаляя ребро этого цикла, не совпадающее с и рассуждая аналогично случаю 1, получим равенство . Если же — дерево, то в нем имеется, по крайней мере, два тупика. Удаляя не совпадающий с тупик, получим, что эйлеровы характеристики графов и совпадают.

Доказательство теоремы 1. Рассмотрим два плоских связных графа и (рис. 18). Пусть — дуга, одна вершина которой принадлежит , а другая . Пусть — наложение на . По лемме 2 справедливо равенство: , поскольку связен. Кроме того, наложение графа на граф также связно, а поэтому . Аналогично получим равенство и поэтому эйлеровы характеристики графов и совпадают. Из произвольности графов и получаем, что любые два плоских связных графа имеют одну и ту же эйлерову характеристику. Достаточно подсчитать эту характкристику для простейшего плоского связного графа. В качестве такого графа выберем граф . Для него ; отсюда . Теорема доказана.

Замечания: 1. Эта теорема дает основание называть число 2 эйлеровой характеристикой плоскости.

2. Условие связности графа существенно для доказательства теоремы, так как уже для графа имеем равенство и .

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