Что такое эйлеров цикл

Во второй части параграфа 3 было показано, что все $(u,v)$-цепи $n$-вершинного
графа, если таковые существуют, можно найти при помощи решений уравнения $BX = F_{{u,v}}$ над полем по модулю 2.

Уравнение $BX = F$ впредь будем называть графовым уравнением,
если: $B$ матрица инцидентности $(n,m)$-графа, $X$ — $m$-мерный
(0,1)-столбец, а $F$ — $n$-мерный (0,1)-столбец с четным числом единиц. При этом
решение ищется над полем по модулю 2.

Если $F$ столбец с нечетным числом единиц, то $rank(B,F) > rankB$ и графовое
уравнение неразрешимо, поэтому этот случай исключается из рассмотрения.

Если $rankB = n – 1$, то графовое уравнение разрешимо при любом столбце $F$ с
четным числом единиц, и граф в этом случае называется связным.

При $m ge n$ решениями однородного графового уравнения будут циклы или совокупности циклов.

Пусть над полем по модулю 2 $rankB = n – 1$, т.е. соответствующий
$(n,m)$-граф связный. Рассмотрим, при каких условиях на матрицу $B$ однородное
графовое уравнение $BX = 0$ имеет решение $X = J$, где $J$ столбец из единиц.
Поскольку равенство $BJ = 0$ означает, что столбец строчных сумм матрицы $B$
над полем по модулю два равен нулю, то каждая строчная сумма над кольцом
целых чисел (строчная сумма $ approx $ степень вершины) есть число четное.
Таким образом, однородное графовое уравнение $BX = 0$ имеет решение $X = J$
тогда и только тогда когда степень каждой вершины графа с матрицей
инцидентности $B$ — четная. В случае связного графа решение $X = J$
соответствует в графе одной замкнутой цепи, или, по-другому, граф является
так называемым эйлеровым циклом.

Поясним, что такое эйлеров цикл. Эйлеров цикл — это такой
граф, рисунок которого на плоскости можно «обвести» карандашом, пройдя
через каждую вершину и каждое ребро, причём через каждое ребро ровно один
раз, не отрывая карандаша от плоскости. Эйлеров цикл называют также
эйлеровым графом.

Из определения эйлерова графа следует, что для его матрицы смежности
выполняется условие $BJ = 0$ (каждое ребро входит в решение ровно один
раз), т.е. $BJ = 0$ является необходимым условием, чтобы
граф с матрицей инцидентности $B$ был эйлеровым.

Покажем теперь, что для связного графа это условие является и
достаточным. Для этого отметим вначале, что для связного
графа решение однородного графового уравнения $X = J$ показывает, что граф
есть цикл (замкнутая цепь).

Лемма. Любой цикл, разбивается на совокупность простых циклов.

Замечание 1. Напомним, что «разбиение» множества на подмножества
означает представление множества в виде объединения непересекающихся
подмножеств, т.е. подмножеств, не имеющих общих элементов. Если граф
рассматривается как множество ребер, то разбиение множества ребер графа,
означает представление графа в виде объединения непересекающихся
подмножеств. Таким образом, утверждение леммы означает, что цикл можно
представить в виде объединения простых циклов, не имеющих общих элементов
(ребер). На рисунке цикла-графа простые циклы, не имеющие общих ребер,
объединение которых и составляет искомый цикл-граф, обязательно будут
пересекаться в некоторых вершинах. Дело в том, что на рисунке мы
рассматриваем граф как пару множеств — множества вершин и множества ребер.
Когда же мы ведем речь о цепях (открытых и замкнутых), мы рассматриваем граф
в пределах этого параграфа только как множество ребер.

Доказательство. Отметим, что из определения цикла как замкнутой
цепи следует, что входящие в формулировку леммы простые циклы не должны
иметь общих ребер (цепь состоит из различных ребер, § 3 часть 1). Далее,
цикл является связным графом — любые его две различные вершины связаны
простой цепью. После сделанных замечаний, доказательство леммы сводится к
построению какой-либо совокупности простых циклов, не имеющих общих ребер,
включающей все ребра цикла. По-другому, доказательство сводится к
возможности разбиения множества ребер цикла, на непересекающиеся
подмножества, являющиеся простыми циклами.

Пусть рассматриваемый цикл связывает $n$ вершин и состоит из $m$ ребер ($m ge n$).
Тогда его матрица инцидентности $B$ имеет размерность $n$ на $m$ и ранг $n-1$.
Цикломатическое число $k$ нашего графа-цикла будет равно $m-n+1$ и $k ge 1$.
Следовательно, фундаментальная система решений однородного графового
уравнения $BX = 0$ будет состоять из $k$ линейно независимых над полем по
модулю 2 решений $X_1, X_2, …, X_k$, соответствующих простым циклам. Это
значит, что любое конкретное решение однородного графового уравнения
является единственным образом определяемой линейной комбинацией
$varepsilon _1 X_1 + varepsilon _2 X_2 + … + varepsilon _k X_k$. В частности,
существующее для нашего случая ($B$ матрица цикла) решение $X = J$, будет
представляться как $J = X_1 + X_2 + … + X_k$. Это становится очевидным,
если решения фундаментальной системы строить, так как это показано во второй
части параграфа 3. А именно, запишем однородное графовое уравнение в виде
$B_1 x_1 + … + B_{n – 1} x_{n – 1} + B_n x_n + … + B_m x_m = 0$. Не
нарушая общности рассуждений, будем считать, что столбцы $B_1 ,…,B_{n – 1}$
составляют максимальную линейно независимую совокупность столбцов матрицы
$B$ над полем по модулю 2. Тогда переменные $x_n, …, x_m$ будем считать
независимыми переменными, а переменные $x_1, …, x_{n – 1}$ — зависимыми,
т.е. определяемыми после того, как независимым переменным приданы конкретные
значения. Придавая последовательно одной независимой переменной значение 1,
а остальным — 0, мы получим $k$ наборов значений независимых переменных,
каждому из которых будет соответствовать конкретный набор из ($n – 1$)-ой
зависимых переменных. Так, если независимой переменной $x_j $ ($j in {n,n + 1,…,m})$
мы придаем значение 1, а остальным — значение 0, то набор
зависимых переменных определяется как единственное решение системы
$B_1 x_1 + … + B_{n – 1} x_{n – 1} = B_j $. Объединение набора значений независимых
переменных с соответствующим ему набором значений зависимых переменных дает
нам одно решение фундаментальной системы. Таким образом мы и получаем
систему линейно независимых решений $X_1, X_2, …, X_k$, называемую
фундаментальной. Равенство $J = varepsilon _1 X_1 + varepsilon _2 X_2 + … + varepsilon _k X_k$
возможно, только если $varepsilon _1 = varepsilon _2 = … = varepsilon _k = 1$ (необходимое условие).
Но поскольку мы знаем, что графовое уравнение $BX = 0$ для цикла имеет решение
$X = J$, то действительно $J = X_1 + X_2 + … + X_k $.

Единицы, соответствующие различным независимым переменным, стоят в
столбцах-решениях $X_j $ ($j = 1,2,…,k$) на разных местах по одной 1 в
каждом решении. Единица, соответствующая какой-то $i$-ой зависимой переменной
($i in {1,…,n – 1}$), может стоять на $i$-ом месте, в нескольких столбцах,
но обязательно в нечетном количестве столбцов-решений. Такую единицу будем
называть кратной для данной системы решений. Разобьем на пары столбцы с
единицей на $i$-ом месте, при этом одному столбцу с единицей на $i$-ом месте не
найдется пары. Заменим каждую пару столбцов с единицей на $i$-ом месте их
суммой. В полученных столбцах-суммах, каждый из которых тоже будет решением,
на $i$-ом месте будут стоять нули. В модернизированной системе решений, только
у одного решения будет 1 на i-ом месте. То есть переходом к
модернизированной системе мы избавились от одной кратной 1. Беря теперь за
основу модернизированную систему решений, мы можем избавиться от одной
кратной 1 этой системы. Продолжая этот процесс, мы придем к совокупности
решений, которые будут простыми циклами, без кратных единиц. Другими словами
мы представим решение $J$ в виде $J = {X}_1 + {X}_2 + … + {X}_l$, где любые
два решения ${X}_i $ и ${X}_j $ ($i ne j$) не имеют общих единиц, т.е.
единиц расположенных на одинаковых местах. Тем самым лемма доказана.

Пример.

Рис. 1.

Граф на рисунке 1 — связный, имеет 6 вершин и 8 ребер. Степень каждой его
вершины четная, значит, это цикл. Его цикломатическое число равно $8 – 6 + 1 = 3$.
Следовательно, фундаментальная система решений однородного графового
уравнения состоит из трех решений (трех простых циклов). В то же время легко
видеть, что множество ребер графа разбивается на два простых цикла (граф
представляется в виде объединения двух «непересекающихся» простых циклов):

${{1,3},{3,4},{4,2},{2,1}}$ и
${{3,6},{6,5},{5,2},{2,3}}$.

Отметим, что цикл — это замкнутая цепь, и, следовательно, может быть записан
в виде последовательности смежных ребер. Так граф с рисунка 1 может быть
записан в виде упорядоченной последовательности смежных ребер следующим образом:
${{1,3},{3,6},{6,5},{5,2},{2,3},{3,4},{4,2},{2,1}}$.

Очевидно, что любая запись цепи в виде последовательности смежных ребер
эквивалентна «обводу» рисунка графа-цепи без отрыва карандаша от плоскости
в соответствии с записью ребер в последовательности. Поэтому, кроме факта,
констатированного в лемме, что цикл может быть представлен как объединение
непересекающихся простых циклов, мы должны ещё констатировать возможность
упорядочения ребер исходного цикла в последовательность смежных ребер.

Доказательство возможности упорядочения ребер цепи в упорядоченную
последовательность смежных ребер проводится методом математической индукции
по числу простых не пересекающихся между собой (не имеющих общих ребер)
простых циклов, на которые разлагается исходный цикл (лемма).

Будем считать, что мы умеем упорядочивать ребра в простом цикле. Поэтому,
если исходный цикл есть простой цикл, то доказывать нечего.

В качестве базы индукции рассмотрим случай, когда исходный цикл разлагается
на два простых непересекающихся цикла. Считая, что ребра в простых циклах
уже упорядочены, приступим к упорядочиванию ребер исходного цикла. Для этого
выберем какое-нибудь ребро, принадлежащее первому циклу, и будем
«двигаться» по упорядоченной последовательности ребер этого цикла, пока не
встретим ребро, которое будет смежным некоторому ребру второго цикла. Такое
ребро обязательно существует, поскольку исходный цикл связный граф. Далее,
выписываем все ребра второго цикла, начиная с упомянутого ребра. Последнее
ребро второго цикла в этой записи будет смежным с тем ребром первого цикла,
с которого мы покинули первый цикл. Следовательно, далее продолжаем движение
по первому циклу. Наше «движение» по циклам и соответствует упорядочению
ребер исходного цикла, разбитому на два простых цикла, в последовательность
смежных ребер. Таким образом, случай разбиения исходного цикла на два
простых цикла действительно может служить базой индукции.

Предположим, что мы умеем упорядочить ребра исходного цикла в
последовательность смежных ребер, если исходный цикл разбивается на $k$ простых
циклов, где $2 le k

Рассмотрим теперь случай, когда исходный цикл, который обозначим через $Z$,
разбивается на $l$ непересекающихся простых циклов ${X}_1 ,{X}_2 ,…,{X}_l$
(будем отождествлять запись циклов с записями соответствующих решений
однородного графового уравнения). Не нарушая общности рассуждений, будем
считать, что ребро, с которого мы начинаем упорядочение, принадлежит циклу
${X}_1$. Тогда граф, образованный объединением циклов ${X}_2 ,…,{X}_l$
может быть как связным, так и несвязным. Ясно, что этот граф может быть
представлен в виде $k$ компонент связности $Z_1 ,…,Z_k $, где $1 le k le l – 1$.
Каждая компонента связности, очевидно, будет циклом. Ребра каждой
компоненты связности, в силу индукционного предположения, упорядочим в
последовательности смежных ребер. Каждая компонента связности будет иметь
смежные ребра c ${X}_1$ в силу связности Z. Номера компонент связности
можно упорядочить по тому, в какой очередности при движении по циклу ${X}_1$
в них впервые встречаются смежные ребра, как принадлежащие циклу ${X}_1$,
так и соответствующей компоненте связности. Тогда упорядочивание ребер цикла
$Z$ будет выглядеть следующим образом. Начиная с выбранного ребра (задающего и
направление) мы движемся по циклу ${X}_1$, пока не достигнем цикла $Z_1$.
Переходим на цикл $Z_1$ и обходим все ребра этого цикла, пока не вернемся
снова на цикл ${X}_1$. Продолжаем прерванное движение по циклу ${X}_1$,
пока не достигнем цикла $Z_2$. Переходим на цикл $Z_2$ и обходим все ребра
этого цикла, пока не вернемся снова на цикл ${X}_1$. Продолжая движение
таким образом мы обойдем все ребра цикла $Z$ и вернемся к исходному ребру.
Другими словами, мы упорядочим все ребра цикла $Z$ в последовательность смежных
ребер. Тем самым мы доказали, что условий четности степеней вершин графа и
его связности достаточно, чтобы граф был эйлеровым.

Следствие. Любой связный граф $Gamma $, не являющийся эйлеровым, можно разбить на $k$ открытых цепей,
где $2k$ равно числу вершин графа с нечетными степенями.

Доказательство. Раз $Gamma$ связный и не является эйлеровым, то он имеет
вершины с нечетными степенями. Как было показано ранее, в любом графе число
вершин с нечетными степенями — четно. Пусть число вершин с нечетными
степенями равно $2k$, где $k ge 1$. Возьмем любые две вершины графа $Gamma$
из числа 2$k$ вершин с нечетными степенями. Построим простую цепь, соединяющую
первую выбранную вершину со второй. Если цепь проходит через некоторое число
вершин с нечетными степенями, то выберем в качестве второй концевой вершины
ближайшую к первой вершине. Это показывает, что мы всегда можем выбрать две
вершины с нечетными степенями таким образом, что соединяющая их простая цепь
$Gamma _1$ будет ребром или «проходить» только через вершины с четными
степенями. Удалим теперь из графа цепь $Gamma _1$, соединяющую выбранные
вершины (т.е. удалим все ребра цепи $Gamma _1$ и все вершины графа $Gamma$,
являющиеся одновременно и вершинами цепи $Gamma _1$ и имеющими степень 2).
У оставшегося подграфа $tilde {Gamma }$ число вершин с нечетными
степенями будет $2(k – 1)$, т.е. на две единицы меньше. Граф $tilde {Gamma}$
может быть несвязным. Каждая компонента связности может содержать только
четное число вершин с нечетными степенями. Поэтому мы можем выбрать пару
вершин с нечетными степенями, принадлежащую одной компоненте связности, так,
чтобы соединяющая их простая цепь $Gamma _2$ была ребром или проходила
через вершины с четными степенями. Очевидно, что цепи $Gamma_1$ и $Gamma_2$
не имеют общих ребер. Продолжая эту процедуру дальше, мы выделим в графе $Gamma$ $k$ открытых цепей
$Gamma _1, …, Gamma _k$ (как подмножеств ребер), соединяющих различные пары вершин с нечетными степенями и попарно не
пересекающихся (не имеющих общих ребер). Удалим из графа $Gamma$
совокупность цепей $Gamma _1, …, Gamma _k$ и обозначим оставшийся подграф через
$hat{Gamma}$. Из способа построения цепей $Gamma _1, …, Gamma _k следует, что все вершины графа
$hat{Gamma}$ будут иметь четную степень. Следовательно, множество ребер
$hat{Gamma}$ разбивается на некоторое множество простых циклов. В итоге
все множество ребер графа $Gamma$ разбивается на $k$ простых открытых цепей
$Gamma _1, …, Gamma _k$ и некоторое множество простых циклов. При этом
каждый цикл имеет общую вершину, по крайней мере, с одной из цепей, в силу
связности графа $Gamma$. Присоединяя цикл к одной из цепей, с которой он
имеет общую вершину, мы и получим разбиение всего множества ребер на $k$
открытых цепей. Что и требовалось доказать.

Замечание 2 (как следствие следствия). Если связный граф $Gamma$
имеет только две вершины с нечетными степенями, то рисунок графа на
плоскости можно обвести карандашом, не отрывая его от плоскости, начав
движение в одной из «нечетных» вершин и закончив в другой нечетной вершине
и проходя по каждому ребру только один раз. Невозможность сделать подобное,
в случае если граф имеет более одной пары вершин с нечетными степенями,
сформулирована (и доказана) уже в учебнике по математике для 5-го класса в
форме: «Линию нельзя обвести одним росчерком, если она содержит более двух
узлов, в которых сходится нечетное число отрезков».

Замечание 3. Принято считать, что теория графов берет свое начало с
задачи Эйлера о кёнигсбергских мостах, которая может быть пояснена как
задача — можно ли обвести линию (граф, моделирующий задачу, изображенный на
рисунке 2) не отрывая карандаша от рисунка и проходя по каждому отрезку только один раз?

По сути, на рисунке изображен не граф, а так называемый мультиграф, который
допускает соединение узлов (вершин) кратным числом отрезков (ребер).

Интересно, что все изложенное о цепях переносится с графов на мультиграфы
почти без изменений. Достаточно в определении матрицы инцидентности
допустить наличие равных столбцов, соответствующих кратным ребрам. Проверка
этого утверждения представляет неплохое упражнение-исследование для
обучающихся.