Планарные графы

vi из V сопоставлена точка ai в некотором евклидовом пространстве,

причем ai ¹ aj при i ¹ j.
Каждому ребру e = (vi, vj) из E сопоставлена непрерывная кривая L, соединяющая точки ai и aj и не проходящая через другие точки ak.

точек, кроме концевых, то это множество точек и кривых называется

геометрической реализацией графа G.


ТЕОРЕМА: Каждый конечный граф G можно реализовать в трехмерном евклидовом пространстве (без пересечения ребер).

ней все вершины графа G. Пусть в G имеется q

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

геометрическое представление на плоскости (без пересечения ребер).
Непересекающиеся части плоскости,

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

= (V,E) с p вершинами, q ребрами и r гранями

выполняется равенство: p-q+r = 2.

Доказательство. При фиксированном p индукцией по q. Так как G - связный граф, то q ³ p-1.

связный и q = p-1, то G - дерево, то

есть в G нет циклов. Тогда r = 1.
Отсюда p-q+r =p-(p-1)+1 = 2.
б) Пусть для p-1£qПусть G - связный граф с p вершинами и q0 ребрами и пусть в его планарной реализации r граней. Так как q0 > p-1, то G - не дерево.

цикл. Тогда к нему с двух сторон примыкают разные грани.

Удалим ребро e из G.
Тогда две грани сольются в одну, а полученный граф G1 останется связным.
При этом получится планарная реализация графа G1 с p вершинами, q0-1 ребрами и r-1 гранями.

G1 справедлива формула Эйлера, то есть p-(q0-1)+(r-1) = 2, откуда

p-q0+r = 2.
Что и требовалось доказать.

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

пара вершин соединена ребром.

K5 существует планарная реализация. Так как граф K5 связен, то

для этой планарной реализации справедлива формула Эйлера p-q+r = 2. Поскольку в графе K5 имеем p = 5 и q = 10, то число всех граней должно равняться r = 2-p+q = 7.
Пусть грани занумерованы 1, 2, ..., r и пусть при обходе i-ой грани по периметру (по ее краю) проходится qi ребер.

стороной для двух граней), то


Но в

каждой грани не менее 3 сторон. Поэтому qi ³ 3 для всех i. Отсюда


Получаем 20 ³ 21 - противоречие. Значит для графа K5 не существует планарной реализации. 

b1, b2, b3, в котором каждая вершина ai соединена ребром

с каждой вершиной bj и нет других ребер

K3,3 существует планарная реализация. Так как граф K3,3 связен, то

для этой планарной реализации справедлива формула Эйлера p-q+r = 2.
Поскольку в графе K3,3 имеем p = 6 и q = 9, то число всех граней должно равняться r = 2-p+q = 5.

qi - число сторон в i-ой грани.
Но в графе

K3,3 нет циклов длины 3. Поэтому в каждой грани не менее 4 сторон.
Следовательно, qi ³ 4 для всех i. Отсюда


Получаем 18 ³ 20 - противоречие. Значит для графа K3,3 не существует планарной реализации. 

и достаточно, чтобы он не мог содержать в себе в

качестве подграфов граф К33 или К5.

появляется в нём ровно 1 раз.
Граф G(V,E) называется эйлеровым, если

он имеет замкнутый эйлеров путь (эйлеров цикл), и полуэйлеровым, если  эйлеров путь, не являющийся замкнутым, но содержащий все вершины по 1 разу.

и только тогда, когда каждая вершина G имеет чётную степень.

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

Р – эйлеров цикл в графе G. Тогда при каждом прохождении цикла через  вершину графа используется одно ребро для входа и одно ребро для выхода.

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

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

степень каждой вершины не меньше 2, то граф имеет цикл.
Следовательно

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

общие вершины с циклом С.
Проходим рёбра G следующим образом: идём

по рёбрам цикла С до первой неизолированной вершины графа G1. Затем проходим эйлеров цикл в компоненте графа G1, затем снова двигаемся по циклу С до следующей неизолированной вершины графа G1.
Процесс закончится в исходной вершине, что и показывает существование эйлерова цикла. 

компонентой связности.
Пример графа с 2 компонентами связности.

эйлеров граф. Тогда следующая процедура всегда возможна и приводит к

построению эйлеровой цепи графа G.
Выходя из произвольной вершины, идём по рёбрам графа произвольным образом, соблюдая следующие правила:
Стираем рёбра по мере их прохождения (вместе с изолированными вершинами, которые при этом образуются);
На каждом этапе идём по ребру, удаление которого нарушает связность, только в том случае, когда нет других возможностей.

{i,M}, M, {M,J}, J, {J,N}, N, {N,K}, K, {K,H}, H,

{H,i}, i, {i,J}, J, {J,K}, K, {K,L}, L, {L,M}, M, {M,N}, N, {N,H}, H.

постановкой:
можно ли нарисовать какую ни будь диаграмму (соединив данные

точки линией), не отрывая карандаша от бумаги и не проходя никакую линию дважды.

ровно один раз через каждую вершину.

Название произошло от задачи «Кругосветное

путешествие», придуманной Гамильтоном:

названия столиц различных стран) по одному разу и вернуться в

исходную точку.

Это плоская укладка додэкаэдра - многогранника, гранями которого служат 12 правильных пятиугольников; у него 20 вершин и 30 ребер; вершины и ребра додекаэдра составляют некоторый плоский граф

(n3) выполняется условие

для  v V.
Тогда граф G является гамильтоновым.

Доказательство:
Заметим следующее. Если к любому графу G добавить некоторое количество новых вершин, соединяя каждую из них с каждой вершиной графа, то получим гамильтонов граф G/.
Пусть добавили к графу минимальное число k новых вершин, k>0, после чего граф стал гамильтоновым.

где viV, w – одна из новых вершин.
Следовательно, v2

не является смежной с v1 в графе G/, поскольку тогда можно не использовать вершину w, что противоречило бы минимальности числа k.
Далее, пусть вершина v2/ смежная с v2, а v1/ - смежная с v1. Тогда v2/ не может следовать за v1/ в цикле.
Действительно, в этом случае цикл v1, w, v2,…, v1/, v2/ ,…, v1 можно заменить на
v1, v1/,…, v2, v2/ ,…, v1 и снова высвободить вершину w.

не меньше числа вершин, смежных с v1, поскольку на гамильтоновом

цикле за любой вершиной, смежной с v1, следует вершина не смежная с v2.
Число вершин, смежных с v1, не меньше, чем (n/2)+k, то же и для вершины v2.
Далее, поскольку любая вершина графа G/ является либо смежной, либо не смежной вершине v2, то значит общее число вершин n+k не меньше, чем

Полученное противоречие показывает, что k=0, т.е. Исходный граф гамильтонов.