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

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

В формулировке следующего утверждения используется обозначение 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)— гамильтонов цикл.

§ 49. Расщепляемые графы

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

Граф G называется расщепляемым, если существует разбиение множества его вершин на клику и независимое множество, т. е. такое разбиение

AUB = VG, (1)

что порожденный подграф G(A) является полным, G(B)—пустым. Это разбиение называется полярным. Множество А называется верхней долей графа G, а В — нижней; одна из этих долей может быть пустой.

Как подтверждает простая проверка, все графы порядка п ≥ 3 расщепляемы, но уже среди четырехвершинных графов есть и расщепляемые и не расщепляемые.

Для правильной графической последовательности d преведем параметр m(d), положив

т(d) = max {i: di ≥ i—l}.

Например, m(d)=3 для d = (4², 2², I²).

Теорема 49.1 (П. Хаммер, Б. Симеоне, 1981 г.). Пустъ d — правильная графическая п-последовательностъ, G — ее произвольная реализация. Граф G расщепляем тогда и только тогда, когда верно равенство

гдеm = m(d).

Пусть G — расщепляемый граф. Среди всех полярных разбиений множества VG выберем разбиение (1) с максимальным числом вершин в верхней доле. Очевидно, что если а € А, b € В и IАI = k, то deg а ≥ k — 1, deg b < k. Следовательно, m = к. Поскольку G (А) = К_т, G(В) = О_п-m , то верно равенство (2).

Обратно, пусть для некоторого графаG VG = {1, 2, ... .., п}, deg i = di. Положим A = {1, 2, ..., т}, В = {m + l, ..., п) и сумму степеней вершин из А разобьем на две части:

гдеС — вклад, вносимый в эту сумму ребрами вида а₁а₂ , а_i € А, а D — тот вклад, который вносят ребра вида ab, а € А, b € В. Очевидно, что верны неравенства

Равенство (2) верно только тогда, когда оба неравенства (3) являются равенствами. Но это и означает, что G(A) = К_т , G(B) = Оп-т.

Очевидно

Следствие 49.2. Если одна из реализаций графиче­ской последовательности расщепляема, то и все ее реали­зации расщепляемы.

Графическая последовательность называется расщеп­ляемой, если она имеет расщепляемую реализацию.

При доказательстве достаточности выполнения усло­вия (2) для расщепляемости графической последователь­ности d не были использованы ни смысл параметра m(d), ни то, что последовательность d не возрастает. Поэтому верно

Утверждение 49.3. Для расщепляемости графиче­ской п-последователъности d необходимо и достаточно, чтобы для какого-либо m, l≤m≤n, выполнялось ра­венство (2).

Расщепляемые графы составляют важный и содержа­тельный класс графов. В частности, он включает в себя все пороговые графы, рассматриваемые в следующем па­раграфе. Некоторые задачи, сложные в общей ситуации (например, задача построения наибольшего независимого множества), становятся тривиальными в классе расщеп­ляемых графов. Другие задачи для этого класса графов столь же сложны, как и для произвольных графов. Из­вестно, например, что проблема изоморфизма произволь­ных графов просто сводится к аналогичной проблеме для расщепляемых графов (см. [18]).

Характеризация расщепляемых графов в терминах запрещенных порожденных подграфов приведена в § 62.