3.5. Эйлеровы и гамильтоновы графы

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

Связный граф G называется эйлеровым (см. рис. 7), если существует замкнутая цепь, проходящая через каждое его ребро только один раз. Такая цепь называется эйлеровой цепью. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым (см. рис. 8). На рис.9 приведен пример не эйлерова графа.

Рис.7. Эйлеров граф Рис.8. Полуэйлеров граф Рис.9. Не эйлеров граф