Теорема 1

Почти нет эйлеровых графов.

Теорема 2

Почти все графы связанные.

Теорема 3

Почти все графы гамильтоновы.

Теорема 4

Диаметры почти всех графов равны 2.

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

	Определения

Теорема

Пусть задан граф G=(V,E). Пусть каждой вершине vi из V сопоставлена точка а_i в некотором евклидовом пространстве, причем а_i ≠а_j при i≠j. Пусть каждому ребру e=(v_i, v_j) из E сопоставлена непрерывная кривая L, соединяющая точки а_i и a_j и не проходящая через другие точки a_k. Тогда если все кривые, сопоставленные ребрам графа, не имеют общих точек, кроме концевых, то это множество точек и кривых называется геометрической реализацией графа G.

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

		Пример

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

Планарность графа часто легче доказать, чем не планарность:

· для того, чтобы доказать планарность графа, достаточно найти его графическое изображение на плоскости без пересечения ребер;

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

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

Одна из областей всегда неограничена (является частью бесконечной плоскости). Эта область называется внешней.

Пример

R6 – остальная часть бесконечной плоскости

Рис.2.13.2. Граф, его карта и области (R1 –R6)

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

Для любого связного графа G, являющегося плоским, справедливо соотношение:

n – m + r = 2,

где n – число вершин, m – число ребер, r – количество областей графа.

Область 1 - внешняя

Формула Эйлера = n-m+r = 4-6+4 = 2

Рис.2.13.3. Пример планарного графа

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

· -полносвязный граф К₅ не планарен;

· -двудольный граф К₃,₃ не планарен.

Теорема

2. С графом K_3,3 связана следующая старинная задача: Есть три колодца и три дома. Хозяева домов в большой вражде. Можно ли проложить дорожки от каждого дома к каждому колодцу, чтобы они не пересекались?

Планарный граф с числом вершин n 3 имеет m 3n-6 ребер.

Каждый планарный граф G=(V,E) имеет минимальную степень вершин не более пяти, т.е.

d(G) £ 5

Максимальным планарным графом явялется такой планарный граф, добавление к которому любого нового ребра:

· делает граф планарным;

· или такая операция невозможна, как в случае с полными графами.

Максимальный планарный граф с числом вершин n имеет m=3n-6 ребер.

	Определение

Подразбиением графа G=(V,E) является любой граф, полученный из G заменой его ребер путем, длиной ко крайней мере один.

Граф является планарным тогда и только тогда, когда он не содержит в качестве подразбиения ни граф К₅, ни граф К₃,₃.

	Определение

Операция стягивания в графе G – удаление ребра и отождествление его концевых вершин.

	Теорема Вагнера

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

	Класс сложности

Проблема планарности графа относится к Р-классу.

Имеется несколько алгоритмов, определяющий планарен ли граф за линейное время (основаны, как правило, на теоремах Куратовского и Вагнера).

	Алгоритм определения планарности гамильтонова графа (метод цикла)

1. В графе определяется гамильтонов цикл С;

2. Перечисляются оставшиеся ребра графа и делятся на два раздельных множества А и В, где:

· А-множество ребер, которые могут быть нарисованы внутри цикла С без пересечения;

· В -множество ребер, которые могут быть нарисованы вне цикла С без пересечения.

Пример

Шаг 1. Находим гамильтонов цикл С:

{1,2,3,4,5,6,7,8,1}

Шаг 2. Начинаем перечисление ребер:

{8,2}

{7,2}

{7,5}

{5,2}

{4,2}

.

Шаг 3.

{1,3}- пересекается с ребрами А

{8,3}- пересекается с ребрами А

{7,4}- пересекается с ребрами А

	Граф планарен