3.1. Эйлеровы графы

Эйлеровой цепью в графе G называется замкнутая цепь, содержащая все ребра графа G. К открытой эйлеровой цепи относится открытая цепь, содержащая все ребра G. Граф, содержащий эйлерову цепь, называется эйлеровым графом.

Рассмотрим граф, представленный на рис. 3.3, а. Последовательность ребер образует эйлерову цепь в графе следовательно, последний является эйлеровым.

В графе на рис. 3.3, б последовательность ребер образует открытую эйлерову цепь. Однако в графе эйлеровой цепи нет. Следовательно, граф не является эйлеровым.

Неэйлеров граф не обладающий открытой эйлеровой цепью приведен на рис. 3.3, в.

Теперь сформулируем теорему, дающую простую и часто используемую характеризацию эйлеровых графов:

Теорема 3.1. Следующие утверждения эквивалентны для связного графа G:

1. G — эйлеров граф.

2. Степень каждой вершины в графе G четная.

(см. скан)

Рис. 3.3. а — эйлеров граф б — неэйлеров граф , имеющий открытую эйлерову цепь; в — неэйлеров граф не имеющий открытой эйлеровой цепи.

3. G является объединением нескольких реберно-непересекающихся циклов.

Доказательство.

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

Так как G — связный граф и каждая вершина в нем имеет четную степень, то степень каждой вершины в графе G больше 1. Таким образом, в графе О нет висячих вершин. Следовательно, по теореме 2.5 граф G не является деревом. Это означает, что граф G имеет по крайней мере один цикл, например

Рассмотрим граф Так как каждая вершина в графе имеет четную степень, то и каждая вершина, принадлежащая должна иметь четную степень. Однако возможен случай, когда граф — несвязный.

Если граф полностью несвязный, т. е. содержит только изолированные вершины, и утверждение 3 доказано. В противном случае граф имеет по крайней мере один цикл

Рассмотрим граф . Аналогично каждая вершина в графе имеет четную степень. Если граф полностью несвязный, тогда . В противном случае будем повторять эту операцию, пока не получим полностью несвязный граф где циклы графа G, попарно не имеющие общих ребер, Тогда и, следовательно, утверждение 3 доказано.

Пусть G — объединение реберно-непересекающихся циклов Рассмотрим любой из них, например Так как G — связный граф, то должен существовать по крайней мере один цикл, например имеющий общую вершину с циклом Пусть — замкнутая цепь, начинающаяся в вершине их и последовательно проходящая циклы Очевидно, что эта цепь содержит все ребра

Поскольку граф G — связный, цепь должна иметь общую вершину по крайней мере с одним циклом, например отличным от Замкнутая цепь начинающаяся в и последовательно проходящая через содержит все ребра циклов

Будем повторять эту операцию до тех пор, пока не получим замкнутую цепь содержащую все ребра циклов Эта замкнутая цепь и будет являться эйлеровой цепью в графе G. Следовательно, граф G — эйлеров.

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

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

Из утверждения 3 теоремы 3.1 имеем следующее следствие:

Следствие 3.1.1. Каждая вершина эйлерова графа содержится в некотором цикле.

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

Теорема 3.2. Пусть — связный граф с вершинами нечетной

вершиной Поэтому Но тогда . Таким образом, мы имеем что противоречит условию 2. Если из условия 3 не следует условие 4, то существует такое что Тогда Если теперь мы положим то получим Поэтому имеем неравенства, противоречащие условию и Если это не верно, то существует такое t, что . Но тогда , что противоречит условию 4.

Очевидно, если какая-либо графическая последовательность удовлетворяет условиям теоремы 3.4 или следствия 3.4.1, то тем же условиям удовлетворяет любая графическая последовательность, мажорирующая ее.

Условие Хватала — самое сильное из этих пяти условий и вообще из всех подобных условий. Это означает, что если какая-либо графическая последовательность не удовлетворяет условию Хватала, то она мажорируется последовательностью степеней негамильтонова графа [3.1].

Рис. 3.7. Негамильтонов граф.

Хотя в общем случае довольно трудно установить, является ли граф негамильтоновым, в определенных случаях это удается сделать с помощью изощренных методов. Это иллюстрируется в работе [3,6] на следующем примере.

Рассмотрим граф G, представленный на рис. 3.7. Покажем, что он не содержит гамильтонова пути.

Теорема 3.3. Эйлеров граф G является произвольно-эйлеровым из вершины v тогда и только тогда, когда каждый цикл графа G содержит эту вершину.

Доказательство.

Необходимость. Пусть G — произвольно-эйлеров граф из вершины и. Предположим, что в графе G существует цикл С, не содержащий v. Рассмотрим граф Каждая вершина в нем имеет четную степень. Граф G может быть и несвязным. Однако его компонента содержащая вершину у, является эйлеровым графом и содержит все ребра, инцидентные вершине у. Таким образом, в графе G" существует эйлерова цепь Т, начинающаяся и возвращающаяся в вершину у. Эта цепь обязательно состоит из всех ребер, инцидентных вершине у. Поэтому ее нельзя расширить до включения всех ребер цикла С. Это противоречит тому, что G — произвольно-эйлеров граф из вершины

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

После удаления из графа G ребер цепи Т получим граф G, в котором у будет изолированной вершиной. Каждая вершина в графе G имеет четную степень. Таким образом, компонента графа G, содержащая вершину и, является эйлеровым графом. Согласно следствию 3.1.1, существует цикл, содержащий вершину и. Это противоречит предположению, что вершина v находится в каждом цикле графа

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

Граф называется произвольно-эйлеровым, если он является таковым для каждой из своих вершин. Из теоремы 3.3 следует, что вершины произвольно-эйлерова графа G находятся точно в одном цикле С графа G и в последнем не существует других циклов. Иначе говоря, G — произвольно эйлеров граф тогда и только тогда, когда он является циклом.