Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом.
Граф имеет эйлеров цикл (т.е. является эйлеровым) тогда и только тогда, когда он связный и не имеет вершин с нечетной локальной степенью.
Эйлерова цепь – незамкнутая цепь, проходящая через каждое ребро графа только один раз. Полуэйлеров граф – граф, имеющий эйлерову цепь. Граф имеет эйлерову цепь (то есть является полуэйлеровым) тогда и только тогда, когда он связный и ровно две его вершины имеют нечетную локальную степень.
Гамильтоновы циклы
Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом.
Гамильтонова цепь – незамкнутая цепь, проходящая через каждую вершину графа только один раз.
Контрольные вопросы
1. Является ли последовательность aecfbdafc маршрутом? цепью? простой цепью?
2. Является ли последовательность dabcfbed циклом? простым циклом?
3. Является ли следующий граф Эйлеровым? Почему?
4. Приведите граф с шестью вершинами, который имеет гамильтонов цикл, но не имеет эйлерова цикла.
5. Приведите граф с шестью вершинами, который имеет эйлеров цикл, но не имеет гамильтонова цикла.
