1.Планарный и плоский графы. Формула Эйлера для плоских графов.. Гомеоморфизм графов. Критерий планарности графов.

1.Планарный и плоский графы. Формула Эйлера для плоских графов.. Гомеоморфизм графов. Критерий планарности графов.

Теорема. Любой граф можно изобразить в трехмерном пространстве диаграммой, не содержащей пересечения ребер.

Доказательство. Рассмотрим в трехмерном пространстве прямую и проведем через нее связку из m-плоскостей, где m - число ребер графа (рис. 1.23). Все вершины графа расположим на исходной прямой. Каждое ребро будем проводить в одной и только одной плоскости из пучка плоскостей. В результате граф будет представлен диаграммой, не содержащей пересечений ребер. Что и требовалось доказать.

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

Пример. Граф на рис. 1.24 является планарным, т.к. он может быть представлен любой из следующих диаграмм на рис. 1.25.

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

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

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

Число граней графа G обозначается r(G) или просто r. Для плоских графов выполняются определенные соотношения между числом вершин, ребер и граней.

Теорема (формула Эйлера).

В связном плоском графе с n вершинами, m ребрами и r гранями справедливо

n-m+r=2.

Доказательство. Проведем доказательство методом математической индукции по числу m ребер графа. Пусть m=0, тогда т.к. G - связный граф, то , то есть граф представляет собой изолированную вершину. Следовательно, .

Предположим, что формула верна для , покажем, что для она тоже выполняется. Пусть к графу с m ребрами добавляется еще одно ребро. Возможно два случая:

1. Добавляемым ребром соединяются вершины, уже имеющиеся в графе (рис. 1.26).

Получим . В результате имеем ,

что верно, учитывая предположение индукции.

1. Добавляемое ребро соединяет новую вершину с уже имеющейся в графе (рис. 1.27), тогда получим

.

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

Следствие 1. В любой плоской укладке связного планарного графа содержится одно и то же количество граней, равное m-n+2.

Следствие 2. Для связного планарного графа с числом вершин n > 3 справедливо .

Доказательство. Рассмотрим произвольную плоскую укладку связного планарного графа с указанными свойствами. Подсчитаем сумму L₁+L₂+…+L_r, где L_i - число ребер, ограничивающих i-ую грань H_i. Справедливо , т.к. каждая грань ограничивается по крайней мере тремя ребрами. С другой стороны, каждое ребро разделяет не больше двух граней, поэтому в ΣL_i каждое ребро учитывается один или два раза, поэтому ΣL_i ≤ 2m (Например для графа на рис. 1.28 имеем

x₁ x₂ x₃ x₃ x₁ x₅ x₁ x₂ x₅ x₄ x₆

(1+1+1)+(1+1+1)+(1+1+1+1+1)

L₁+L₂+L₃ =

=

L₁+L₂+L₃=

В результате получаем 3r ≤ ΣL_i ≤ 2m или 3r ≤ 2m, или . Тогда, используя формулу Эйлера, получаем .

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

Обозначим через - полный пятивершинный граф (рис. 1.29).

Следствие 3. Граф непланарен.

Доказательство проведем методом от противного. Пусть планарен. В графе число вершин , следовательно, для выполняется следствие 2 настоящей теоремы (). Так как - полный граф, то справедливо

Подставим n и m в формулу следствия 2, получим – противоречие. Полученное противоречие доказывает утверждение следствия

Обозначим через - граф, изображенный на рис. 1.30.

Следствие 4. Граф – непланарен.

Доказательство проведем методом от противного. Пусть планарен. Следовательно, для него справедлива формула Эйлера: . Поскольку граф в качестве подграфов не содержит треугольников, то есть циклов длины три, то в любой плоской укладке этого графа каждая грань ограничена не менее чем четырьмя ребрами. Следовательно, должно выполняться неравенство (см. доказательство следствия 2) или . Учитывая это неравенство и формулу Эйлера, получаем .

В справедливо m=9, n=6. Подставляя эти числа в последнее неравенство, получаем - неверно. Полученное противоречие доказывает, что непланарен.

Подразбиением ребра x={u,v} называется операция удаления этого ребра и замены его двумя ребрами {u,w} и {w,v}, соединенными одной дополнительной общей вершиной w.

Таким образом, операция подразбиения ребра сводится к навешиванию дополнительных вершин на ребро.

Два графа называются гомеоморфными, если они могут быть получены из одного и того же графа подразбиением его ребер.

Графы H (рис. 1.32) и T (рис. 1.33) гомеоморфны, т.к. могут быть получены из одного и того же графа G (рис. 1.31) подразбиением его ребер.

Теорема (Понтягина – Куратовского, критерий планарности графов).

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам и .

Теорема приводится без доказательства.

Пример. Граф, изображенный на рисунке 1.34, непланарен, так как он содержит подграф, гомеоморфный графу (он на рисунке ограничен пунктиром).

Замечание. В теории графов доказано, что почти все графы непланарны и почти все графы являются гамильтоновыми.

Дата добавления: 2015-10-21