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

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

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

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

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

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

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

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

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

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

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

(v1 ,v2 ,... ,vi ,vn ,vn-1 ,.., vi+1 ,v1)

— гамильтонов цикл. Пусть теперь vivi+1 ¢ EG. По­скольку вершина vi смежна как с vi+1 , так и с vn, а вер­шина v1 не смежна ни с vi+1 , ни с vn , хотя deg v1

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

 
 

(v1 ,v2 ,... ,vi ,vn ,vn-1 ,.., vi+1 ,v1)

(рис. 48.1).

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

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

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

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

AUB = VG, (1)

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

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

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

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

Например, m(d)=3 для d = (42, 22, I2).

Теорема 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, ..., п) и сумму степеней вершин из А разобьем на две части:

 
 

где С — вклад, вносимый в эту сумму ребрами вида а1а2 , а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.

Пороговые графы

 
 

Среди расщепляемых графов важный класс составля­ют пороговые графы. Вершины произвольного графа G порядка п занумеруем числами 1, 2, ..., п, т. е. положим VG = 1, 2, ..., п). Как и в§ 28, обозначим через ƒG множество, элементами которого служат все независимые подмножества вершин графа G и пустое множество. Если существуют такие неотрицательные вещественные числа ά1, ά2, … , άn что множество всех (0, 1)-решений не­равенства

совпадает с множеством характеристических векторов элементов множества fG, то граф G называется порого­вым, а неравенство (1) — разделяющим неравенством.

Например, граф, изображенный на рис. 50.1, является пороговым, 3x1 + 2x2 + x3+2x4≤ 3 — разделяющее нера-

 
 

венство. Очевидно, что полный и пустой графы также являются пороговыми.

Отметим некоторые свойства пороговых графов. Очевидно следующее

Утверждение 50.1. Любой порожденный подграф порогового графа также является пороговым.

 

Лемма 50.2. Графы 2К.2, Р4 и С4 не являются по­роговыми.

 
 

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

 
 

— разделяющее неравенство. Тогда

Но последняя система неравенств противоречива. Тем са­мым лемма доказана.

Непосредственно из предыдущего вытекает

Следствие 50.3. Любой пороговый граф не имеет порожденных подграфов вида 2К2, Р4 и С4.

Обозначим через К ° G и О ° G графы, полученные из графа G присоединением новой доминирующей и, соответ­ственно, изолированной вершины.

Лемма 50.4. Если G пороговый граф, то оба гра­фа K°GuO°G также являются пороговыми.

 
 

Пусть G — пороговый граф порядка п, (1 — разде­ляющее неравенство. Рассмотрим граф К° G. Пусть а — минимальное число среди коэффициентов ά1, в неравенст­ве (1); b — минимальное число среди всех таких сумм

что S > β; δ и γ — произвольные числа, удовлетворяющие неравенствам

 
 

(В случае, когда G = On, указанного b не существует и в (2) соответствующее неравенство опускается.) Пря­мая проверка подтверждает, что неравенство

является разделяющим для графа К° G.

Аналогично, взяв в (3) γ и δ , удовлетворяющие усло­виям β < δ < b, γ ≤ δ — β , получим разделяющее нера­венство для графа О °G.

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

Из того факта, что любые две реализации графической последовательности получаются одна из другой с по­мощью цепочки переключений (теорема 45.1), вытекает Следствие 50.5. Граф G является униграфом тогда и только тогда, когда для любого переключения s графы G и sG изоморфны.

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

Утверждение 50.6. Граф принадлежит классу K тогда и только тогда, когда ни один из трех графов 2К2, Р4 и С4 не является его порожденным подграфом.

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

Лемма 50.7. Если G € K, то в графе G есть либо до­минирующая, либо изолированная вершина.

Пусть, напротив, G е K и в графе G нет ни доми­нирующих, ни изолированных вершин, и пусть и — его вершина максимальной степени. Тогда в этом графе су­ществуют две такие вершины v и w, что uv EG, uw ¢ EG.

Если при этом vw € EG, то, поскольку степень вершин и максимальна, существует четвертая вершина x, смежная с и и не смежная с v (см. рис. 50.3). Порожденный подграф G(u, v, w, х) входит в список подграфов, фрещенных для класса Ж утверждением 50.6 (он совпадает с Р4 или с С4).

 
 

Пусть vw ¢ EG. Так как в графе G нет изолированных вершин, то существует четвертая вершина х, смежная c w. Вершины и и v смежны с х, иначе порожденный

граф G(u, и,w,x) имел бы вид, запрещенный утверждением 50.6.. Так как и — вершина максимальной степени, то существует пятая вершина у, смежная с и, но не смежная с х. Подграф G{u,w, х, у) снова запрещенный ис. .50.4).

Полученное противоречие доказывает лемму.

Очевидны следующие два свойства графов из класса K.

1. Порожденный подграф любого графа из класса K также принадлежит этому классу.

2. Если G € K, то оба графа К° G и О °G также принадлежат классу K.

Для п > 2 положим

 
 

где Gn = K1, Gi = К или Gi = 0 ( i = 1, п — 1). Очевидно, что из вышесказанного вытекает следующее

Утверждение 50.8. Класс K есть класс всех графов, имеющих вид

Gi о G2 °... °Gn,

где Gn = K1, п ≥ 1, а для i= 1, п — 1 компоненты Gi независимо друг от друга принимают значения К или О.

Теорема 50.9. Граф является пороговым тогда и только тогда, когда он имеет вид, описанный в утверэкгдении 50.8.

Требуется доказать, что класс пороговых графов совпадает с классом K . Выше отмечалось, что любой пороговый граф принадлежит классу K . С другой стороны,согласно утверждению 50.8 любой граф из класса K мож­но построить, исходя из одной вершины, присоединяя на каждом шаге к уже полученному графу либо доминирую­щую, либо изолированную вершину. Одновершинный граф является пороговым. Согласно лемме 50.4 свойство пороговости графа сохраняется при присоединении к графу новой доминирующей или изолированной вершины. Сле­довательно, любой граф из класса K является поро­говым.

Следствие 50.10. Любой пороговый граф является расщепляемым.

 
 

Пусть пороговый граф G получается из вершины а в результате присоединения на каждом шаге к уже полу­ченному графу либо доминирующей, либо изолированной

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

Следствие 50.11. Для любого натурального числа п существует ровно 2n-1 попарно неизоморфных порого­вых графов порядка п.

 
 

Очевидно, что два графа

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

п = m, Gi = Git i = 1, п — 1.

Каждая из компонент Gi может принимать два значения. Следовательно, число неизоморфных среди таких графов равно 2n-1.

На рис. 50.5 показаны все 8 пороговых графов поряд­ка 4. Из теоремы 50.9 следует, что каждый из них опре­деляется (0, 1)-вектором (α, β, γ).

Непосредственно из теоремы 50.9 вытекает Следствие 50.12. Если G пороговый граф, то и дополнительный граф G также является пороговым.

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

Следствие 50.13. При тг>1 правильная п-последо-вателъность d является пороговой тогда и только тогда, когда верно одно из следующих двух утверждений:

1) d1 = п— 1 и производная последовательность d1 = {d2—i, ..., dn1) пороговая;

2) dn = 0 и производная последовательность dn = { d1, d2, ..., dn-1) пороговая.

§ 51. Пороговое разложение графа

Поскольку граф с одним ребром является пороговым, то любой граф G можно представить в виде объединения

G = G1 U G2 U ... U Gt

пороговых графов G, с совпадающими множествами вер­шин. Назовем такое представление пороговым разложе­нием графа G. Минимальное число t компонент в порого­вых разложениях графа G назовем пороговым числом графа G и обозначим через th(G).

Параметр th(G) связан с минимизацией числа линей­ных неравенств, задающих булеву функцию. Рассмотрим эту связь. Пусть

 
 

— система линейных неравенств с вещественными коэф­фициентами и правыми частями, В — {0, 1}, Вп — множест­во всех бинарных векторов 1 2 ,.., хп) длины п. Определим булеву функцию ƒ: Вп->В, положив f (х1 2 ,.., хп) = 0 тогда и только тогда, когда вектор 1 2 ,.., хп) удовлетворяет системе (1). Будем говорить, что функция f определяется системой неравенств (1). Тем са­мым множество нулей булевой функции, определяемой системой линейных неравенств, совпадает с множеством (0, 1)-решений этой системы.

Теорема 51.1. Любая булева функция определяется некоторой системой линейных неравенств.

Известно, что всякая булева функция ƒ от п пере­менных может быть задана своей совершенной дизъюнк­тивной нормальной формой (совершенной д. н. ф.):

 
 

где (σ1, σ2, ... , σn) пробегает множество всех единиц функции ƒ,

(см., например, [32]).

 
 

Легко видеть, что каждая конъюнкция g вида

 
 

определяется одним линейным неравенством. В самом де­ле, пусть, для определенности,

 
 

Рассмотрим неравенство

Бинарный вектор х = (х1 2 ,.., хп) не удовлетворяет этому неравенству только при условиях

х1= х2 = …= хп =1

 
 

Но эти же условия необходимы и достаточны для того, чтобы вектор х был единицей функции ƒ. Аналогично, конъюнкция

 

 
 

определяется неравенством

Итак, каждая элементарная конъюнкция, входящая в совершенную д. н. ф. функции ƒ, определяется одним ли­нейным неравенством. Очевидно, что функция ƒ опреде­ляется системой этих неравенств.

Минимальное число t неравенств в системах, задаю­щих функцию ƒ, называется пороговым числом функции ƒ и обозначается через t(f). Если функция ƒ графическая, т. е. ƒ = 0 или ­­­­ƒ — монотонная булева функция, все ниж­ние единицы которой имеют норму 2, то, как показано в 28, этой функции соответствует граф G t , множество характеристических векторов независимых подмножеств вершин которого совпадает с множеством нулей функции ƒ.

Теорема 51.2. Для любой графической функции f верно равенство

t(f) = th(Gt). (2)

Пусть ƒ — графическая функция,

Gt = Gi U G2 U ... U Gt

 
 

пороговое разложение графа Gt. Тогда система fGt всеx независимых подмножеств вершин графа Gt есть пересечение

Аналогичных систем для пороговых графов Ga. Множество характеристических векторов элементов системы fGa совпадает с множеством бинарных решений линейного неравенства, являющегося разделяющим для графа Ga. Из неравенства (3) следует, что множество бинарных решений системы из t таких неравенств есть множество характеристических векторов элементов из fGf, т. е. множество нулей функции f. Следовательно, эта система неравенств задает функцию f, и потому t(f) t. Итак, t(f) ≤ th(Gi).

 
 

Обратно, пусть функция f задается некоторой системой линейных неравенств (1). Следующим образом построим t графов G'h (k = 1, t) : VG'h = {1,2, ...,n}, ij EG'h тогда и только тогда, когда i ≠ j и αki + αkj > βk. Очевидно , что

 
 

Предположим, что какой-либо из графов G'h не является пороговым. Тогда в нем есть порожденный подграф, запрещенный следствием 50.3; пусть это подграф, показаный на рис. 50.2, где пунктирные линии означают отсутствие соответствующих ребер. Из определения графа G'h следует, что

то последняя система неравенств противоречива, следовательно, G'h — пороговый граф. Итак, (3')—пороговое разложение графа Gf. Поэтому th(Gf) ≤ t и, следователь­но, th(Gf) ≤ t(f). Равенство (2) доказано.

Вычисление порогового числа произвольного графа G и, тем более, построение соответствующего порогового разложения графа — крайне трудные задачи. Пороговое число можно оценить с помощью числа независимости ao(G), однако последнее так же трудно вычислимо.

 
 

Теорема 51.3 (В. Хватал, П. Хаммер, 1977 г.). Для любого непустого графа G порядка п верно неравенство

 

Пусть S — наибольшее независимое множество вер­шин графа G%

VG\S = {u1 ,u2, ..., uh}.

 
 

Обозначим через Ei множество ребер графа G, инцидент­ных вершине ui (i = 1, k). Поскольку ребра, входящие в Еi, составляют звезду, являющуюся согласно теоре­ме 50.9 пороговым графом, то и граф Gi = (VG, Еi ) поро­говый. Но

 
 

Следовательно, (6) — пороговое разложение графа G. По­этому th(G) ≤ k= п — ao (G), т. е. верно неравенство (4). Пусть теперь в графе G нет треугольников и пусть

— пороговое разложение с минимальным числом компо­нент. В пороговом графе G< также нет треугольников. Из теоремы 50.9 следует поэтому, что граф Gi является звездой или получается из звезды в результате присоеди­нения изолированных вершин. В любом случае в графе Gi есть вершина ui инцидентная всем его ребрам. Так как U EGi = EG, то множество VG\{ u1 , u2, ..., ut) не­зависимо в графе G. Следовательно, ao(G) ≥ n — th(G), что вместе с неравенством (4) приводит к равенству (5).

Заметим, что равенство (5) может быть верным и для графа с треугольниками. Таков, например, граф на с. 51.1.

Поскольку для любого n-вершинного графа G верно равенство ao(G)+ β0(G) = n (теорема 25.5), где βo(G)— число покрытия графа G, то из предыдущей теоремы вытекает

Следствие 51.4. Для любого графа G, не содержащего треугольников, верно ра­венство th (G)= βo(G).

В частности, любой двудольный граф не содержит треугольников. Кроме того, для двудольного графа G верно равенство (G) = a1(G), где a1(G) — число паросочетания (теорема 32.1). Поэтому из теоремы 51.3 вытекает

Следствие 51.5. Для любого двудольного графа G верно равенство th(G) = a1(G).

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








Дата добавления: 2019-07-26; просмотров: 495;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.048 сек.