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

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

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

В математике, для заданного семейства множеств $S$, трансверсаль (также называемая в некоторой зарубежной литературе сечением (англ. cross-section)) - это множество, содержащее ровно один элемент из каждого множества из $S$. Когда множества из $S$  не пересекаются друг с другом, каждый элемент трансверсали соответствует ровно одному элементу $S$  (множество, членом которого он является). Если исходные множества являются пересекающимися, существует два варианта определения трансверсали. Первый вариант имитирует ситуацию, когда множества взаимно не пересекаются, заключается в существовании биекции $\phi$ от трансверсали к $S$, так что для каждого $x$ в трансверсали получаем, что $x$ отображается в некоторый элемент $\phi (x)$ . В этом случае трансверсаль также называется системой различных представителей. Другой, менее используемый вариант не требует взаимно однозначного отношения между элементами трансверсали и множествами из $S$. В этой ситуации элементы системы представителей не обязательно различны. Далее приведены строгие определения наиболее распространённых подходов.

Определения

1) Пусть $X$ — некоторое множество. Пусть $2^X$ — булеан множества $X$, т.е. совокупность всех подмножеств множества $X$. Пусть $(X_1,X_2,\dots ,X_n)$ — некоторая выборка из $2^X$. Элементы в этой выборке могут повторяться.

Вектор $(x_1,x_2,\dots ,x_n)$ из элементов множества $X$ называется трансверсалью семейства $(X_1,X_2,\dots ,X_n)$, если выполнены следующие соотношения:

а) $x_i\in X_i,\mathrm{\forall }i\in \overline{1,n}$.

б) $x_i\ne x_j,\mathrm{\forall }i,j\in \overline{1,n}$

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

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

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

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

Примеры

1) Пусть заданы множество $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$.

2) В некотором учреждении имеется $m$ комиссий. Требуется из состава каждой комиссии назначить их председателей так, чтобы ни один человек не председательствовал более чем в одной комиссии. Здесь трансверсаль комиссий составят их председатели.

3) В теории групп для данной подгруппы $H$ группы $G$ правый (соответственно левый) трансверсаль - это множество, содержащее ровно один элемент от каждого правого (соответственно левого) смежного класса $H$. В этом случае «множества» (смежные классы) взаимно не пересекаются, т.е. смежные классы образуют разбиение группы.

4) Как частный случай предыдущего примера, учитывая прямое произведение групп $G=H\times K$, получаем, что $H$ является трансверсалью для смежных классов $K$.

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

6) Другой случай трансверсали на основе разбиения возникает, когда рассматривается отношение эквивалентности, известное как (теоретико-множественное) ядро ​​функции, определенной для функции $f$ с областью определения X, как её разбиение $\ker f:=\{\{y\in X\mid f(x)=f(y)\}\mid x\in X\}$ которое разбивает область f на классы эквивалентности, так что все элементы в классе имеют один и тот же образ при отображении f. Если f инъективна, существует только одна трансверсаль $\ker f$. Для необязательно-инъективной f исправление трансверсали T в $\ker f$ вызывает взаимно-однозначное соответствие между T и образом f, обозначаемое далее как $\mathrm{Im}f$. Следовательно, функция $g:(\mathrm{Im}f)\to T$ хорошо определяется свойством, которое для всех z : $\mathrm{Im}f,g(z)=x$ , где x - единственный элемент в T, такой что $f(x)=z$; кроме того, g может быть расширен (не обязательно единственным образом), так что он будет определен во всей области значений f путем выбора произвольных значений для g(z), когда z находится за пределами изображения f. Это простой расчет, чтобы убедиться, что определенное таким образом g обладает свойством $f\circ g\circ f=f$, что является доказательством (когда область определения и область значений f одно и тоже множество), что полугруппа полного преобразования является регулярной полугруппой. Отображение $g$ действует как (не обязательно единственный) квазиобратный элемент для f; в теории полугрупп это просто обратный элемент. Однако обратите внимание, что для произвольного g с вышеупомянутым свойством «двойственное» уравнение $g\circ f\circ g=g$ может не выполняться, но если мы обозначим $h=g\circ f\circ g$, то f является квазиобратным к h, то есть $h\circ f\circ h=h$.

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

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

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

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

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

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

Пусть $E$ - непустое конечное множество и $S=\{S_1,S_2,...,S_m\}$ - семейство не обязательно разных непустых его подмножеств. В таком случае $S$ имеет трансверсаль тогда и только тогда, когда для произвольных $k$ подмножеств $S_i$ их объединение включает не менее, чем $k$ разных элементов $(k=1,2,...,m)$.

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

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

Независимые трансверсали

Пусть на множестве $E$ задан некоторый матроид.Пусть $S=(S_1,S_2,...,S_m)$ — семейство подмножеств множества $E$. Независимой трансверсалью для $S$ назовём трансверсаль, которая является независимым множеством в смысле указанного матроида. В частности, если матроид - дискретный, то любая трансверсаль - независимая. Следующая теорема даёт критерий существования независимой трансверсали.

Теорема Р. Радо

Пусть $M=(E,J)$ — матроид. Последовательность $S=(S_1,S_2,\dots ,S_m)$ — непустых подмножеств множества $E$ имеет независимую трансверсаль тогда и только тогда, когда объединение любых $k$ подмножеств из этой последовательности содержит независимое множество, в котором не менее $k$ элементов, где $k$ — произвольное натуральное число, не превосходящее $m$.

Доказательство:

$◻$ Условие теоремы удобно сформулировать, используя понятие ранга множества (наибольшей мощности независимого подмножества):

$\mathrm{\forall }A\subset \{1,2,\dots ,m\}\rho \left(\bigcup _{i\in A}{S}_i\right)\ge \left|A\right|$ (1)

Необходимость. Если имеется независимая трансверсаль, то её пересечение с множеством $\bigcup _{i\in A}{S}_i$ имеет $\left|A\right|$ элементов, откуда $\rho \left(\bigcup _{i\in A}{S}_i\right)\ge \left|A\right|$.

Достаточность. Предварительно докажем следующее утверждение:

Утверждение. Если в некотором множестве (например, $S_1$) содержится не менее двух элементов, то из этого множества можно удалить один элемент, не нарушив при этом условия (1).

$△$ От противного: пусть $\left|S_1\right|\ge 2$ и, какой элемент ни удалить из $S_1$, условие (1) не будет выполнено. Возьмём два элемента $x$ и $y$ из множества $S_1$. Для них найдутся такие множества индексов $A\text{'}=\left\{1\right\}\bigcup A$ и $B\text{'}=\left\{1\right\}\bigcup B$, где $A,B\subset \{2,3,\dots ,m\}$, что

$\rho \left(\bigcup _{i\in A}{S}_i(\bigcup S_1\mathrm{\setminus }\left\{x\right\})\right)<\left|A^{\prime }\right|=\left|A\right|+1$ и $\rho \left(\bigcup _{i\in B}{S}_i(\bigcup S_1\mathrm{\setminus }\left\{y\right\})\right)<\left|B^{\prime }\right|=\left|B\right|+1$ . (2)

Положим: $X=\bigcup _{i\in A}{S}_i\bigcup \left(S_1\mathrm{\setminus }\left\{x\right\}\right)$, $Y=\bigcup _{i\in B}{S}_i\bigcup \left(S_1\mathrm{\setminus }\left\{y\right\}\right)$. Соотношения (2) перепишем в виде: $\rho \left(X\right)\le \left|A\right|;\rho \left(Y\right)\le \left|B\right|$, откуда $\rho \left(X\right)+\rho \left(Y\right)\le \left|A\right|+\left|B\right|$. (3)

С помощью условия (1) оценим снизу ранги объединения и пересечения множеств $X$ и $Y$. Поскольку $X\bigcup Y=\bigcup _{i\in A\bigcup B}{S}_i\bigcup \left(S_1\mathrm{\setminus }\left\{x\right\}\right)\bigcup \left(S_1\mathrm{\setminus }\left\{y\right\}\right)=\bigcup _{i\in A\bigcup B}{S}_i\bigcup S_1$, выполняется неравенство $\rho (X\bigcup Y)\ge |A\bigcup B|+1$. (4)

В силу того, что $X\bigcap Y\supset \bigcup _{i\in A\bigcap B}{S}_i$, имеем $\rho (X\bigcap Y)\ge |A\bigcap B|$. (5)

Используя свойство полумодулярности ранговой функции , после сложения (4) и (5) получим: $\rho \left(X\right)+\rho \left(Y\right)\ge \rho (X\bigcup Y)+\rho (X\bigcap Y)\ge |A\bigcup B|+|A\bigcap B|+1=\left|A\right|+\left|B\right|+1$. (6)

Неравенство (6) противоречит неравенству (3). Утверждение доказано. $△$

Будем применять процедуру из утверждения до тех пор, пока у нас не останется $m$ одноэлементных множеств $\left\{t_1\right\},\left\{t_2\right\}\dots ,\left\{t_m\right\}$. При этом ранг их объединения $T=\{t_1,t_2,\dots ,t_m\}$ равен $m$. Значит, $T$ и есть искомая независимая трансверсаль. $◻$

Следствие

Пусть $M=(E,J)$ — матроид. Последовательность $S=(S_1,S_2,\dots ,S_m)$ непустых подмножеств множества $E$ имеет независимую частичную трансверсаль мощности $t$ тогда и только тогда, когда объединение любых $k$ подмножеств из этой последовательности содержит независимое подмножество мощности не менее $k+t-m$, т.е. $\mathrm{\forall }A\subset \{1,2,\dots ,m\}\rho \left(\bigcup _{i\in A}S{}_i\right)\ge \left|A\right|+t-m.$

Общие трансверсали

Критерий существования независимой трансверсали позволяет получить необходимое и достаточное условия существования общей трансверсали у двух различных систем подмножеств одного и того же множества.

Теорема

Два семейства $S=(S_1,S_2,...,S_m)$ и $R=(R_1,R_2,...,R_m)$ непустых подмножеств конечного множества $E$ обладают общей трансверсалью тогда и только тогда, когда для любых подмножеств $A$ и $B$ множества $1,2,...,m$ выполняется неравенство $|\left(\bigcup _{i\in A}{S}_i\right)\bigcap \left(\bigcup _{i\in B}{R}_i\right)|\ge \left|A\right|+\left|B\right|-m.$ .

Теорема о числе различных трансверсалей семейства подмножеств

Пусть $S=(S_1,S_2,...,S_m)$ — семейство подмножеств некоторого множества $E$. Пусть известна матрица $A={\left(a_{ij}\right)}_{nxn}=\{\begin{array}{rl}& 0,x_j\notin S_i\\ & 1,x_j\in S_i\\ \end{array}$.

Тогда число различных трансверсалей семейства $S$ равно перманенту матрицы $A$ .

Cвязь с другими разделами и применение

В теории оптимизации и теории графов нахождение общей трансверсали может быть сведено к нахождению максимального потока в сети .

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

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

Применение трансверсалей и покрытий из них лежит в основе метода Эйлера — Паркера поиска ортогональных латинских квадратов к заданному латинскому квадрату.

Обобщение

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

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

1. $P_i\subseteq S_i$ для $i\in \{1,2,\dots ,m\}$;
2. $|P_i|=k_i$;
3. $P_i\cap P_j=\varnothing ,i\ne j$.

Литература

• М.Л. Краснов, А.И. Киселев, Г.И. Макаренко, Е.В. Шикин, В.И. Заляпин, А.Ю. Эвнин. Вся высшая математика: Учебник. — М.: КомКнига, 2006. — Т. 7. — 208 с. — ISBN 5-484-00521-3.

• М. Холл. Глава №5 «Системы различных представителей» // Комбинаторика = Combinatorial Theory / пер. с англ. С. А. Широковой; под ред. А. О. Гельфонда и В. Е. Тараканова. — М.: Мир, 1970. — С. 65—78. — 424 с.
• В.Н.Сачков. Введение в комбинаторные методы дискретной математики. — М.: Наука. Гл. ред. физ.-мат. лит., 1982. — 384 с.

• М. Свами, К. Тхуласираман. Глава №8.6 «Паросочетания в двудольных графах» // Графы, сети и алгоритмы = Graphs, Networks, and Algorithms / пер. с англ. М. В. Горбатовой, В. Л. Торхова, С. А. Фролова, В. Н. Четверикова; под ред. В. А. Горбатова. — М.: Мир, 1984. — С. 165—166. — 455 с. — 11 000 экз.
• В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. — М.: Наука, 1990. — С. 87—92. — 384 с. — ISBN 5-02-013992-0.
• Н. И. Костюкова. Графы и их применение  (неопр.). — Лекция №16: Теория трансверсалей. Дата обращения: 29 июля 2009.
• Alexander Schrijver. Chapter 22 «Transversals», chapter 23 «Common transversals» // Combinatorial optimization. — Springer, 2003. — P. 378—409. — 1800 p. — ISBN 978-3540443896.
• Roberts F., Tesman B. Applied Combinatorics. — Boca Raton: CRC Press, 2009. — ISBN 978-1-4200-9982-9.
• Brualdi R. Introductory Combinatorics. — Upper Saddle River, NJ: Prentice Hall, 2010. — ISBN 0-13-602040-2.