Русская Википедия:Трансверсаль

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

Определения

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

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

а) <math>x_i \in X_i, \forall i \in \overline{1,n}</math>.

б) <math>x_i \neq x_j, \forall i,j \in \overline{1,n} </math>

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<math> \forall A \subset \left\{ 1, 2, \ldots , m \right\} \ \ \ \rho \left( \bigcup\limits_{i\in A}{{{S}_{i}}} \right)\ge \left| A \right| </math> (1)

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

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

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

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

<math> \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 </math> и <math> \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 </math> . (2)

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

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

В силу того, что <math>X\bigcap{Y}\supset \bigcup\limits_{i\in A\bigcap{B}}{{{S}_{i}}}</math>, имеем <math> \rho \left( X\bigcap{Y} \right)\ge \left| A\bigcap{B} \right|</math>. (5)

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

Неравенство (6) противоречит неравенству (3). Утверждение доказано. <math> \vartriangle </math>

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

Следствие

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

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

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

Теорема

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

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

Пусть <math> S=(S_1, S_2, ... , S_m)</math> — семейство подмножеств некоторого множества <math>E</math>. Пусть известна матрица <math>A={{\left( {{a}_{ij}} \right)}_{n\ x\,n}}=\left\{ \begin{align}

 & 0,\ \ {{x}_{j}}\notin {{S}_{i}} \\ 
& 1,\ \ {{x}_{j}}\in {{S}_{i}} \\ 

\end{align} \right.</math>.

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

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

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

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

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

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

Обобщение

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

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

1. <math>P_i \subseteq S_i</math> для <math>i \in\{1, 2, \ldots, m\}</math>;
2. <math>|P_i| = k_i</math>;
3. <math>P_i \cap P_j = \varnothing, i \neq j</math>.

Литература

• Шаблон:Книга

• Шаблон:Книга
• Шаблон:Книга

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Cite web
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга