05. Гамильтонов цикл и гамильтонов граф. Условия Дирака, Оре и Поша, гарантирующие существование в графе гамильтонова цикла

Пусть - некоторый граф. Он называется Гамильтоновым, если в нем сущест-вует простой цикл, содержащий все вершины графа. Например, каждый полный граф – гамиль-тонов, потому что в нем проведены всевозможные ребра и, в частности, те, благодаря которым возможен обход по всем вершинам. А вот пример графа, не являющегося гамильтоновым:

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

Итак, условие первое - Условие Дирака. Пусть - число вершин в данном графе; если степень каждой вершины не меньше, чем , то граф называется Графом Дирака. Можно дока-зать, что Каждый граф Дирака обязательно гамильтонов.

Вот пример графа Дирака:

Очевидно, этот граф - гамильтонов. А вот пример гамильтонова графа, не являющегося графом Дирака:

Условие второе - Условие Оре. По-прежнему будем обозначать через количество вер-шин в данном графе. Если для любой пары несмежных вершин выполнено неравенство , то граф называвается Графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Можно доказать, что Всякий граф Оре обяза-тельно гамильтонов.

Вот пример графа Оре:

А вот пример графа, не являющегося графом Оре и, тем не менее, графа гамильтонова:

Нетрудно заметить, что всякий граф Дирака автоматически является графом Оре. Но вот пример графа Оре, не являющегося графом Дирака:

Условие третье - Условие Поша. Это - более сложная конструкция. Введем следующую функцию целого неотрицательного аргумента . Сначала запишем определение формулой, а затем прокомментируем его. Итак, речь идет по-прежнему о графе ,

Для которого и строится функция :

;

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

Для примера построим функцию Поша следующего графа:

Функция будет описано таблично:

X	0	1	2	3	4	5	...
F(x)	0	1	3	4	4	4	...

Теперь сформулируем условие Поша.

Графом Поша называется граф , удовлетряющий следующим условиям (число вершин этого графа обозначим через , его функцию Поша обозначим через , символ будет обо-значать целое число):

1) для выполняется неравенство ;

2) если - целое число, то при имеет место неравенство: .

Можно доказать, что Каждый граф Поша обязательно гамильтонов. Легко заметить, что простой цикл на большом числе вершин графом Поша не является, но, конечно, явяляется га-мильтоновым графом.

Кроме того, нетрудно заметить, что Всякий граф Дирака является графом Поша. То же верно и в отношении графов Оре: каждый граф Оре является графом Поша. Обратное в обоих последних случаях неверно. Вот пример: фиксируем какой-нибудь полный граф на достаточно большом числе вершин; добавим к нему еще одну вершину и соединим ее с любыми двумя вершинами в исходном графе; очевидно, вновь полученный граф - гамильтонов; фиксируем

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

< Предыдущая		Следующая >