![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Граф G называется триангулированным (или хордальным), если ни один из его порожденных подграфов не яляется простым циклом длины l ≥ 4. Это означает, что триангулированном графе для любого его простого цикла длины l ≥ 4 есть ребро, соединяющее две несоседние вершины этого цикла. Такое ребро называется хордой.
На рис. 62.1 изображены два графа G и Н, из которыx G является триангулированным, а Н не является.
Очевидйо, что граф является триангулированным, если все его компоненты — триангулированные графы. Следующая характеризация связных триангулированных графов принадлежит Г. Дираку. В ней используется понятие разделяющего множества вершин. Множество S вершин графа G называется разделяющим множеством вершин, если граф G — S имеет больше компонент, чем граф G. Если при этом Gi(i=1,i) —компоненты графа G—S, то
порожденные подграфы G (VGi U S) называются частями графа G относительно S.
Теорема 62.1. Связный граф является триангулированным тогда и только тогда, когда любое его разделяющее множество вершин, минимальное относительно включения, есть клика.
Необходимость. Пусть G — триангулированный связный граф, S — одно из его минимальных по включению разделяющих множеств вершин, G1 ,..., Gp — компоненты графа G — S, v — некоторая вершина, принадлежащая множеству S. Тогда для любого индекса i = 1, р вершина v смежна с некоторой вершиной графа Gi, иначе множество S\v было бы также разделяющим.
Пусть v1 и v2 — две произвольные вершины из S, a L1=(v1, и1, и2,..., и1, v2), L2 = (v1, w1, w2,..., wt, v2) — такие цепи минимальной длины, что (и1, и2,..., иi) — цепь графа G1, a (w1, w2,..., wt) —цепь графа G2. Поскольку граф G является триангулированным, то цикл С = L1 U L2 имеет хорду. Так как длины цепей L1 и L2 минимальны, то эта хорда не может иметь ни один из следующих видов: viuj1, viwk1, uj1uj2, wk1wk2,,(i=1, 2, j1=1,l, j2=1,l, k1=1,t, k2=1,t) А так как вершины графов G1 и G2 друг с другом не смежны, то она также не может иметь вид uiwk (j=1,l, k=1,t). Таким образом, эта хорда совпадает с v1v2 и, следовательно, вершины v1 и v2 смежны. Тем самым доказано, что множество S является кликой.
Достаточность. Пусть в графе G любое минимальное разделяющее множество вершин является кликой. Рассмотрим произвольный простой цикл С графа G
![]() |
Любой минимальный (v1, v2) -сепаратор S (см. § 35) должен содержать вершину и и хотя бы одну из вершин wi. Так как G (S) — полный граф, то для этой вершины wi,-ребро uwi является хордой цикла С.
Теорема 62.2. Каждый триангулированный граф является совершенным.
Доказательство теоремы основано на следующей лемме.
Лемма 62.3. Пусть S — разделяющее множество вершин графа G, являющееся кликой. Тогда если каждая часть графа G относительно S — совершенный граф, то и сам граф G — также совершенный.
> Пусть G' — произвольный порожденный подграф графа G, φ (G)= φ, S’ = S∩ VG'. Если Sr = VG'; то G'- полный и потому совершенный граф. Если S' ≠ VG' и граф G' — S' связен, то G' — порожденный подграф некоторой части графа G относительно множества S. Поскольку всякая такая часть совершенна, то и G' — совершенный граф. Остается случай, когда множество S' является разделяющим для графа G'. Если G’1..., G’p — части графа G' относительно S’ то любая из них является порожденным подграфом некоторого совершенного графа — соответствующей части графа G относительно множества S. Поэтому она сама — совершенный граф. Следовательно, χ(G'i) = φ(G'i) ≤ φ. Вершины графа G', невходящие в S' и принадлежащие различным частям G', не смежны. Поэтому, раскрасив φ цветами вершины каждого из графов Gi так, чтобы любая вершина из множества S' имела при всех этих раскрасках один и тот же цвет, получим правильную φ -раскраску графа G'. Следовательно, χ(G') =φ =φ(G').
> Доказательство теоремы 62.2. Воспользуемся индукцией по числу вершин графа. Для графов порядка п ≥ 3 утверждение очевидно. Пусть G — триангулированный граф, \G\ — п>3, и пусть теорема верна для графов с меньшим числом вершин.
Полный граф является совершенным. Если же граф G не будет полным, то из теоремы 62.1 вытекает, что в G существует разделяющее множество вершин S, являющееся кликой. По индуктивному предположению все части графа G относительно S — совершенные графы. Но тогда по предыдущей лемме и сам граф G является совершенным. <
Следующая теорема проливает свет на строение триангулированных графов и окажется полезной в дальнейшем.
Вершина графа называется симплициалъной, если ее окружение — клика.
Теорема 62.4. Любой триангулированный граф имеет симплициалъную вершину. Более того, если этот граф отличен от полного, то в нем есть по меньшей мере две несмежные симплициалъные вершины.
Утверждение теоремы очевидно для полных графов и легко проверяемо для графов, имеющих не более трех вершин. Пусть G — триангулированный граф порядка п > 3, отличный от полного, и пусть теорема верна для графов, порядки которых меньше чем п. Пусть, далее, и и v — две несмежные вершины графа G и S — минимальный (и, v) -сепаратор. Обозначим через Gu и Gv части графа G относительно S, содержащие, соответственно, вершины и и v. Покажем, что графы Gu и Gv имеют симплициальные вершины, не принадлежащие множеству S. Если Gu — полный граф, то симплициальной является любая его вершина. В противном случае по индуктивному предположению граф Gu имеет две симплициальные вершины. Поскольку по теореме 62.1 граф G(S) — полный, то хотя бы одна из них не принадлежит S. Аналогично показывается существование симплициальной вершины, не принадлежащей множеству S, в графе Gv. Очевидно, что эти две симплициальные вершины не смежны.
Легко показать, что триангулированным является всякий расщепляемый граф. Связь между классами триангулированных и расщепляемых графов устанавливается следующей теоремой, полученной С. Фолдесом и П. Хам-мером в 1977 году и содержащей характеризацию расщепляемых графов в терминах запрещенных порожденных подграфов.
Теорема 62.5. Для графа G следующие утверждения эквивалентны:
1) граф G расщепляем;
2) оба графа G и G’ являются триангулированными,
3) граф G не содержит порожденных подграфов вида 2К.2, С4 и С5.
> 1)=>2). Пусть G — расщепляемый граф. Тогда, по определению, существует разбиение A U В = VG на клику 4 и независимое множество В. Пусть в G есть порожденный простой цикл Сp длины р. По меньшей мере одна из двух соседних вершин этого цикла должна быть в А. Но з А любые две вершины смежны, поэтому р ≤ 3. Тем замым доказано, что любой расщепляемый граф является триангулированным. Поскольку дополнительный к расцепляемому граф также расщепляем, то истинность импликации 1)=>2) доказана.
Импликация 2)=>) очевидна, поскольку порожденный подграф триангулированного графа также должен быть триангулированным, а графы 2К2, С4 и С5 или их дополнения не такие.
Остается доказать истинность импликации 3)=>1). Пусть граф G не имеет порожденных подграфов вида 2К2, С4 и С5. Среди всех наибольших клик графа G выберем гакую клику А, чтобы граф G — А имел наименьшее число ребер, и положим В = VG\A. Докажем, что либо В = ¢ (и тогда граф G расщепляем, поскольку он полный), либо В — независимое множество. Пусть, напротив, существует ребро ху, оба конца которого х и у принадлежат множеству В. Каждая из вершин х и у не смежна хотя бы с одной вершиной из клики А, поскольку последняя максимальна. Если бы каждая вершина, входящая в А, кроме некоторой вершины z, была смежна и с х, и с у, то множество (A\ z) U x U у было бы кликой, что противоречит выбору клики А. Следовательно, в А существуют две несовпадающие вершины и и v такие, что хи ¢ EG и yи ¢ EG.
Так как граф G не имеет порожденных подграфов 2К2 и С4, то из двух возможных ребер xv и уи ровно одно действительно есть в G. Пусть, например, xv ¢ EG, уu €EG.
Если |A|>2, то рассмотрим произвольную вершину v € A\(u\v). Пусть вначале yw ¢ EG. Тогда, если хw ¢ EG, то G(x, у, v, w) = 2K2. Если же xw € EG, то G(х, у, и, w) = C4. Следовательно, yw €EG и, таким образом, у смежна с каждой вершиной из множества A\v. Поэтому множество A'=A\v U y является наибольшей кликой. Если жевершины w не существует, т. е. |A| =2, то множество А' также является наибольшей кликой.
![]() |
Как показывают примеры, граф, дополнительный к триангулированному, не обязат ельн о сам является триангулированным (например, граф 2К2 = С4 не является триангулированным). Следовательно, класс всех расщепляемых графов уже класса триангулированных графов.
Дата публикования: 2015-01-23; Прочитано: 694 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!