Эйлеровым путем в графе называется путь, содержащий все ребра графа.
Эйлеровым циклом в графе называется цикл, содержащий все ребра графа
Граф, обладающий эйлеровым циклом, называется эйлеровым графом. Принято всякую замкнутую линию, если ее можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, называть уникурсальной. Задача 4.1. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (рис. 23, где Л - левый берег, П - правый берег, А и Б - острова). Можно ли, прогуливаясь по берегам реки, пройти по каждому мосту ровно один раз? Рис. 23 Рис. 24
На рисунке 24 изображен граф, соответствующий задаче о кёнигсбергских мостах. Докажем, что этот граф не является уникурсальным. Задача 4.2. Шесть островов на реке в парке "Лотос" соединены мостами. рис. 25 Можно ли, начав прогулку на одном из островов, пройти по каждому из мостиков ровно один раз и вернуться на тот же остров? В случае отрицательного ответа определите, сколько мостиков и между какими островами нужно построить, чтобы такая прогулка стала возможной. Решение. Построим граф G, в котором каждому участку суши поставим в соответствие вершину и соединим две вершины ребром тогда и только тогда, когда соответствующие участки суши будут соединены мостом.
Рис 26 рис. 27 Задача заключается в определении, будет ли граф G эйлеровым. Найдем необходимые и достаточные условия существования эйлерова цикла. Теорема 2. (Теорема Эйлера) Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины четная. Теорема 3. Для уникурсального графа число вершин нечетного индекса равно нулю или двум. Теорема 4. Если граф G обладает эйлеровым путем c концами А и В (А не совпадает с В), то граф G связный и А и В — единственные нечетные его вершины. Теорема 5. Если граф G связный и А и В единственные нечетные вершины его, то граф G обладает эйлеровым путем с концами А и В.
Таким образом, всякую замкнутую фигуру, имеющую в точности две нечетные вершины, можно начертить одним росчерком без повторений, начав в одной из нечетных вершин, а кончив в другой. Задача 4.2. «Муха в банке». Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все двенадцать ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается.
Решение. Является ли куб эйлеровым графом? Куб представляет собой граф, у которого все вершины имеют степень 3. Для того чтобы был эйлеровым нужно, чтобы все его вершины были четными, а это условие в данном случае не выполняется. Следовательно, граф не является эйлеровым. Значит, муха не сможет обойти все ребра куба, не проходя по одному ребру дважды.
Примеры эйлеровых графов:
1) план выставки, если экспонаты расположены по обеим сторонам залов, т.е. можно составить такой замкнутый маршрут, что по каждому залу посетитель сможет пройти в точности два раза – по одному с каждой стороны в разных направлениях.
2) Любой город можно обойти, пройдя по каждой улице ровно два раза – по одному в каждом направлении.
3) На рисунке изображена схема зоопарка. Вершины графа – вход, выход, перекрестки, повороты, тупики. Ребра – дорожки, вдоль которых расположеныклетки. Найдите маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути.
Решение.
Гамильтоновой цепью графа называется его простая цепь, которая проходит через каждую вершину графа точно один раз.
Цикл графа, проходящий через каждую его вершину, называется гамильтоновым циклом. Граф называется гамильтоновым, если он обладает гамильтоновым циклом.
Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона (Hamilton W.), который в 1859 году предложил следующую игру-головоломку: требуется, переходя по очереди от одной вершины додекаэдра к другой вершине по его ребру, обойти все 20 вершин по одному разу и вернуться в начальную вершину.
Критерий существования гамильтонова цикла в произвольном графе G еще не найден. Достаточным условием существования гамильтонова цикла является полнота графа G.
Если в графе G, имеющем n вершин, степень каждой вершины не меньше, чем, то граф G гамильтонов.
Отметим, что придумано еще много других развлекательных и полезных задач, связанных с поиском гамильтоновых циклов. Сформулируем две из них.
1. (Задача про банкет) Компанию из нескольких человек требуется рассадить за круглым столом таким образом, чтобы по обе стороны от каждого сидели его знакомые. Очевидно, для решения этой задачи нужно найти гамильтонов цикл в графе знакомств компании.
2. (Задача о шахматном коне.) Можно ли, начиная с произвольного поля шахматной доски, обойти конем последовательно все 64 поля по одному разу и вернуться в исходное поле? (решение будет рассмотрено ниже).
Следующая теорема, доказанная Поша (Posa L.), дает достаточное условие того, что неориентированный граф является гамильтоновым. Она обобщает результаты, полученные ранее Оре (Ore O.) и Дираком (Dirac G.A.), которые приводятся здесь в виде следствий.
Теорема 1
Пусть G имеет p ≥ 3 вершин. Если для всякого n, 1 ≤ n ≤ (p−1) ⁄ 2, число вершин со степенями, не превосходящими n, меньше чем n, и для нечетного p число вершин степени (p−1) ⁄ 2 не превосходит (p−1) ⁄ 2, то G — гамильтонов граф.
Теорема 2
В полном графе G(V, E) всегда существует гамильтонов путь.
Решение.
, то граф G гамильтонов.