§ 50. Пороговые графы

Среди расщепляемых графов важный класс составля­ют пороговые графы. Вершины произвольного графа 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 = O_n, указанного 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 положим

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

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

Gi о G₂ °... °G_n,

где G_n = 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. Для любого натурального числа п существует ровно 2^n-1 попарно неизоморфных порого­вых графов порядка п.

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

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

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

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

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

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

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

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

1. d₁ = п— 1 и производная последовательность d¹ = {d₂—i, ..., d_n— 1) пороговая;

1. d_n = 0 и производная последовательность dⁿ = { d₁, d₂, ..., d_n-1) пороговая.