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

Определение 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). Нетрудно видеть, что эйлерова характеристика не изменилась, так как .

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

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

Рис. 18

Рис. 17

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

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

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

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

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

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

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

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

Теорема 2: Графы и , где множество состоит из элементов вида, не допускают плоской реализации.

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

Пусть — число ребер, ограничивающих грань с номером; имееми , то есть . Полученное противоречие доказывает первую часть теоремы.

Допустим, что допускает плоскую реализацию. Тогда из теоремы 1 имеем равенства: .

Пусть имеют тот же смысл, что и раньше. Очевидно,и поэтому выполнено неравенство: .

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

Теорема 3: (Понтрягин - Куратовский). Для того чтобы граф был плоским, необходимо и достаточно, чтобы он не содержал в качестве подграфов графы или из условия теоремы 2.

Доказательство достаточности в этой теореме здесь не приводится. Отметим, что аналогичных критериев реализуемости графа уже для тора не найдено. Если произвольный граф не допускает плоской реализации, то он, возможно, допускает реализацию пространственную, т. е. может быть изображён без самопересечений ребер на пространственном объекте (шаре, торе и др.).