5.6. Ориентированные гамильтоновы графы

Контур ориентированного графа G называется ориентированным гамильтоновым контуром G, если он содержит все его вершины.

Ориентированный путь графа G называется гамильтоновым, если в нем содержатся все вершины того же графа.

Ориентированным гамильтоновым графом называется граф, имеющий гамильтонов контур.

Гамильтоновым контуром, например, является последовательность дуг в графе, представленном на рис. 5.13, а.

Рис. 5.13. а — ориентированный гамильтонов граф, б — ориентированный граф с гамильтоновым ориентированным путем, но без гамильтоновых контуров

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

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

Ориентированный граф называется полным, если полным является неориентированный граф, лежащий в его основе. Следующая теорема принадлежит Муну [5.4].

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

Доказательство. Пусть — сильно связный полный ориентированный граф на 3 вершинах. Возьмем произвольную вершину и гргфа G. Пусть Поскольку граф 0 — сильно связный, S и Т не являются пустыми. По этой же причине в графе G имеется дуга, идущая из вершины в вершину Таким образом, вершина и лежит в контуре длины 3 (рис. 5.14).

Докажем теорему индукцией по k. Допустим, что вершина и входит в контуры всех длин от 3 до . Покажем, что вершина и входит и в контур длины

Пусть С: — контур длины . Необходимо рассмотреть два случая.

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

В противном случае обозначим через S множество всех вершин, не входящих в контур С и являющихся конечными в дугах, исходящих из вершин контура С, а через Т — множество всех вершин, не входящих в контур С и являющихся начальными в дугах, заходящих в вершины того же контура. Снова, поскольку граф G сильно связный, S и Т — непусты. Кроме того, существует дуга, идущая из вершины в вершину . Таким образом, вершина и входит в контур длины (рис. 5.15).

Рис. 5.14.

Рис. 5.15.

Следствие 5.10.1. Сильно связный полный ориентированный граф гамильтонов.

Приведем сейчас без доказательства очень сильную теорему, принадлежащую Гуйа-Ури. Доказательство ее исключительно сложно, его можно найти в работе [5,9].

Теорема 5.11. Пусть G — сильно связный граф на вершинах без параллельных дуг и петель. Если для всякой вершины у справедливо неравенство то граф G имеет гамильтонов контур.

Следующее утверждение обобщает результат Дирака (следствие 3.4.1) для неориентированных графов, и его можно доказать с помощью теоремы 5.11 и упражнения 5.6.

Следствие 5.11.1. Пусть 0 — ориентированный граф на вершинах без параллельных дуг и петель. Если то граф G содержит гамильтонов контур.

Непосредственное доказательство этого результата можно найти в работе [5.6].

Завершаем этот раздел утверждением о существовании ориентированного гамильтонова пути.

Теорема 5.12. Если ориентированный граф — полный, то он имеет ориентированный гамильтонов путь.

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

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