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

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

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

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

ОпределенияПравить

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

Вектор $(x_1,x_2,\dots <!--\; \dots \; -->,x_n)$$(x_{1},x_{2},\ldots ,x_{n})$  из элементов множества $X$$X$  называется трансверсалью семейства $(X_1,X_2,\dots <!--\; \dots \; -->,X_n)$$(X_{1},X_{2},\ldots ,X_{n})$ , если выполнены следующие соотношения:

а) $x_i\in <!--\; \in \; -->X_i,\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->\stackrel{¯<!--\; ¯\; -->}{1,n}$$x_{i}\in X_{i},\forall i\in {\overline {1,n}}$ .

б) $x_i\ne <!--\; \ne \; -->x_j,\mathrm{\forall <!--\; \forall \; -->}i,j\in <!--\; \in \; -->\stackrel{¯<!--\; ¯\; -->}{1,n}$$x_{i}\neq x_{j},\forall i,j\in {\overline {1,n}}$ 

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

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

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

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

ПримерыПравить

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

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

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

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

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

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

СуществованиеПравить

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

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

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

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

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

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

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

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

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

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

Теорема Р. РадоПравить

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

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

$\mathrm{◻<!--\; ◻\; -->}$$\square$  Условие теоремы удобно сформулировать, используя понятие ранга множества (наибольшей мощности независимого подмножества):

$\mathrm{\forall <!--\; \forall \; -->}A\subset <!--\; \subset \; -->\left\{1,2,\dots <!--\; \dots \; -->,m\right\}\mathrm{\rho <!--\; \rho \; -->}\left(\underset{i\in <!--\; \in \; -->A}{\bigcup <!--\; \bigcup \; -->}{S}_i\right)\ge <!--\; \ge \; -->\left|A\right|$$\forall A\subset \left\{1,2,\ldots ,m\right\}\ \ \ \rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|$  (1)

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

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

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

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

$\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\left(\bigcup {{{S}_{1}}\backslash \left\{x\right\}}\right)\right)<\left|{{A}'}\right|=\left|A\right|+1$  и $\rho \left(\bigcup \limits _{i\in B}{{S}_{i}}\left(\bigcup {{{S}_{1}}\backslash \left\{y\right\}}\right)\right)<\left|{{B}'}\right|=\left|B\right|+1$  . (2)

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

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

В силу того, что $X\bigcap <!--\; \bigcap \; -->Y\supset <!--\; \supset \; -->\underset{i\in <!--\; \in \; -->A\bigcap <!--\; \bigcap \; -->B}{\bigcup <!--\; \bigcup \; -->}{S}_i$$X\bigcap {Y}\supset \bigcup \limits _{i\in A\bigcap {B}}{{S}_{i}}$ , имеем $\mathrm{\rho <!--\; \rho \; -->}\left(X\bigcap <!--\; \bigcap \; -->Y\right)\ge <!--\; \ge \; -->\left|A\bigcap <!--\; \bigcap \; -->B\right|$$\rho \left(X\bigcap {Y}\right)\geq \left|A\bigcap {B}\right|$ . (5)

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

Неравенство (6) противоречит неравенству (3). Утверждение доказано. $△<!--\; △\; -->$$\vartriangle$ 

Будем применять процедуру из утверждения до тех пор, пока у нас не останется $m$$m$  одноэлементных множеств $\left\{t_1\right\},\left\{t_2\right\}\dots <!--\; \dots \; -->,\left\{t_m\right\}$$\left\{{{t}_{1}}\right\},\ \left\{{{t}_{2}}\right\}\ \ldots ,\ \left\{{{t}_{m}}\right\}$ . При этом ранг их объединения $T=\left\{t_1,t_2,\dots <!--\; \dots \; -->,t_m\right\}$$T=\left\{{{t}_{1}},\ {{t}_{2}},\ \ldots ,\ {{t}_{m}}\right\}$  равен $m$$m$ . Значит, $T$$T$  и есть искомая независимая трансверсаль. $\mathrm{◻<!--\; ◻\; -->}$$\square$ 

СледствиеПравить

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

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

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

ТеоремаПравить

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

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

Пусть $S=(S_1,S_2,...,S_m)$$S=(S_{1},S_{2},...,S_{m})$  — семейство подмножеств некоторого множества $E$$E$ . Пусть известна матрица $A={{\left({{a}_{ij}}\right)}_{n\ x\,n}}=\left\{{\begin{aligned}&0,\ \ {{x}_{j}}\notin {{S}_{i}}\\&1,\ \ {{x}_{j}}\in {{S}_{i}}\\\end{aligned}}\right.$ .

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

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

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

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

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

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

ОбобщениеПравить

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

Пусть имеется последовательность целых положительных чисел $(k_1,k_2,\dots <!--\; \dots \; -->,k_m)$$(k_{1},k_{2},\ldots ,k_{m})$ . Тогда $(k_1,k_2,\dots <!--\; \dots \; -->,k_m)$$(k_{1},k_{2},\ldots ,k_{m})$ -трансверсалью семейства $S$$S$  будет семейство $P=(P_1,P_2,\dots <!--\; \dots \; -->,P_m)$$P=(P_{1},P_{2},\ldots ,P_{m})$  подмножеств множества $E$$E$ , для которого выполняются условия:

1. $P_i\subseteq <!--\; \subseteq \; -->S_i$$P_{i}\subseteq S_{i}$  для $i\in <!--\; \in \; -->\{1,2,\dots <!--\; \dots \; -->,m\}$$i\in \{1,2,\ldots ,m\}$ ;
2. $|P_i|=k_i$$|P_{i}|=k_{i}$ ;
3. $P_i\cap <!--\; \cap \; -->P_j=\mathrm{\varnothing <!--\; \varnothing \; -->},i\ne <!--\; \ne \; -->j$$P_{i}\cap P_{j}=\varnothing ,i\neq 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.