Теорема Холла для трансверсалей

Пусть S = {S₁, …, S_m} – семейство подмножеств непустого конечного множества Е. Тогда S имеет трансверсаль в том и только в том случае, если для любых k подмножеств S_i их объединение содержит по меньшей мере k разных элементов.

Замечание. Множество всех трансверсалей данной системы множеств S является матроидом.

Рассмотрим некоторые применения теоремы Холла.

1. Есть множество работ, которые должны быть выполнены, и множество рабочих, каждый из которых может выполнять несколько работ. Когда можно распределить работы между рабочими так, чтобы каждый выполнял свою работу?

2. Латинским (m‰n) прямоугольником назвается матрица A_m_‰_n, элементами которой являются натуральные числа a _ij, удовлетворяющие условиям:

1) 1£ a _ij £ m;

2) элементы a _ij в каждой строке и каждом столбце различны.

Следует отметить, что из этих условий вытекает неравенство m £ n. Если же m = n, то латинский прямоугольник называется латинским квадратом.

Выясним такой вопрос: если задан латинский прямоугольник, то при каких условях можно присоединить новые строки так, чтобы получить латинский квадрат? Ответ: всегда.

3. Общие трансверсали. Если Е – непустое конечное множество, S и T – два семейства его непустых подмножеств, то интересно знать, когда существует общая трасверсаль для S и T, т.е. множество, состоящее из m различных элементов множества Е и являющееся трансверсалью и для S, и для T. Задача составления расписаний. Пусть Е – множество отрезков времени, в которые могут читаться лекции; S_i – множество отрезков времени, в которые данные m лекторов желают читать лекции, T_i – множества отрезков времени, в которые свободны лекционных аудиторий. Тогда, найдя общую трансверсаль для S и T, мы сможем предоставить каждому лектору свободную аудиторию в удобное для него время.

Необходимое и достаточное условие: для "A,BÍ{1, 2, …,m} имеет место