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

Эйлер (1736): Задача о Кенигсбергских мостах. На рисунке 4.1 изобра-жена часть реки Прейгель, находящейся в Кенигсберге, ныне - Калининграде. Буква Л обозначает левый берег, П – правый, А и Б – острова.

Требуется найти маршрут пешехода, проходящий через все мосты, через каждый мост пешеход должен пройти ровно один раз. Эйлер доказал, что эта задача не имеет решений.

Рис. 4.1. Схема мостов и соответствующий ей граф

Обобщим определение простого графа.

Определение 1. Графом называется тройка (V, E, a), состоящая из множеств V, E и функции a: E ®P₂(V), сопоставляющей каждому eÎE неупорядоченную пару {u,v}. Элементы из E называются ребрами, элементы из V – вершинами. Если a(e)={u,v} вершины u и v называются концами ребра e. В этом случае u и v называются смежными вершинами и инцидентными ребру e. Если концы ребра e равны, то ребро e называется петлей. Степенью вершины v называется число инцидентных ей ребер. Ребро, являющееся петлей, учитывается два раза. В частности, петля дает степень 2. Для графа, соответствующего схеме Кенигсбергских мостов, степени вершин равны 3, 3, 3 и 5. Путем в графе называется последовательность вершин и ребер v₀g₁v₁g₂v₂ ∙∙∙ v_n-1g_nv_n, таких что v_i и v_i+1 инцидентны ребрам g_i+1, для всех iÎ{1,2, ∙ ∙ ∙, n}. Граф, допускающий путь, не содержащий кратных ребер и содержащий все ребра, называется эйлеровым. Такой путь тоже называется эйлеровым.

На рис. 4.1 справа изображен граф, ребра которого соответствуют мостам, а вершины – частям суши.