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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Не путать с трансверсалью треугольника.

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

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

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

Пример[править | править вики-текст]

Пусть заданы множество 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.

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

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

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

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

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

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

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

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

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

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

  1. P_i \subseteq S_i для i \in\{1, 2, \ldots, m\};
  2. |P_i| = k_i;
  3. 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.