Эйлеровы цепи и циклы

Пусть G – псевдограф.

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

Определение 11.2. Псевдограф G называется эйлеровым, если он содержит эйлеров цикл.

Заметим, что эйлеров псевдограф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.

Теорема 11.1. Для того чтобы связный псевдограф обладал эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были чëтными. 

Теорема 11.2. Для того чтобы связный псевдограф обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечëтной степени. 

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

Пример 11.1 (решение задачи о кëнигсбергских мостах). Поставим в соответствие схеме центральной части города Кëнигсберг, приведëнной на

рис. 1, мультиграф G, изображëнный на рис. 20, в котором каждой части суши соответствует вершина, а каждому мосту – ребро, соединяющее соответствующие вершины. На языке теории графов задача формулируется следующим образом: найти эйлеров цикл в мультиграфе G.