На рисунке представлены четыре графа. Задача состоит в том, чтобы найти среди них те, которые имеют эйлеров цикл. Эйлеров цикл — это такой цикл в графе, который проходит через каждое ребро ровно один раз.
Чтобы граф имел эйлеров цикл, каждая вершина графа должна иметь четную степень, то есть от каждой вершины должно исходить четное количество ребер.
Давайте посмотрим на каждый граф:
а) В этом графе каждая вершина соединена с каждой, это полный граф для 10 вершин и все вершины имеют степень 9 (нечетное количество), значит, данный граф не имеет эйлерова цикла.
б) Каждая вершина в этом графе также имеет степень, равную 7 (нечетное количество), следовательно, в нем нет эйлерова цикла.
в) В этом графе каждая вершина соединена с каждой (за исключением вершин на "основании" пятиугольника), вершина s находится в центре и имеет степень 5 (нечетное число ребер), что выключает этот граф из кандидатов на наличие эйлерова цикла.
г) Наконец, в графе г) каждая вершина имеет степень 2 (четное количество ребер), и этот граф образует простой цикл. Значит, он имеет эйлеров цикл.
Таким образом, эквивалентный эйлеров цикл имеет граф под буквой г).
