§ 69. Независимые множества

Множество вершин гиперграфа называется независимым, если оно не содержит ребер. Пустое множество вершин по определению независимо. Как и в случае графов, наибольшее по мощности независимое множество вершин гиперграфа Н называется наибольшим, а число вершив в этом множестве называется числом независимости гиперграфа Н и обозначается через αо(Н). Через ГН обозначается множество, элементами которого служат все независимые множества вершин гиперграфа Н.

Очевидно, что изучая независимые множества вершин гиперграфе, естественно рассматривать гиперграфы без кратных ребер. Опишем, как каждому такому гиперграфу поставить в соответствие монотонную булеву функцию. Пусть Н — гиперграф, VH =(1,2, ..., п), x_v=( х₁,х₂, ..., х_п) — характеристический вектор произвольного подмножества U € VH. Определим булеву функцию f_H, Положив f_H (x)=0 для n-мерного (0, 1)-вектора х = х_v Тогда и только тогда, когда U € ГH. Поскольку любое подмножество независимого множества также независимо, то функция f_H монотонна и f_n (0, 0, ..., 0) = 0.

Соответствие Н -> f_H не является, вообще говоря, инъективным, поскольку ребра гиперграфа могут содержаться одно в другом. Поэтому определенный интерес представляют гиперграфы специального вида — антицепи. Гиперграф называется антицепью, если никакое из его ребер в является подмножеством другого ребра. Очевидно, что все k-однородные гиперграфы и, в частности, все простые графы — антицепи.

Пусть Н — произвольная антицепь с непустым мно­жеством ребер, VH = {1, 2, ..., п). Очевидно, что харак­теристические векторы ребер гиперграфа Н попарно не­сравнимы относительно порядка ≤: x=( х₁, х₂, ..., х_п)≤ y=( y₁, y₂, ..., y_п) <=> (x_i ≤ y_i i = 1, п). Поэтому суще­ствует единственная монотонная булева функция п пере­менных, множество нижних единиц которой совпадает с множеством всех характеристических векторов ребер ги­перграфа H. Очевидно, что f_H и есть такая функция. Для антицепи, не имеющей ребер, f_H = 0.

С другой стороны, пусть f — монотонная булева функ­ция п переменных, f ≠ 1. Определим гиперграф H_f, поло­жив VH_f = {1, 2, ..., п) и объявив ребрами все подмно­жества в VH_f, характеристические векторы которых слу­жат нижними единицами функции f_H. Поскольку эта функ­ция монотонна, то гиперграф H_f окажется антицепью. Очевидно, что f_{H f} = f.

Итак, соответствие f -> H_f — биекция между мно­жеством монотонных булевых функций, отличных от тож­дественно равной 1, и множеством антицепей.

П усть теперь А — произвольная m X n-матрица без ну­левых столбцов, элементы которой — неотрицательные ве­щественные числа. Рассмотрим систему линейных нера­венств

Здесь X — столбец неизвестных x₁, x₂ ,.. ,x_n, В — стол­бец высоты m с неотрицательными элементами. Нас бу­дут интересовать (0, 1)-решения этой системы. Определим булеву функцию f п переменных, положив f(x₁, x₂ ,.. ,x_n) = 0 тогда и только тогда, когда (x₁, x₂ ,.. ,x_n) — решение системы (1). Очевидно, что f — монотонная функ­ция и f (0, 0, ..., 0) = 0. Скажем, что функция f задается системой неравенств (1).

Л егко понять, что любая монотонная булева функция, отличная от тождественно равной 1, задается некоторой системой линейных неравенств вида (1) с неотрицатель­ными коэффициентами и правыми частями. В самом де­ле, пусть f — такая функция, H_f — соответствующая ан­тицепь, VH_f = (1, 2, ..., п), EH_f = {e₁ , е₂, ...., е_m },|e_i| = n_i (i = 1, m). Рассмотрим систему неравенств

Очевидно, что вектор х = x_U = (x₁, x₂ ,.. ,x_n) — решение этой системы тогда и только тогда, когда U € SH. Последнее означает, что f_{H f} = 0. Но f_Hf = f , следовательно, функция f задается системой (2).

Если же антицепь H_i не имеет ребер, т. е. если f=0, то в качестве системы неравенств (2) можно взять си­стему x_i ≤ 1 (i = 1, п).

Очевидно, что система неравенств, задающая монотон­ную булеву функцию, определяется неоднозначно.

Из всего сказанного выше очевидно вытекает сле­дующее

Утверждение 69.1. Пусть f — монотонная булева функция, отличная от тождественно равной 1, (1)—за­дающая эту функцию система линейных неравенств, H_f — соответствующая антицепь, VH_f = (1, 2, ...,п), U € VH_f, x_U — характеристический вектор подмножества U. Тогда следующие высказывания эквивалентны:

1. f (x_U)=0;

2. вектор x_U является решением системы (1);

3. U€ГH_f.

Для того частного случая, когда все нижние единицы функции f имеют норму 2 (функция f графическая), ука­занная связь между функциями, системами неравенств и антицепями отмечалась ранее в § 28. В этой и только в этой ситуации антицепь H_f является простым графом.

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