Формула Эйлера, основные теоремы

   
На этом шаге мы рассмотрим формулу Эйлера.

Формула Эйлера.
Для любой геометрической реализации графа G=(V,E) на плоскости верно:
p-q+r=2, где p=|V|, q=|E|, r - число граней (без доказательства).
Теорема 2.
Если в связном планарном графе нет циклов длины меньше k и k=3,
то q<=k(p-2)/(k-2), где p=|V|, q=|E|.
Доказательство (не совсем формальное).
Пусть граф реализован на плоскости и при этом получилось r граней.
Пусть qi - число сторон в i-й грани (см. рисунок 1).
Каждое ребро является стороной двух граней, поэтому 2q=Sum(qi, i=1...r).
По условию в графе нет циклов длины меньше k, но тогда qi=k
(т.к. стороны грани образуют цикл) и 2q=Sum(qi, i=1..r)-k*r.
По формуле Эйлера r=2-p+q, следовательно, 2q=k*(2-p+q), из чего следует
доказываемое неравенство.


Рис.1. Пример графа

   
Граф на рисунке 1 имеет 8 ребер, 3 грани, 3+6+7=16 сторон.
Следствие 1 теоремы 2.
Для любого связного планарного графа без петель и кратных ребер выполняется
неравенство: q<=3(p-2), где p=|V|, q=|E|.
Доказательство.
Т.к. по условию в графе нет петель и кратных ребер, в нем нет и циклов длины меньше 3, поэтому, подставляя
k=3 в неравенство теоремы 2, получаем: q<=k(p-2)/(k-2)=3(p-2).
Теорема 3.
Граф K5 не планарен.
Доказательство.
K5 связен, в нем нет петель и кратных ребер, но следствие 1 теоремы 2 не выполняется -
q=10>3(p-2)=9. Значит, K5 не планарен.
Теорема 4.
Граф K33 не планарен.
Доказательство.
Замечание: использование следствия 1 теоремы 2 здесь не поможет, т.к. q=9<3(p-2)=12.
В K33 нет циклов длины меньше 4, поэтому применим неравенство теоремы 2 непосредственно
(при k=4): q=9>4(p-2)/2=8. Следовательно, K33 не планарен.

Теорема Понтрягина-Куратовского (критерий планарности графов).
Граф G планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 или K33.
Доказательство.
Необходимость следует из утверждений 1-4 (см. ниже), а также из того факта, что графы K5 и
K33 не планарны (в соответствии с теоремами 3 и 4).
Утверждение 1.
Если графы U1 и U2 изоморфны, то U1 планарен тогда и только тогда,
когда U2 планарен.
Доказательство.
Любая геометрическая реализация U1 является геометрической реализацией U2, и наоборот.
Утверждение 2.
Любое подразделение U' графа U планарно тогда и только тогда, когда U планарен.
Доказательство.
(=>) граф U' планарен, следовательно, существует его геометрическая реализация на плоскости R'.
Построим по R' плоскую геометрическую реализацию R графа U. Для этого объединим все
линии R', соответствующие ребрам U', полученным в результате выполнения операций подразделения ребер.
В силу существования R граф U является планарным.

   
(<=) граф U планарен, следовательно, существует его геометрическая реализация на плоскости R. Построим по
R плоскую геометрическую реализацию R' графа U'. Для этого повторим в любой последовательности
операции подразделения ребер, которые привели к построению U'. После выполнения каждой из этих операций будем
разбивать линию, соответствующую подразделяемому ребру, на две линии (разбиение можно производить в любой
точке, не совпадающей с концами линии). В силу существования R' граф U' является планарным.
Утверждение 3.
Если графы U1 и U2 гомеоморфны, то U1
планарен тогда и только тогда, когда U2 планарен.
Доказательство.

(=>) по условию U1 и U2 гомеоморфны (по определению), поэтому существуют их
изоморфные подразделения U1' и U2'. По условию граф U1 планарен
{по утв.2}, граф U1' планарен {по утв.1}, поэтому изоморфный ему граф U2' планарен
{по утв.2}, следовательно граф U2 планарен.

   
(<=) аналогично.
Утверждение 4.
Если подграф U' графа U не планарен, то U также не планарен.
Доказательство.
Допустим, что граф U планарен. Следовательно, существует его плоская геометрическая реализация R. Но тогда можно
построить плоскую геометрическую реализацию R' графа U': для этого достаточно удалить из R точки и линии,
соответствующие тем вершинам и ребрам U, которых нет в U'. Из существования R' следует, что U' планарен - получили противоречие.

Достаточность теоремы доказывается гораздо сложнее.

   
Существуют и другие критерии планарности графов.

   
На следующем шаге мы рассмотрим раскраски графов.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий