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

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

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

В математике, для заданного семейства множеств ${\displaystyle S}$, трансверсаль (также называемая в некоторой зарубежной литературе сечением (англ. cross-section)^[1][2][3]) - это множество, содержащее ровно один элемент из каждого множества из ${\displaystyle S}$. Когда множества из ${\displaystyle S}$  не пересекаются друг с другом, каждый элемент трансверсали соответствует ровно одному элементу ${\displaystyle S}$  (множество, членом которого он является). Если исходные множества являются пересекающимися, существует два варианта определения трансверсали. Первый вариант имитирует ситуацию, когда множества взаимно не пересекаются, заключается в существовании биекции ${\displaystyle \varphi }$ от трансверсали к ${\displaystyle S}$, так что для каждого ${\displaystyle x}$ в трансверсали получаем, что ${\displaystyle x}$ отображается в некоторый элемент ${\displaystyle \varphi (x)}$ . В этом случае трансверсаль также называется системой различных представителей. Другой, менее используемый вариант не требует взаимно однозначного отношения между элементами трансверсали и множествами из ${\displaystyle S}$. В этой ситуации элементы системы представителей не обязательно различны^[4][5]. Далее приведены строгие определения наиболее распространённых подходов.

Определения[править | править код]

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

Вектор ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ из элементов множества ${\displaystyle X}$ называется трансверсалью семейства ${\displaystyle (X_{1},X_{2},\ldots ,X_{n})}$, если выполнены следующие соотношения:

а) ${\displaystyle x_{i}\in X_{i},\forall i\in {\overline {1,n}}}$.

б) ${\displaystyle x_{i}\neq x_{j},\forall i,j\in {\overline {1,n}}}$

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

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

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

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

Примеры[править | править код]

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

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

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

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

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

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

Существование[править | править код]

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

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

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

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

Теорема Холла для трансверсалей[править | править код]

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

Частичная трансверсаль[править | править код]

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

Независимые трансверсали[править | править код]

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

Теорема Р. Радо[править | править код]

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

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

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

${\displaystyle \forall A\subset \left\{1,2,\ldots ,m\right\}\ \ \ \rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|}$ (1)

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

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

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

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

${\displaystyle \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}$ и ${\displaystyle \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)

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

С помощью условия (1) оценим снизу ранги объединения и пересечения множеств ${\displaystyle X}$ и ${\displaystyle Y}$. Поскольку ${\displaystyle 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}}}}$, выполняется неравенство ${\displaystyle \rho \left(X\bigcup {Y}\right)\geq \left|A\bigcup {B}\right|+1}$. (4)

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

Используя свойство полумодулярности ранговой функции ^[7], после сложения (4) и (5) получим: ${\displaystyle \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). Утверждение доказано. ${\displaystyle \vartriangle }$

Будем применять процедуру из утверждения до тех пор, пока у нас не останется ${\displaystyle m}$ одноэлементных множеств ${\displaystyle \left\{{{t}_{1}}\right\},\ \left\{{{t}_{2}}\right\}\ \ldots ,\ \left\{{{t}_{m}}\right\}}$. При этом ранг их объединения ${\displaystyle T=\left\{{{t}_{1}},\ {{t}_{2}},\ \ldots ,\ {{t}_{m}}\right\}}$ равен ${\displaystyle m}$. Значит, ${\displaystyle T}$ и есть искомая независимая трансверсаль. ${\displaystyle \square }$

Следствие[править | править код]

Пусть ${\displaystyle M=(E,J)}$ — матроид. Последовательность ${\displaystyle S=(S_{1},S_{2},\ldots ,S_{m})}$ непустых подмножеств множества ${\displaystyle E}$ имеет независимую частичную трансверсаль мощности ${\displaystyle t}$ тогда и только тогда, когда объединение любых ${\displaystyle k}$ подмножеств из этой последовательности содержит независимое подмножество мощности не менее ${\displaystyle k+t-m}$, т.е. ${\displaystyle \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.}$ ^[8]

Общие трансверсали[править | править код]

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

Теорема[править | править код]

Два семейства ${\displaystyle S=(S_{1},S_{2},...,S_{m})}$ и ${\displaystyle R=(R_{1},R_{2},...,R_{m})}$ непустых подмножеств конечного множества ${\displaystyle E}$ обладают общей трансверсалью тогда и только тогда, когда для любых подмножеств ${\displaystyle A}$ и ${\displaystyle B}$ множества ${\displaystyle {1,2,...,m}}$ выполняется неравенство ${\displaystyle \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.}$ ^[8].

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

Пусть ${\displaystyle S=(S_{1},S_{2},...,S_{m})}$ — семейство подмножеств некоторого множества ${\displaystyle E}$. Пусть известна матрица ${\displaystyle 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.}$.

Тогда число различных трансверсалей семейства ${\displaystyle S}$ равно перманенту матрицы ${\displaystyle A}$ . ^[9]

Cвязь с другими разделами и применение[править | править код]

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

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

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

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

Обобщение[править | править код]

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

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

1. ${\displaystyle P_{i}\subseteq S_{i}}$ для ${\displaystyle i\in \{1,2,\ldots ,m\}}$;
2. ${\displaystyle |P_{i}|=k_{i}}$;
3. ${\displaystyle 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.