Теория:
Рассмотрим ещё один вид пути в графе и связанный с ним вид графа.
Эйлеровым путём в графе называется путь, который обходит все рёбра связного графа по одному разу.
Граф, в котором существует эйлеров путь, называется эйлеровым графом.
Другими словами, граф, который можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро один раз, называется эйлеровым.
Пример:
Рис. \(1\). Эйлеров граф
Граф на рисунке \(1\) можно нарисовать, проводя карандашом по следующему пути: \(C\) — \(K\) — \(M\) — \(B\) — \(C\) — \(A\) — \(B\). Это не единственный возможный путь.
Важное условие существования эйлерова графа связано с наличием определённого количества нечётных вершин.
Леонард Эйлер в процессе решения задачи о Кёнигсберских мостах сформулировал и доказал теорему.
Теорема. Если в графе существует путь, проходящий через все рёбра ровно по одному разу, то в этом графе не больше двух вершин нечётной степени.
Но вспомним следствие из леммы о рукопожатиях.
Следствие. Число нечётных вершин графа всегда чётно.
Сделаем вывод.
Обрати внимание!
Эйлеров граф может иметь либо две нечётные вершины, либо не иметь их совсем.
В прошлый раз мы говорили про пути в графе. Но иногда важную роль играет и направление этого пути.
Граф называется ориентированным, если указано направление каждого ребра.
Число рёбер, входящих в вершину, называют входящей степенью вершины, а число рёбер исходящих — исходящей степенью вершины.
Пример:
Рис. \(2\). Ориентированный граф
Входящая степень вершины B равна \(2\), исходящая степень вершины A равна \(2\).
Для вершины C входящая степень вершины равна исходящей степени вершины и равна \(1\).
Свойство. В ориентированном графе сумма исходящих степеней всех вершин равна сумме входящих степеней всех вершин и равна числу рёбер.
Пример:
вернёмся к графу на рисунке \(2\) и проверим это свойство.
Сумма исходящих степеней всех вершин, начиная с вершины A, равна:
\(2+1+1+1 = 5\).
Сумма входящих степеней всех вершин, начиная с вершины A, равна:
\(2+1+1+1 = 5\).
Количество рёбер тоже равно \(5\).