Эйлеровы и гамильтоновы графы.
Эйлеровы графы
Замечание 1. Теорема справедлива также для мульти- и псевдографов.
Замечание 2. Связный граф эйлеров тогда и только тогда, когда существует разбиение множества его ребер Е(G) на простые циклы.
Замечание 3. Если в связном графе существует ровно две вершины нечетной степени, то эйлерова цикла не существует, но существует эйлерова цепь, которая начинается в одной вершине нечетной степени, а заканчивается -- в другой (доказательство аналогично доказательству теоремы Эйлера). Если число вершин нечетной степени равно 2k, то нетрудно показать, что граф покрывается (т. е. является обьединением) k реберно-непересекающихся цепями.
Ориентированный граф называется эйлеровым, если в нем существует ориентированный эйлеров цикл, т. е. цикл, проходящий по всем дугам с соблюдением ориентации. Легко видеть, что для ориентированных графов, справедлива
Теорема. Связный ориентированный граф является эйлеровым тогда и только тогда, когда для любой его вершины v полустепень исхода равна полстепени захода: deg+v = deg-v.
