§ 62. Триангулированные графы

Граф 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 — одно из его минимальных по включе­нию разделяющих множеств вершин, G₁ ,..., G_p — компо­ненты графа G — S, v — некоторая вершина, принадлежа­щая множеству S. Тогда для любого индекса i = 1, р вер­шина v смежна с некоторой вершиной графа G_i , иначе множество S\v было бы также разделяющим.

Пусть v₁ и v₂ — две произвольные вершины из S, a L1=( v₁, и₁, и₂, ..., и₁, v₂), L₂ = (v₁ , w₁, w₂, ..., w_t, v₂) — такие цепи минимальной длины, что (и₁, и₂, ..., и_i) — цепь графа G₁, a ( w₁, w₂, ..., w_t)—цепь графа G₂. По­скольку граф G является триангулированным, то цикл С = L₁ U L₂ имеет хорду. Так как длины цепей L₁ и L₂ минимальны, то эта хорда не может иметь ни один из следующих видов: v_iu_j1, v_iw_k1 , u_j1u_j2 , w_k1w_k2,,(i=1, 2, j1=1,l , j2=1,l, k1=1,t, k2=1,t) А так как вершины графов G₁ и G₂ друг с другом не смежны, то она также не может иметь вид u_iw_k (j=1,l, k=1,t). Таким обра­зом, эта хорда совпадает с v₁v₂ и, следовательно, верши­ны v₁ и v₂ смежны. Тем самым доказано, что множество S является кликой.

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

длины, большей трех:

Любой минимальный (v₁, v₂)-сепаратор S (см. § 35) дол­жен содержать вершину и и хотя бы одну из вершин w_i.Так как G (S) — полный граф, то для этой вершины w_i,-ребро uw_i является хордой цикла С.

Теорема 62.2. Каждый триангулированный граф является совершенным.

Доказательство теоремы основано на следующей лемме.

Лемма 62.3. Пусть S — разделяющее множество вер­шин графа G, являющееся кликой. Тогда если каждая часть графа G относительно S — совершенный граф, то и сам граф G — также совершенный.

• Пусть G' — произвольный порожденный подграф графа G, φ(G)=φ, S’ = S∩VG'. Если S^r = VG'_; то G'-полный и потому совершенный граф. Если S' ≠ VG' и граф G' — S' связен, то G' — порожденный подграф не­которой части графа G относительно множества S. По­скольку всякая такая часть совершенна, то и G' — совершенный граф. Остается случай, когда множество S' явля­ется разделяющим для графа G'. Если G’₁ ..., 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) -сепаратор. Обозначим через G_u и G_v части графа G относительно S, содержащие, соответствен­но, вершины и и v. Покажем, что графы G_u и G_v имеют симплициальные вершины, не принадлежащие множест­ву S. Если G_u — полный граф, то симплициальной явля­ется любая его вершина. В противном случае по индук­тивному предположению граф G_u имеет две симплициальные вершины. Поскольку по теореме 62.1 граф G(S) — полный, то хотя бы одна из них не принадлежит S. Аналогично показывается существование симплициальной вершины, не принадлежащей множеству S, в графе G_v. Очевидно, что эти две симплициальные вершины не смежны.

Легко показать, что триангулированным является вся­кий расщепляемый граф. Связь между классами триан­гулированных и расщепляемых графов устанавливается следующей теоремой, полученной С. Фолдесом и П. Хам-мером в 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К₂, С4 и С5 или их дополнения не такие.

Остается доказать истинность импликации 3)=>1). Пусть граф G не имеет порожденных подграфов вида 2К₂, С4 и С5. Среди всех наибольших клик графа G выберем гакую клику А, чтобы граф G — А имел наименьшее число ребер, и положим В = VG\A. Докажем, что либо В = ¢ (и тогда граф G расщепляем, поскольку он полный), либо В — независимое множество. Пусть, напротив, существует ребро ху, оба конца которого х и у принадлежат множеству В. Каждая из вершин х и у не смежна хотя бы с одной вершиной из клики А, поскольку последняя максимальна. Если бы каждая вершина, входящая в А, кроме некоторой вершины z, была смежна и с х, и с у, то множество (A\ z) U x U у было бы кликой, что противоречит выбору клики А. Следовательно, в А существуют две не­совпадающие вершины и и v такие, что хи ¢ EG и yи ¢ EG.

Так как граф G не имеет порожденных подграфов 2К₂ и С₄,то из двух возможных ребер xv и уи ровно одно действительно есть в G. Пусть, например, xv ¢ EG, уu €EG.

Если |A|>2, то рассмотрим произвольную вершину v € A\(u\v). Пусть вначале yw ¢ EG. Тогда, если хw ¢ EG, то G(x, у, v, w) = 2K₂. Если же xw € EG, то G(х, у, и, w) = C₄. Следовательно, yw €EG и, таким образом, у смежна с каждой вершиной из множества A\v. Поэтому множество A'=A\v U y является наибольшей кликой. Если же вершины w не существует, т. е. |A| =2, то множество А' также является наибольшей кликой.

Сдругой стороны,\E(G-A')\>\E{G-A)\, xy€EG, xu¢EG. Поэтому в VG\A существует такая вершина t,что t≠y, tv € EG, ty ¢ EG. Тогда в G должно быть ребро xt, иначе G(t, x, у, v) = 2K₂. Аналогично tu ¢ EG, иначе G (t, х, у, и) = С₄ (см. рис. 62.2, на котором отсутствующие ребра обозначены пунктиром). Но тогда G(t, х, у, и, v) = С5, что противоречит условию. Получен­ное противоречие доказывает, что множество В независи­мо и, следовательно, G — расщепляемый граф.

Как показывают примеры, граф, дополнительный к триангулированному, не обязательно сам является триан­гулированным (например, граф 2К2 = С₄ не является три­ангулированным). Следовательно, класс всех расщепля­емых графов уже класса триангулированных графов.