5.3

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

[8/63%]
Показать
LaTeX
Задача 5.3.1
?
(1)

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

(2)

Теорема Холла. Пусть S1,…,SmS_{1}, \ldots , S_{m} — конечные множества. В каждом из них можно выбрать по элементу xi∈Six_{i} \in S_{i} так, чтобы все xix_{i} были различны, тогда и только тогда, когда для каждого k∈{1,…,m}k \in \left\{ 1,\ldots ,m\right\} объединение любых kk из этих множеств имеет не менее kk элементов.

Задача 5.3.2

Какое минимальное количество рёбер можно удалить из графа Kn,nK_{n,n}, чтобы не осталось совершенных паросочетаний (т.е. подграфов из nn непересекающихся отрезков)?

?
Задача 5.3.3

Пусть для системы mm-элементных множеств каждый элемент, входящий хотя бы в одно из них, входит ровно в ll из них. Тогда при m⩾lm \geqslant l у этой системы множеств есть с.р.п.

?
Примечание.
?

Пусть дан набор M\mathscr {M} множеств. В каждом из множеств выбрали по элементу. Если все элементы различны, то такой набор назовем системой различных представителей (сокращенно с.р.п.). Или, формально, системой различных представителей для набора M\mathscr {M} множеств называется упорядоченный набор различных элементов x(S)∈Sx(S) \in S, S∈MS \in \mathscr {M}, т.е. такое инъективное отображение x:M→⋃S∈MSx : \mathscr {M} \to \bigcup_{S \in \mathscr {M}} S, что x(S)∈Sx(S) \in S для любого S∈MS \in \mathscr {M}.

(Упорядоченность набора важна для подсчёта количества с.р.п. в задаче 5.3.5, а не для выяснения существования с.р.п.)

Например, теорема Холла утверждает, что у системы S1,…,SmS_{1}, \ldots , S_{m} конечных множеств есть система различных представителей тогда и только тогда, когда ∣⋃i∈ISi∣⩾∣I∣\left|\bigcup_{i \in I} S_{i}\right| \geqslant \left|I\right| для любого I⊂{1,…,m}I \subset \left\{ 1,\ldots ,m\right\}.

Задача 5.3.4

С.р.п. поднабора можно дополнить до с.р.п. всего набора. Вот более подробная формулировка. Из набора M\mathscr {M} множеств выбрано несколько подмножеств S1,…,SkS_{1}, \ldots , S_{k}. Допустим, что элементы x1,…,xkx_{1}, \ldots , x_{k} — это с.р.п. набора множеств S1,…,Sk∈MS_{1}, \ldots , S_{k} \in \mathscr {M}. Если у всего набора M\mathscr {M} есть с.р.п., то существует его с.р.п., содержащая элементы x1,…,xkx_{1}, \ldots , x_{k}.

?
Задача 5.3.5

Обозначим через F(S1,…,Sm)F(S_{1}, \ldots , S_{m}) количество с.р.п. у системы {S1,…,Sm}\left\{ S_{1}, \ldots , S_{m}\right\}.

?
(1)

Для любого ли kk существует система S1,…,SmS_{1}, \ldots , S_{m} такая, что F(S1,…,Sm)=kF(S_{1}, \ldots , S_{m}) = k?

(2)

Найдите все возможные значения F(S1,S2)F(S_{1}, S_{2}) при условии ∣S1∣=∣S2∣=5\left|S_{1}\right| = \left|S_{2}\right| = 5.

(3)

Найдите все возможные значения F(S1,S2,S3)F(S_{1}, S_{2}, S_{3}) при условии ∣S1∣=∣S2∣=∣S3∣=5\left|S_{1}\right| = \left|S_{2}\right| = \left|S_{3}\right| = 5.

Задача 5.3.6

Пусть даны два разбиения множества SS на mm подмножеств: S=⨆i=1mAi=⨆i=1mBiS = \bigsqcup_{i=1}^{m} A_{i} = \bigsqcup_{i=1}^{m} B_{i}, m⩽∣S∣m \leqslant \left|S\right|. Пусть выполнено одно из следующих условий.

?
(1)

Для любого подмножества {i1,…,ik}⊂{1,…,m}\left\{ i_{1},\ldots ,i_{k}\right\} \subset \left\{ 1,\ldots ,m\right\} множество Ai1∪…∪AikA_{i_{1}} \cup \ldots \cup A_{i_{k}} содержит не более kk из множеств B1,…,BmB_{1}, \ldots , B_{m}.

(2)

∣A1∣=…=∣Am∣=∣B1∣=…=∣Bm∣\left|A_{1}\right| = \ldots = \left|A_{m}\right| = \left|B_{1}\right| = \ldots = \left|B_{m}\right|.

Тогда можно перенумеровать множества A1,…,AmA_{1}, \ldots , A_{m} так, чтобы в новой нумерации Ai∩Bi≠∅A_{i} \cap B_{i} \neq \emptyset для любого i=1,…,mi = 1, \ldots , m.

Задача 5.3.7

Пусть даны два разбиения множества SS на mm подмножеств: S=⨆i=1mAi=⨆i=1mBiS = \bigsqcup_{i=1}^{m} A_{i} = \bigsqcup_{i=1}^{m} B_{i}, m⩽∣S∣m \leqslant \left|S\right|. Пусть для любых подмножеств I,J⊂{1,…,m}I, J \subset \left\{ 1,\ldots ,m\right\} выполнено неравенство

∣(⨆i∈IAi)∩(⨆j∈JBj)∣⩾∣I∣+∣J∣−m. \left|\left(\bigsqcup _{i \in I} A_{i}\right) \cap \left(\bigsqcup _{j \in J} B_{j}\right)\right| \geqslant \left|I\right| + \left|J\right| - m.

Тогда можно перенумеровать множества A1,…,AmA_{1}, \ldots , A_{m} так, чтобы после нумерации нашлись попарно различные элементы xi∈Ai∩Bix_{i} \in A_{i} \cap B_{i}, i=1,…,mi = 1, \ldots , m.

?
Примечание.
?

Такой набор x1,…,xmx_{1}, \ldots , x_{m} называются общей системой различных представителей наборов множеств A1,…,AmA_{1}, \ldots , A_{m} и B1,…,BmB_{1}, \ldots , B_{m}.

Задача 5.3.8
?
(1)

Найдите необходимое и достаточное условие на двудольный граф, при котором вершины можно занумеровать A1,…,AnA_{1}, \ldots , A_{n} (в первой доле) и B1,C1,…,Bn,CnB_{1}, C_{1}, \ldots , B_{n}, C_{n} (во второй доле) так, что есть рёбра A1B1,A1C1,…,AnBn,AnCnA_{1}B_{1}, A_{1}C_{1}, \ldots , A_{n}B_{n}, A_{n}C_{n}.

(2)

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

{t!,t⩽m,t!/(t−m)!,t>m, \begin{cases} t!, & t \leqslant m, \\ t!/(t-m)!, & t > m, \end{cases}

способов переженить юношей на любимых ими девушках.