Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

Очевидно, что изучая независимые множества вершин гиперграфе, естественно рассматривать гиперграфы без кратных ребер. Опишем, как каждому такому гиперграфу поставить в соответствие монотонную булеву функцию. Пусть Н — гиперграф, VH =( 1, 2,..., п), xv=(х12,..., хп) — характеристический вектор произвольного подмножества UVH. Определим булеву функцию fH, Положив fH (x)= 0 для n -мерного (0, 1)-вектора х = хv Тогда и только тогда, когда UГH. Поскольку любое подмножество независимого множества также независимо, то функция fH монотонна и fn (0, 0,..., 0) = 0.

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

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

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

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

 
 

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

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

 
 

Легко понять, что любая монотонная булева функция, отличная от тождественно равной 1, задается некоторой системой линейных неравенств вида (1) с неотрицатель­ными коэффициентами и правыми частями. В самом де­ле, пусть f — такая функция, Hf — соответствующая ан­тицепь, VHf = ( 1, 2,..., п), EHf = {e1, е2,...., еm },|ei| = ni (i = 1, m). Рассмотрим систему неравенств

Очевидно, что вектор х = xU = (x1, x2 ,..,xn) — решение этой системы тогда и только тогда, когда U € SH. Последнее означает, что fH f = 0. Но fHf = f, следовательно, функция f задается системой (2).

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

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

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

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

1) f (xU)=0;

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

3) U€ГHf.

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

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





Дата публикования: 2015-01-23; Прочитано: 260 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.014 с)...