В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 50
Текст из файла (страница 50)
Это означает, что в трнангуллровапном графе для любого его простого цикла длины 1>4 есть ребро, соединнющее две несоседние вершины этого цикла. Такое ребро называется хордой. На рпс. 62А изображены два графа С и Н, из которых С является триапгулнроваппым, а Н не является.
272 Очевидно, что граф является триангулированным, если все сто компоненты — триангулпрованные графы. Следующая характернзацня связных трнангулнрованных графов принадлежит Р. Дираку. В пей используется понятие разделяющего множества вершин. Мнон1ество Я верппш графа 6 называется разделяющим мноясеством вершин, если граф 6 — Я имеет больше компонент, чем граф 6. Если при этом 6, (1=1, 1) — компоненты графа 6 — Я, то порожденные подграфы 6()тС, 0 Я) называются частями графа 6 относительно Я. Рис. 62Л Теорема 62.1.
Связный граф является триангулированным тогда и только тогда, когда любое его разделяющее мноавество вершин, минимальное относительно включения, есть клика. С' Необходимость. Пусть 6 — триангулнровапный связный граф, Я вЂ” одно из его минимальных по включению разделяющих множеств вершин, Сн ..., Сг — компоненты графа С вЂ” Я, о — некоторая вершина, принадлежащая ьгноткеству Я. Тогда для любого индекса с= 1, р вершина о смежна с некоторой вершиной графа Сь иначе множество Я~о было бы также разделяющим.
Пусть о~ и ог — две произвольные вершины нз Я, а 7"1 =(оь ин иг, ° ° .> иь иг)~ с'г =(о! ш! юг~ ° ° ° ж~ ог) такие цепи минимальной длины, что (ин иг, ..., и,)— цепь графа 6н а (шн шм ..., ш~) — цепь графа Сг. Поскольку граф С является триангулированным, то цикл С = со 0 с.г имеет хорду. Так как длины цепей Ь| н Ьз минимальны, то эта хорда не может иметь нп один из следующих видов:о;и., огшь, и; и;,, иь юд (1= 1, 2, у~ = = 1, 1, )г = 1, 1, )2~ = 1, 1, )сг = 1, ц) .
Л так как вершины графов 6~ и 6г друг с другом не смежны, то она также не может иметь вид и,ш„(7'= 1, 1, )с =1, Г). Таким образом, эта хорда совпадает с о~от н, следовательно, вершины о~ и ог смежны. Тем самым доказано, что множество Я является кликой. Достаточность. Пусть в графе 6 любое минимальное разделяющее множество вершин является кликой. Рассмотрим произвольный простой цикл С графа 6 18 в, л, няеличев и ав. 273 длины, большей трех: (оп и~ он шп ю шм о!)1 Любой минимальный (оп ог)-сепаратор Я (см. э 35) должен содержать вершину и и хотя бы одну из вершин юо Так как С(Я) — полный граф, то для этой вершины ю~ ребро ию, является хордой цикла С.
0 Т е о р е м а 62.2. Кагкдый триапгулированпый граф является совершенп ыл. Доказательство теоремы основано на следующей лемме. Лемма 62.3. Пусть Я вЂ” разделяющее множество вершин графа 6, являющееся кликой. Тогда если каждая часть графа 6 относительно Я вЂ” совершенный граф, то и саж граф С вЂ” также совершенный. с' Пусть С вЂ” произвольный порожденный подграф графа С, <р(6') = <р, Я' = Я () т'6'. Если Я' = т'6', то С'— полный и потому совершенный граф. Если Я'Ф т'С' и граф 6' — 3' связен, то С' — порожденный подграф некоторой части графа С относительно множества Я. Поскольку всякая такая часть совершенна, то и С' — совершенный граф.
Остается случай, когда множество Я' является разделяющим для графа 6'. Если Сг, ..., Ср— части графа 6' относительно Я', то любая из них является порожденным подграфом некоторого совершенного графа — соответствующей части графа 6 относительно множества Я. Поэтому она сама — совершенный граф. Следовательно, 2(6~) = ~(6~)(~р.
Вершины графа 6, не входящие в Я и принадлежащие различным частям С, не смежны. Поэтому, раскрасив ~р цветами вершины каждого из графов С~ так, чтобы любая вершина из множества Я' имела при всех этих раскрасках один и тот же цвет, получим правильную ~р-раскраску графа 6. Следовательно, т(6')=гр=~р(6'). < ~> Доказательство теоремы 622. Воспользуемся индукцией по числу вершин графа. Для графов порядка и ( 3 утверждение очевидно. Пусть 6 — триангулированный граф, )61 = п ~ З,и пусть теорема верна для графов с меньшим числом вершин.
Полный граф является совершенным. Если же граф 6 не будет полным, то из теоремы 62.1 вытекает, что в С существует разделяющее множество вершин Я, являющееся кликой. По индуктивному предположению все части графа 6 относительно Я вЂ” совершенные графы. Но тогда 274 по предыдущей лемме и сам граф 6 является совершенным. э Следующая теорема проливает свет на строение триангулированных графов и окаясется полезной в дальнейшем. Вершина графа называется симплсщиальной, если ее окружение — клина.
Т е о р е м а 62А, Любой триангулировашсьсй граф имеет симплиссиальнусо вершину. Более того, голи этот граф отличен от полного, то в нем есть по мгныией мере две несмежные симплис1иальпыв вершины. > Утверждение теоремы очевидно для полных графов и легко проверяемо для графов, имеющих не более трех вершин. Пусть 6 — триангулированный граф порядка и ) 3, отличный от полного, и пусть теорема верна для графов, порядки которых меньше чем и. Пусть, далее, и в о — две несмежньсе вершины графа 6 и Я вЂ” минимальный (и, о)-сепаратор. Обозначим через 6„и 6, части графа 6 относительно Я, содержащие, соответственно, вершины и и о. Покаькем, что графы 6„и 6„имеют симплициальные вершины, не принадлежащие множеству Я.
Если 6 — полный граф, то симплициальиой является лсобая его вершина. В противном случае по индуктивному предположению граф 6„вмоет две симплициальные вершины. Поскольку по теореме 62А граф 6(Я)— полный, то хотя бы одна из них пе принадлежит Я. Аналогично показывается супСествование симплициальной вершины, по принадлежащей мноясеству Я, в графе 6„. Очевидно, что зги две симплициальные вершины не смежны. 0 Легко показать, что трпангулированным является всякий расщепляемый граф. Связь между классами трпапгулированпых и расщепляемых графов устанавливается следующей теоремой, полученной С.
Фолдесом и П. Хаммером в 1977 году и содержащей характеризацию расщепляемых графов в терминах запрещенных порожденных подграфов. Теорема 62.5. Для графа 6 следусощиг утверждения эквивалентны: 1) граф 6 расщепляем; 2) оба графа 6 и 6 явлтотся триангулированными; 3) граф 6 не содержит порожденссых подграфов вида 2Кг, Сс и Сг. ~> 1) ~ 2). Пусть 6 — расщепляемый граф. Тогда, по определению, существует разбиение А 0 В = т'6 на клику аве Яуй Л и незазпсимоо множество В.
Пусть з С есть поровсденный простой цикл Сг длины р. По меньшей мере одна из двух соседних вершин этого цикла должна быть в А. Но в А лсобые две верпшпы смеисны, поэтому р(3. Тем самым доказано, что любой расщепляемый граф является триангулированным. Поскольку дополнительный к расщепляемому граф также расщепляем, то истинность пмплпкацип 1) =- 2) доказана. Импликац>ся 2) =- 3) очевидна, поскольку порожденный подграф триангулированного графа также должен быть триапгулированным, а графы 2Км Сс и Сз или их дополнения не такио. Остается доказать истинность импликации 3)=э- 1).
Пусть граф С не имеет порожденных ш>дграфов вида 2К>ь Сс и Сэ. Среди всех наибольших клик графа С выберем таку>о клику Л, чтобы граф С вЂ” А имел наименьшее число ребер, и положим В= г'6>А. Докаясем, что либо В= = >о (и тогда граф С расщепляем, поскольку он полный), либо  — независимое множество. Пусть, напротив, существует ребро ху, оба конца которого х и у принадлежат множеству В. Кансдая из вершин х и у не смежна хотя бы с одной вершиной из клики А, поскольку последняя максимальна.
Если бы кансдая вершина, входящая э Л, кроме некоторой вершины х, была смеисна и с х, и с у, то множество (Л>з) !! х 0 у было бы кликой, что противоречит выбору клики А. Следовательно, в Л существуют две несовпадающие вершины и и э такие, что хи Ф ЕС и уэ Ф ЕС. Так как граф С не имеет гюроясденных подграфов 2Кс и С4, то из двух возмоясных ребер хэ и уи ровно одно действительно есть в С. Пусть, например, хиФЕС, уи еэ ЕС. Если !Л!)2, то рассмотрим произвольную вершину шси Лй(и !! э).
Пусть вначале ушФ ЕС. Тогда, если хшФ Ф ЕС, то С(х, у, э, ш) = 2Кх Если же хш сп ЕС, то С(х, у, и, и)=С>. Следовательно, ушсиЕС и, таким образом, у смежна с каждой вершиной из множества Л>э. Поэтому множество А' = А> и !! у является наибольшей кликой. Если же вершины ш не существует, т. е.
!Л! = 2, то мшпкоство 1' также является наибольшей кликой. С другой стороны, !Е(6 — Л') ! > !Е(6 — А) !, ху ~ ЕС, хоФЕС. Поэтому в )гС'>Л существует такая вершина 1, что гт'-. у, со снЕС, гу Ф ЕС. Тогда в С должно быть ребро хс, пначо С(>',,т, у, с>) =- 2Кх Лпалог>счно 1и Ф Е6, иначе 6(1, х, у, и)=С4 (си. рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
