Гамильтонова реализация графической последовательности

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

В формулировке следующего утверждения используется обозначение S(v), введенное в § 46.

Теорема 48.1 (В. Чангфейзен, 1978 г.). Если существует реализация правильной п-последователъности d,имеющая гамильтонову цепь с началом в вершине степени d_i, то к такой реализации приведет l-процедура, на первом шаге которой ведущей является вершина степени di, а на каждом из последующих — вершина с минимальной положительной меткой из множества S(v), где v — вершина, ведущая на предыдущем шаге.

Доказательство этой теоремы требует перебора воз­можных вариантов и потому громоздко; здесь оно опу­скается.

Перейдем к построению гамильтоновой реализации. Оно основано на следующей теореме.

Теорема 48.2 (В. Чангфейзен, 1978 г.). Для того чтобы правильная п-последователъность d имела реали­зацию в виде гамильтонова графа, необходимо и доста­точно выполнение следующих двух условий.

1) di > 1, 1 = 1, п;

2) существует реализация последовательности d, име­ющая гамильтонову цепь с началом в вершине степени di.

Необходимость условия теоремы тривиальна, до­кажем достаточность. Пусть G — реализация последова­тельности d, имеющая гамильтонову цепь (v₁ ,v₂ ,..., v_n) с началом в вершине v₁ степени d₁. Если v₁v_n € EG, то (v₁ ,v₂ ,..., v_n,v₁) — гамильтонов цикл.

Пусть v₁v_n ¢ EG. Тогда вершина v_n смежна с какой-либо вершиной v_i, где 1< i <n — 1. Рассмотрим верши­ну v_i+1 . Если v₁v_i+1 € EG, то

(v₁,v₂ ,...,v_i,v_n,v_n-1 ,.., v_i+1 ,v₁)

— гамильтонов цикл. Пусть теперь v_iv_i+1 ¢ EG. По­скольку вершина v_i смежна как с v_i+1 , так и с v_n, а вер­шина v₁ не смежна ни с v_i+1 , ни с v_n, хотя deg v₁ ≥

≥ deg v_i, то существует такая вершина v_k, что k ≠ 2, v_iv_k € EG, v_iv_k ¢ EG. Но тогда граф G допускает пере­ключение s = (v_iv_k, v_i+1v_i). Граф sG имеет гамильтонов цикл

(v₁,v₂ ,...,v_i,v_n,v_n-1 ,.., v_i+1 ,v₁)

(рис. 48.1).

На рис. 48.2 показана процедура построения гамиль­тоновой реализации последовательности (З², 2⁴). Полу­чен граф G с гамильтоповой цепью (1, 3, 2, 5, 6, 4); (1, 3, 2, 5, 6, 4, 1)— гамильтонов цикл.