Эйлеров и Гамильтонов графы
Эйлеров граф
Эйлеров путьв графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров граф — граф, содержащий эйлеров цикл.
Эйлеров путь в графе существует тогда и только тогда, когда это число равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
Гамильтонов граф
Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.
Гамильтонов путь — путь, содержащий каждую вершину графа ровно один раз.
Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.
Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.
Условие Дирака
Пусть p — число вершин в данном графе; если степень каждой вершины не меньше p/2, чем , то граф называется графом Дирака. Граф Дирака — гамильтонов.
Условие Оре
p — количество вершин в данном графе. Если для любой пары несмежных вершин x,y выполнено неравенство d(x) + d(y) >= p , то граф называется графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Граф Оре — гамильтонов.