Эйлеров цикл (цепь) — цикл (цепь), содержащий все ребра графа %%G%% и притом по одному разу. Если граф содержит эйлеров цикл, то он называется эйлеровым.
К задачам на эйлеровы графы относятся головоломки, в которых требуется начертить на плоскости одним росчерком замкнутые кривые, обводя каждый участок только один раз. На практике же эйлеровым графом может быть план выставки, позволяющий расставить указатели маршрута таким образом, чтобы посетитель смог пройти по каждому залу в точности по одному разу.
Гамильтонов цикл (цепь) — цикл (цепь), проходящий через все вершины графа %%G%% и притом по одному разу. Если граф содержит гамильтонов цикл, то он называется гамильтоновым.
Гамильтоновы цепь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.
Граф, не содержащий циклов, называется лесом. Связный лес называется деревом.
| Связность графа | Двенадцатое практическое занятие: маршруты, цепи, циклы, связность |