В лекции [https://dzen.ru/a/YnNaAtX5fBlYfXc4?share_to=link] сформулировано теоретико-множественное представление неориентированного графа. В текущей лекции представим пару важных определений, а также сформулируем теорему, которая позволяет легко определять, существуют ли у заданного неориентированного графа циклы и пути Эйлера.
Перейдём к определениям и примерам.
Определение. Пусть G (V, E) – неориентированный граф. Цикл, который включает все рёбра и вершины графа G, называется эйлеровым циклом. Если это условие выполняется, говорят, что граф G имеет эйлеров цикл.
Или, говоря другими словами, эйлеров цикл – это цикл графа, проходящий через каждое ребро (дугу) графа ровно по одному разу и заканчивающийся в начале пути.
Пример неориентированного графа, пусть будет граф G1.
Теорема 1. Неориентированный граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая его вершина имеет четную степень.
Рассмотрим несколько примеров.
Пусть дан неориентированный граф G2:
Неориентированный граф G2 состоит из 12 вершин, шесть из которых имею чётную степень, равную двум (a, b, e, h, k, l), а шесть других имеют чётную степень, равную четырём (c, d, f, g, I, j), следовательно, неориентированный граф G2 имеет эйлеров цикл. Например, это эйлеров цикл adegkjlihfbcdgjifca с началом и концом в вершине a или, как показано на рисунке ниже, это может быть эйлеров цикл с началом и концом в вершине c.
Пусть дан неориентированный граф G3:
Неориентированный граф G3 состоит из 6 вершин, при этом вершины a и d имеют нечётные степени, поэтому неориентированный граф G3 не имеет эйлерова цикла.
Определение. Пусть G (V, E) – неориентированный граф. Путь, который включает каждое ребро графа G только один раз называется эйлеровым путем. В этом случае говорят, что граф G имеет эйлеров путь.
В случае, когда эйлеров путь не является эйлеровым циклом, то такой путь называется собственным эйлеровым путем.
Пример:
Пусть дан неориентированный граф G4:
Неориентированный граф G4 состоит из 4 вершин, при этом вершины c и d имеют нечётные степени, поэтому неориентированный граф G4 не имеет эйлерова цикла. Однако можно организовать эйлеров путь, который будет являться собственным эйлеровым путём, т.к. не является эйлеровым циклом. Например, как показано на рисунке ниже:
Теорема 2. Неориентированный граф (неориентированный мультиграф или неориентированный псевдограф) имеет собственный эйлеров путь тогда и только тогда, когда он связный и ровно две его вершины имеют нечетную степень.
Рассмотрим несколько примеров.
Пусть дан неориентированный граф G5:
Неориентированный граф G5 является связным.
Вершины a, c, d, f имеют чётную степень, равную двум.
А две вершины b, e имеют нечётную степень, равную трём.
Следовательно, граф G5 имеет собственный эйлеров путь, вариант которого представим на следующем рисунке:
Пусть дан неориентированный граф G6:
Неориентированный связный граф G6 не имеет собственного пути Эйлера, поскольку имеет более двух вершин с нечётной степенью (нечётные вершины a, b, e и f). Эйлерова цикла неориентированный граф G6 также не имеет.
В качестве Упражнения предлагается в вопросно-ответной системе Wolfram|Alpha ввести в командную строку команду (можно вместо 6 вершин выбрать любое число, не меньшее 3):
random graph on 6 vertices
Вопросно-ответная система Wolfram|Alpha сгенерирует произвольный граф, для которого приведите свои рассуждения относительно того, имеет ли такой сгенерированный граф эйлеров цикл или собственный эйлеров путь (если имеет, то запишите его перечнем вершин). Результаты опубликуйте в виде комментария под этой лекцией.
Примеры сгенерированных неориентированных графов:
