В материале [https://dzen.ru/a/Y7lpcpvRNhni1D-y?share_to=link] рассматривались циклы Эйлера и собственные пути Эйлера, определяемые для неориентированного графа. В текущем материале рассмотрим циклы Эйлера для ориентированного графа.
Определение. Пусть G (V, E) − ориентированный граф. Цикл, который включает все ориентированные рёбра и вершины графа G, называется ориентированным эйлеровым циклом. Если это условие выполняется, говорят, что граф G имеет ориентированный эйлеров цикл.
Теорема. Ориентированный граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждой вершины совпадает со степенью её выхода.
Рассмотрим несколько примеров.
Пусть дан ориентированный граф G1:
Ориентированный граф G1 состоит из 6 вершин, соотнесённый граф (т.е. неориентированный граф, соответствующий заданному ориентированному графу G1) является связным, следовательно, и ориентированный граф G1 связен. Внимательно рассмотрев каждую вершину ориентированного графа G1 можно сделать вывод, что степень схода каждой вершины равна степени его выхода, например, вершина f имеет степень входа, равную двум (от вершин b и d) и степень выхода, равную двум (к вершинам c и e).
Приведём один из вариантов эйлерова цикла для ориентированного графа G1:
Пусть дан ориентированный граф G2:
Ориентированный граф G2 – связный, т.к. его соотнесённый связный.
Вершины a, b, e, i, j в соотнесённом графе имеют равную степень, равную 4, в ориентированном графе G2 каждая из указанных вершин имеет степень входа и степень выхода, равную двум. Вершины c, d, f, g, h в соотнесённом графе имеют равную степень, равную 2, в ориентированном графе G2 каждая из указанных вершин имеет степень входа и степень выхода, равную одному.
Следовательно, ориентированный связный граф G2 имеет ориентированный эйлеров цикл. Представим его на рисунке ниже:
Пусть дан ориентированный граф G3:
Ориентированный граф G3 является связным, т.к. его соотнесённый неориентированный граф является связным (т.к. существуют неориентированные пути из любой вершины в любую другую в этом графе).
Вершины a, h в соотнесённом графе имеют нечётную степень, равную 3, поэтому в ориентированном графе G3 при любых направлениях никогда степень входа этих вершин не будет совпадать со степенью выхода, следовательно, ориентированный связный граф G3 не имеет ориентированный эйлеров цикл.
В качестве Упражнения предлагается рассмотреть следующие ориентированные графы (будут показаны ниже), для которых приведите свои рассуждения относительно того, имеют ли они эйлеров цикл (если имеют, то запишите его перечнем вершин). Результаты опубликуйте в виде комментария под этой лекцией. Возможно ли добавлением или удалением одного или двух рёбер привести ориентированный граф Вашего варианта, если таковой не имеет эйлерова цикла, к тому, чтобы был эйлеров цикл?