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

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

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

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

Определения

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

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

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

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

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

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

Другими словами, для элементов трансверсали существует такая нумерация, при которой $t_{i}\in S_{i}$ для $i\in \{1,2,\ldots ,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, как её разбиение $\operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X\,\right\}$ которое разбивает область f на классы эквивалентности, так что все элементы в классе имеют один и тот же образ при отображении f. Если f инъективна, существует только одна трансверсаль $\operatorname {ker} f$ . Для необязательно-инъективной f исправление трансверсали T в $\operatorname {ker} f$ вызывает взаимно-однозначное соответствие между T и образом f, обозначаемое далее как $\operatorname {Im} f$ . Следовательно, функция $g:(\operatorname {Im} f)\to T$ хорошо определяется свойством, которое для всех z : $\operatorname {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=\left\{S_{1},S_{2},...,S_{m}\right\}$ - семейство не обязательно разных непустых его подмножеств. В таком случае $S$ имеет трансверсаль тогда и только тогда, когда для произвольных $k$ подмножеств $S_{i}$ их объединение включает не менее, чем $k$ разных элементов $(k=1,2,...,m)$ [6].

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

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

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

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

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

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

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

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

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

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

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

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

$\vartriangle$ От противного: пусть $\left|{{S}_{1}}\right|\geq 2$ и, какой элемент ни удалить из $S_{1}$ , условие (1) не будет выполнено. Возьмём два элемента $x$ и $y$ из множества $S_{1}$ . Для них найдутся такие множества индексов ${A}'=\left\{1\right\}\bigcup A$ и ${B}'=\left\{1\right\}\bigcup B$ , где $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=\bigcup \limits _{i\in A}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{x\right\}\right)}$ , $Y=\bigcup \limits _{i\in B}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{y\right\}\right)}$ . Соотношения (2) перепишем в виде: $\rho \left(X\right)\leq \left|A\right|;\ \rho \left(Y\right)\leq \left|B\right|$ , откуда $\rho \left(X\right)+\ \rho \left(Y\right)\leq \left|A\right|+\left|B\right|$ . (3)

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

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

Используя свойство полумодулярности ранговой функции [7], после сложения (4) и (5) получим: $\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$ одноэлементных множеств $\left\{{{t}_{1}}\right\},\ \left\{{{t}_{2}}\right\}\ \ldots ,\ \left\{{{t}_{m}}\right\}$ . При этом ранг их объединения $T=\left\{{{t}_{1}},\ {{t}_{2}},\ \ldots ,\ {{t}_{m}}\right\}$ равен $m$ . Значит, $T$ и есть искомая независимая трансверсаль. $\square$

Следствие

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

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

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

Теорема

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

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

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

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

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

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

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

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

Обобщение

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

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

$P_{i}\subseteq S_{i}$ для $i\in \{1,2,\ldots ,m\}$ ;
$|P_{i}|=k_{i}$ ;
$P_{i}\cap P_{j}=\varnothing ,i\neq j$ .

Примечания

John Mackintosh Howie Fundamentals of Semigroup Theory (англ.). — Oxford University Press, 1995. — P. 63. — ISBN 978-0-19-851194-6.
Clive Reis. Abstract Algebra: An Introduction to Groups, Rings and Fields (англ.). — World Scientific, 2011. — P. 57. — ISBN 978-981-4335-64-5.
Bruno Courcelle; Joost Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach (англ.). — Cambridge University Press, 2012. — P. 95. — ISBN 978-1-139-64400-6.
Roberts, Tesman, 2009, с. 692.
Brualdi, 2010, с. 322.
Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. - СПб., БХВ-Петербург, 2004. - isbn 5-94157-546-7. - c. 529
Ранговая функция, полумодулярность (неопр.). Wiki-конспекты ИТМО. Дата обращения: 6 декабря 2019. Архивировано 6 декабря 2019 года.
Вся высшая математика: Учебник. Т.7., 2006
В.Н.Сачков, 1982

Литература

М.Л. Краснов, А.И. Киселев, Г.И. Макаренко, Е.В. Шикин, В.И. Заляпин, А.Ю. Эвнин. Вся высшая математика: Учебник. — М.: КомКнига, 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Howie1995-1] John Mackintosh Howie Fundamentals of Semigroup Theory (англ.). — Oxford University Press, 1995. — P. 63. — ISBN 978-0-19-851194-6.

[Reis2011-2] Clive Reis. Abstract Algebra: An Introduction to Groups, Rings and Fields (англ.). — World Scientific, 2011. — P. 57. — ISBN 978-981-4335-64-5.

[CourcelleEngelfriet2012-3] Bruno Courcelle; Joost Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach (англ.). — Cambridge University Press, 2012. — P. 95. — ISBN 978-1-139-64400-6.

[_99536078ca1ddb04-4] Roberts, Tesman, 2009, с. 692.

[_edf4c1fc5c8b1d92-5] Brualdi, 2010, с. 322.

[6] Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. - СПб., БХВ-Петербург, 2004. - isbn 5-94157-546-7. - c. 529

[7] Ранговая функция, полумодулярность (неопр.). Wiki-конспекты ИТМО. Дата обращения: 6 декабря 2019. Архивировано 6 декабря 2019 года.

[Вся_высшая_математика-8] Вся высшая математика: Учебник. Т.7., 2006

[9] В.Н.Сачков, 1982