Как применяется теорема Эйлера для обхода графов без повторов?

Теорема Эйлера позволяет определить, когда в графе существует путь (или цикл), при котором каждое ребро используется ровно один раз. en.wikipedia.org Такой обход называется эйлеровым циклом или обходом Эйлера. en.wikipedia.org

Теорема гласит: эйлеров цикл существует тогда и только тогда, когда граф связный и степени всех вершин чётны. ru.algorithmica.org

Доказательство: если взять эйлеров цикл и ориентировать все его рёбра в порядке обхода, то из каждой вершины будет выходить столько же рёбер, сколько входить. ru.algorithmica.org Значит, степень у всех вершин исходного неориентированного графа была чётной. ru.algorithmica.org

Если в графе есть вершины с нечётной степенью, то, например, если их ровно две, можно соединить их ребром, построить эйлеров цикл, а затем удалить это ребро из цикла. ru.algorithmica.org Если правильно сдвинуть этот цикл, получится эйлеров путь. ru.algorithmica.org Если нечётных вершин больше двух, то построить эйлеров путь не получится. ru.algorithmica.org

Пользователь

Время добавления