Ядро графа

С D

Эйлеров граф.

Эйлеровой цепью называется цепь, проходящая по всем ребрам графа.

Эйлеровым циклом называется эйлеровая цепь, начинающаяся и заканчивающаяся в одной вершине.

Эйлеровым графом называется граф, содержащий Эйлеров цикл.

ТЕОРЕМА: Для того чтобы связанный граф был Эйлеровым, необходимо и достаточно, чтобы степени всех вершин были четны

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

А

B

Рис. 3.5 Граф «Кенигсбергские мосты»

Вершины графа (A, B, C, D) имеют степени:

(3.3)

Тогда в соответствии с теоремой Эйлера данный граф не является Эйлеровым. А это означает, что нельзя обойти все мосты г. Кенигсберга строго по одному разу, начав и закончив путь в одной точке суши.

Следствие из ТЕОРЕМЫ: Для того чтобы граф содержал Эйлеровую цепь, необходимо и достаточно, чтобы две вершины имели нечетную степень. При этом в одной из вершин цепь будет начинаться, в другой – заканчиваться.

Дата добавления: 2014-01-04