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

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

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

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

Эйлеровой цепью называется цепь, которая содержит все ребра данного графа G , но имеющая различные начало v_i и конец v_j.

Чтобы в графе существовала эйлерова цепь, необходимы его связность и четность степеней всех вершин, кроме начальной v_i и конечной v_j. Последние две вершины должны иметь нечетные степени: из v_i мы лишний раз выходим, а в v_j лишний раз входим.

В орграфе вместо эйлерова цикла рассматривают эйлеров контур, вместо эйлеровой цепи – эйлеров путь.

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