Эйлеровы графы. 
Дискретная математика

Вернемся к историческому примеру о Кенигсбергских мостах. В каком случае в графе можно найти цикл, в котором каждое ребро участвует ровно один раз?

Цикл, содержащий каждое ребро ровно один раз, называется эйлеровым. Граф, содержащий эйлеровый цикл, называется эйлеровым графом.

Теорема (критерий эйлеровости графа): конечный граф G (V, E) является эйлеровым, тогда и только тогда, когда он связен и степени всех его вершин — четны.

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

Теорема (критерий полуйлеровости графа): конечный граф G (V, E) является полуэйлеровым, тогда и только тогда, когда он связен и точно две го вершины имеют нечетную степень.

Гамильтоновы графы

Кроме эйлеровых графов рассматриваются также гамильтоновы графы.

Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие», придуманной Гамильтоном в позапрошлом веке: нужно обойти все вершины графа, диаграмма которого показана на рис. 3.11 (в исходной формулировке это были названия столиц различных стран), по одному разу и вернуться в исходную точку.

Этот граф представляет собой укладку додекаэдра.

Рис. 3.11. Задача «Кругосветное путешествие»

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

Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф.

Теорема (Дирак). Если в графе G (V, E) для любой вершины v выполняется: (v) р/2, то граф G является гамильтоновым.

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

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

Можно предложить следующую простую схему решения задачи коммивояжера: сгенерировать все р! возможных перестановок вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать из них кратчайший. Очевидно, такое вычисление потребует огромного количества шагов.

Как известно, р! с ростом р растет быстрее, чем любой полином от р, и даже быстрее, чем 2Р. Таким образом, решение задачи коммивояжера описанным методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших р.

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

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

Уже давно Эйлером получено просто проверяемое необходимое и достаточное условие существования в графе эйлерова цикла. Что касается гамильтоновых графов, то для них не известно необходимых и достаточных условий. На основе необходимого и досточного условия существования эйлерова цикла можно построить эффективные алгоритмы отыскания такого цикла.

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

Теорема: Эйлеровых графов почти нет (E (p) — число эйлеровых графов с p вершинами, G (p) — число всех графов с p вершинами):

.

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

Теорема: (H (p) — число гамильтоновых графов с p вершинами, G (p) — число всех графов с p вершинами):

.

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

Заключение

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

В информатике графы используются в следующих разделах:

• — операционные системы;
• — алгоритмизация;
• — структуры данных;
• — моделирование и др.