WikiSort.ru - Не сортированное

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

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

Определение

Обозначим как ${\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}$  — множество, то все его элементы различны, отсюда и название «система различных представителей».

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

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

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

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

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

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

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

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

Пусть ${\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)}$ ^[1].

Обобщение

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

Пусть имеется последовательность целых положительных чисел ${\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}$ .

Примечания

Литература

• М. Холл. Глава №5 «Системы различных представителей» // Комбинаторика = Combinatorial Theory / пер. с англ. С. А. Широковой; под ред. А. О. Гельфонда и В. Е. Тараканова. — М.: Мир, 1970. — С. 65—78. — 424 с.
• М. Свами, К. Тхуласираман. Глава №8.6 «Паросочетания в двудольных графах» // Графы, сети и алгоритмы = Graphs, Networks, and Algorithms / пер. с англ. М. В. Горбатовой, В. Л. Торхова, С. А. Фролова, В. Н. Четверикова; под ред. В. А. Горбатова. — М.: Мир, 1984. — С. 165—166. — 455 с. — 11 000 экз.
• В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. — М.: Наука, 1990. — С. 87—92. — 384 с. — ISBN 5-02-013992-0.
• Н. И. Костюкова. Графы и их применение (неопр.). — Лекция №16: Теория трансверсалей. Проверено 29 июля 2009. Архивировано 4 апреля 2012 года.
• Alexander Schrijver. Chapter 22 «Transversals», chapter 23 «Common transversals» // Combinatorial optimization. — Springer, 2003. — P. 378—409. — 1800 p. — ISBN 978-3540443896.

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.