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

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

G = G₁ U G₂ U ... U G_t

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

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

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

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

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

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

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

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

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

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

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

х₁= х₂ = …= х_п =1

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

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

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

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

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

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

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

G_t = Gi U G₂ U ... U G_t

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

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

Обратно, пусть функция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')—пороговое разложение графа G_f. Поэтому th(G_f) ≤ t и, следователь­но, th(G_f) ≤ t(f). Равенство (2) доказано.

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

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

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

VG\S = {u₁ ,u₂, ..., u_h}.

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

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

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

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

Поскольку для любого n-вершинного графа G верно равенство ao(G)+ β₀(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) вычисляется несложно.