Теорема Эйлера

Рассмотрим связный планарный граф с числом вершин и числом ребер . Число граней в любой планарной укладке данного графа равна k. Данные три параметра связаны соотношением:

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

Доказательство будем проводить по индукции по числу граней в укладке планарного графа.

1-ый шаг индукции. Рассмотрим граф с единственной гранью. Связный граф с единственной гранью – дерево (так как грань одна, то циклов в графе быть не может, поскольку каждый цикл разрезает плоскость на 2 области). Известно, что в дереве на вершинах ребро. Подставив данные значения в формулу, получаем тождество:

k-ый шаг индукции. Допустим, что утверждение доказано для планарного связного графа с числом граней k-1>1. Рассмотрим планарный граф, с числом граней k. Так как k , то в таком графе есть цикл. Рассмотрим грань H, в которой граница - некоторый цикл .

H

Пусть – некоторое ребро этого цикла. Удалим это ребро. Получим связный граф с тем же самым числом вершин , с числом ребер на меньше () и с числом граней k-1. Тогда, применяя предположение индукции:

Что и требовалось доказать.

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

Определение. Операция стягивания обратна операции подразбиения:

(вершина h в графе смежна только вершинам v и w)

Дата добавления: 2017-01-13