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

Эйлеров граф

Эйлеров путьв графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

Эйлеров цикл — это эйлеров путь, являющийся циклом.

Эйлеров граф — граф, содержащий эйлеров цикл.

Эйлеров путь в графе существует тогда и только тогда, когда это число равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.

Гамильтонов граф

Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.

Гамильтонов путь — путь, содержащий каждую вершину графа ровно один раз.

Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.

Эйлеров граф

Гамильтонов граф

Условие Дирака

Условие Оре

Условие Дирака

Пусть p — число вершин в данном графе; если степень каждой вершины не меньше p/2, чем , то граф называется графом Дирака. Граф Дирака — гамильтонов.

Условие Оре

p — количество вершин в данном графе. Если для любой пары несмежных вершин x,y выполнено неравенство d(x) + d(y) >= p , то граф называется графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Граф Оре — гамильтонов.