09. Планарные и плоские графы. Формулировки теоремы Понтрягина-Куратовского и теоремы Эйлера о соотношении чисел граней, ребер и вершин плоского графа

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

Планарен, потому что его можно изобразить и так:

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

В математике доказывается, что Не являются планарными два следующих графа: (полный граф на пяти вершинах) И (полный двудольный граф, каждая доля в котором состоит из трех вершин). Существует классическая Теорема Понтрягина-Куратовского, кото-рая утверждает следующее: Граф планарен тогда и только тогда, когда в нем нет подграфов, полученных подразбиением ребер из И .

Опишем классическую конструкцию Эйлера, связанную с плоскими графами. Пусть - плоский граф. Это означает, что имеется определенное изображение его на пло-скости, в котором ребра пересекаются только в вершинах. Каждый простой цикл такого графа ограничивает две части плоскости: одна - внутренняя (ограниченная), другая - внешняя (неогра-ниченная). Если по части плоскости, ограниченной простым циклом плоского графа, не прохо-дит ни одна цепь этого графа, начало и конец которой принадлежат обсуждаемому циклу, то эта часть плоскости называется Гранью плоского графа. Если грань неограниченная, то она называ-ется Внешней; ограниченная грань плоского графа называется Внутренней.

Можно доказать, что У каждого плоского графа обязательно есть внешняя грань и при -

Том только одна.

Подсчитаем для примера количество граней в каком-нибудь плоском графе. Пусть име -

Ется следующий плоский граф:

Здесь - четыре грани, причем одна из них - внешняя. Заметим, кстати, что здесь вершин - 13, а

Ребер - 15. Подсчитаем те же параметры (количества граней, вершин и ребер еще в одном при -

Мере:

Здесь граней - 5, вершин - 7, ребер - 10.

Классическая Теорема Эйлера утверждает: Если в плоском графе имеется «г» граней, «в»

Вершин и «р» ребер, то обязательно выполняется равенство: «г» + «в» - «р»=2.

Отсюда возникает множество соотношений для плоских графов, из которых остановимся

Только на одном, Фиксируем какой-нибудь плоский граф. Пусть в нем вершин и ребер. К

Этому графу можно, при необходимости, добавить ребра и получить снова плоский граф с тем

Же количеством вершин, но с увеличенным количеством ребер такой, что все грани в нем будут

Ограниченны треугольниками (включая внешнюю). Если - новое количество ребер и - ко -

Личество граней в этом новом графе, то ; тогда теорема Эйлера приобретает вид: , но , так что , откуда , а Для

Произвольного плоского графа, следовательно,

.

< Предыдущая		Следующая >