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

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

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

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

Обозначим как конечное непустое множество, а как  — семейство его подмножеств, то есть последовательность непустых подмножеств длины .

Трансверсалью семейства является такое подмножество , для которого существует биекция , причём для выполняется условие .

Другими словами, для элементов трансверсали существует такая нумерация, при которой для .

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. для ;
  2. ;
  3. .

Литература[править | править вики-текст]

  • М. Холл. Глава №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.