Лекция: Теорема 1

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

Теорема 2

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

Теорема 3

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

Теорема 4

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

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

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

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

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

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

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

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

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

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

n – m + r = 2,

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

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

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

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

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

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

d(G) £ 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{8,2}

{7,2}

{7,5}

{5,2}

.

Шаг 3.

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

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

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