3.6
Эйлеровы
графы, критерий эйлеровости
Связный граф
называется эйлеровым,
если на нем существует простой цикл, проходящий через все дуги графа.
Теорема 1. Для того, чтобы конечный связный граф был эйлеровым
необходимо и достаточно, чтобы степени всех вершин были четными.
Связный граф называется квазиэйлеровым,
если на нем существует простая цепь, проходящая через все дуги графа.
Теорема 2. Для того, чтобы конечный связный граф был квазиэйлеровым,
необходимо и достаточно, чтобы степени всех вершин были четными числами или
степени всех вершин, за исключением ровно двух, были четными числами, причем в
первом случае эйлерова цепь является эйлеровым циклом, а во втором случае эйлерова
цепь начинается в одной из вершин нечетной степени, а заканчивается в другой
вершине нечетной степени.