Заметка о теореме Холла

Хорошо известно утверждение Холла о системе представителей. Задано конечное множество элементов S : {ai, ...а_г} и класс его подмножеств F : Si,..., Sz С S.

Определение 1. Множество элементов Н : {а^,...,^ е S} (zi,...,?/ — попарно различные индексы из множества {1,..., г}) называется системой представителей для класса F, если выполнены условия: a^ G Sy,...^^ Е Si.

Не теряя общности, считаем, что элементы в множествах класса F не повторяются и допускаем повторение множеств St в классе F.

Теорема Холла. Для класса F система представителей существует тогда и только тогда, когда для любой выборки множеств S^, ...,Si_t (ii,...,it — попарно различные индексы из множества {1, ...,Z}, t — произвольное целое не большее I) из класса F выполнено условие:

(с) Г.Н. Копылов, В.Н. Лебедев, 2006

\8^.„.к3 8ц\>1                         (1)

Доказательство этого утверждения можно найти в [1].

1.    Критерий группы представителей

Мы рассматриваем обобщение системы представителей.

' Определение 2. Группой представителей назовем класс множеств G : Gi,..., Gi такой, что выполнены следующие условия;

GyCSy,\Gy\ = ky,i = l,...,V,                         (2)

СуПСз = Ф,г^зЛз = 1,..,1.                   (3)

Замечание: элементы в множествах класса G не повторяются.

Справедлив следующий критерий наличия группы представителей для заданного класса множеств F.

Критерий. Группа представителей G для данного класса множеств F : Sy, ...,Si существует тогда и только тогда, когда выполнено следующее условие. Для любого натурального t < I и любой выборки t множеств Sy_v....,Sy_t (гу,...,!,! — попарно различные индексы из множества {1,...,/}) справедливо:

t

Доказательство построено сведением к утверждению Холла.

Рассматриваем тройку Т : (S^F;^ (S : {ai, ...а_г} — множество элементов; F : Sy С S,..., Si С S — класс его подмножеств; k : F —► {1, ...,г}, ку > |Sj|, г = 1,..., I — целочисленная функция на классе F. Не теряя общности, считаем, что элементы в множествах не повторяются и допускаем повторение множеств.

Рассмотрим следующую пару R : (S; F'), где F' следующий класс подмножеств множества S; множество Sy повторяем ку раз, г = 1...Z. В результате получим класс из h = 52-₌₁ ку множеств. Несложно показать, что для тройки Т : (S;F;k) существует группа представителей, тогда и только тогда, когда для двойки R : (S;F') существует система представителей.

Теперь можно использовать теорему Холла.

Необходимость. Пусть существует группа представителей для тройки Т : (S; F\ к) Поэтому существует система представителей для двойки R : (5; F'\ Поэтому по теореме Холла для любой выборки множеств Sy₁,...,Sy_t (iy,...,it — попарно различные индексы из множества {l,...,h}, t — произвольное натуральное не большее h) из класса F' выполнено условие (1)

Рассмотрим полные выборки, то есть такие, в которых вместе с множеством Sy присутствуют и все его копии. Тогда условие (1) непосредственно дает условие (4). • Достаточность. Пусть теперь выполнено условие (4) критерия группы представителей. Для любого натурального t < I и любой выборки t множеств Sy₁,...₁Sy_t (zi,...,i_t — попарно различные индексы из множества {1,...,/}) справедливо:

.                                                                                                                                                                t

| Sy₁ U .... U S_it | >  У^ ку^.

j=i

Рассмотрим произвольную выборку S^,..., Si_t (?i,...,z_t — попарно различные индексы из множества {1,7г}, t — произвольное натуральное не большее А) для класса F'. Тогда будет выполнено условие (1): jS^ U .... U 5^| >  t. Действительно, неравенство выше следует из более сильного неравенства (4) для пополненной выборки (вместе с множеством St пополненная выборка содержит и все копии первоначальной; при этом объединение множеств останется тем же, а число множеств увеличится).

2.    Сложностные аспекты поиска группы представителей

Теперь мы рассмотрим вопрос алгоритмической сложности определения группы представителей.

ЗАДАЧА. Задана тройка Т : (S;F;fc) (S : {ai,... a_r} — множество элементов; F : Si С S, ...,Si С 5 — класс его подмножеств; к ; F —* {!,..., г}, /с,-< [5,1, г = 1, ...Д — целочисленная функция на классе F).

ВОПРОС: Существует ли для данной тройки Т группа представителей или нет?

Непосредственно из доказанного критерия следует, что сформулированная выше задача относится к классу NP О со — NP, то есть и множество задач с ответом «да» и множество задач с ответом «нет» распознаются за недетерминированное полиномиальное время.

Достаточно просто решить данную задачу и за полиномиальное детерминированное время. Действительно, рассмотрим следующую систему линейных неравенств с целочисленными переменными. Введем п = rl переменных ж^Д = l...r; j = 1...Z. И рассмотрим следующую систему линейных неравенств:

^2 3Cij < 1, г = 1-г;

^2 3Cij = kj, j = 1...Z;                              (5)

i=l...r

0 <  Xtj < 1, г = l...r; j = 1...Z.

Просто показать, что для тройки Т : (St^k) существует группа представителей тогда и только тогда, когда система (5) имеет целочисленное решение. Матрица ограничений задачи унимодулярна. Покажем индукцией по размеру квадратной подматрицы, что определитель любой квадратной подматрицы ограничений задачи (5) из множества {1, —1,0} (здесь используется известная техника, которую можно найти в [2]).

Достаточно рассмотреть только подматрицы верхних двух групп неравенств (если подматрица содержит строку из третьей группы, то эта строка содержит не более одного ненулевого элемента и можно провести индуктивный переход).

Начальный шаг индукции, очевидно, справедлив. Рассмотрим какую-либо квадратную подматрицу размера m, т. Если подматрица имеет столбец, в котором не более одного единичного элемента, то, раскладывая определитель по этому столбцу и применяя индуктивное предположение, получаем требуемое. Поэтому будем

= 42                                 Г.Н. Копылов, В.Н. Лебедев. Заметка о теореме Холла считать, что каждый столбец подматрицы содержит ровно две единицы (каждая переменная жу входит один раз в неравенства верхней группы г = 1...г и один раз в неравенства второй группы у = 1...Z). В этом случае суммируем строки подматрицы, относящиеся к первой группе неравенств, и затем суммируем строки, относящиеся ко второй группе неравенств, получим две одинаковые единичные строки, поэтому определитель такой подматрицы нулевой.

Теперь используем полиномиальный алгоритм решения задачи линейного программирования. Например, алгоритм Хачияна [2]. Многогранник ограничений системы линейных неравенств с унимодулярной матрицей ограничений и целочисленной правой частью имеет только целочисленные вершины. Поэтому, если при решении задачи (5) без ограничения на целочисленность найдено решение, то можно утверждать о наличии и целочисленного решения для задачи (5) (многогранник ограничений системы ограничен — решения находятся в кубе; поэтому, если многогранник не пуст, то наличие вершины гарантируется). .

В силу сведения задачи поиска группы представителей к задаче поиска системы представителей, можно применить и более эффективные полиномиальные алгоритмы, например, венгерский алгоритм из [2].