Трансверсаль

Не путать с трансверсалью треугольника.

Трансверса́ль (система различных представителей) — понятие из теории множеств, которое является достаточно важным для всей дискретной математики. Оно также существует в логике и линейной алгебре.

Определение

Обозначим как $E$ конечное непустое множество, а как $S = (S_1, S_2, \ldots, S_m)$ — семейство его подмножеств, то есть последовательность непустых подмножеств $E$ длины $m$.

Трансверсалью семейства $S$ является такое подмножество $T \subseteq E$, для которого существует биекция $\phi : T \rightarrow {1, 2, \ldots, m}$, причём для $\forall t \in T$ выполняется условие $t \in S_{\phi(t)}$.

Другими словами, для элементов трансверсали существует такая нумерация, при которой $t_i \in S_i, i=1, 2, \ldots, m$.

Поскольку $T$ — множество, то все его элементы различны, отсюда и название «система различных представителей».

Пример

Пусть заданы множество $E = \{1, 2, 3, 4, 5\}$ и семейство подмножеств $S = \{S_1 = \{1, 4, 5\}, S_2 = \{1\}, S_3 = \{2, 3, 4\}, S_4 = \{2, 4\}\}$. Примером трансверсали для такого семейства может служить $T = \{1, 2, 3, 4\}$, в котором $1 \in S_2, 2 \in S_4, 3 \in S_3, 4 \in S_1$.

Частичная трансверсаль

В случае, если $\phi$ — инъекция, то трансверсаль называется частичной. Частичные трансверсали семейства $S$ являются трансверсалями его подсемейств. Любое подмножество трансверсали является частичной трансверсалью.

Существование

На практике чаще важен ответ на вопрос, существует ли трансверсаль для конкретного семейства. Некоторой шуточной формулировкой этого вопроса является задача о свадьбах:

Пусть имеется некоторое множество юношей и некоторое множество девушек. При этом каждый юноша из первого множества знаком с несколькими девушками из второго. Требуется женить всех юношей так, чтобы каждый сочетался моногамным браком со знакомой ему девушкой.

Эта задача имеет решение, если для семейства множеств, образованных из девушек, знакомых с конкретным юношей, существует трансверсаль.

Строгим решением задачи о существовании трансверсали является теорема Холла, а также её обобщение — теорема Радо.

Обобщение

Понятие трансверсали можно обобщить.

Пусть имеется последовательность целых положительных чисел $(k_1, k_2, \ldots, k_m)$. Тогда $(k_1, k_2, \ldots, k_m)$-трансверсалью семейства $S$ будет семейство $P = (P_1, P_2, \ldots, P_m)$ подмножеств множества $E$, для которого выполняются условия:

1. $P_i \subseteq S_i, i = 1, 2, \ldots, m$;
2. $\mathcal {j}P_i\mathcal {j} = k_i$;
3. $P_i \bigcap P_j = \varnothing, i \neq j$.

Литература

• М. Холл Глава №5 «Системы различных представителей» // Комбинаторика = Combinatorial Theory / пер. с англ. С. А. Широковой; под ред. А. О. Гельфонда и В. Е. Тараканова. — М.: Мир, 1970. — С. 65—78. — 424 с.
• М. Свами, К. Тхуласираман Глава №8.6 «Паросочетания в двудольных графах» // Графы, сети и алгоритмы = Graphs, Networks, and Algorithms / пер. с англ. М. В. Горбатовой, В. Л. Торхова, С. А. Фролова, В. Н. Четверикова; под ред. В. А. Горбатова. — М.: Мир, 1984. — С. 165—166. — 455 с. — 11 000 экз.
• В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич Лекции по теории графов. — М.: Наука, 1990. — С. 87—92. — 384 с. — ISBN 5-02-013992-0
• Н. И. Костюкова Графы и их применение. — Лекция №16: Теория трансверсалей. Архивировано из первоисточника 4 апреля 2012. Проверено 29 июля 2009.
• Alexander Schrijver Chapter 22 «Transversals», chapter 23 «Common transversals» // Combinatorial optimization. — Springer, 2003. — P. 378—409. — 1800 p. — ISBN 978-3540443896