§ 8. Системы различных представителей
Пусть даны пять множеств
- $S_1={1,2,3}$
- $S_2={1,2,4}$
- $S_3={1,2,5}$
- $S_4={3,4,5,6}$
- $S_5={3,4,5,6}$
Требуется выбрать пять различных элементов x1, x2,...,x5 таких, что $х_i∈S_i,$т.е. требуется выбрать представителей заданных множеств, причём выбранные представители должны быть разными элементами. Например, для приведённого примера в качестве представителей можно выбрать следующие элементы: 1, 2, 5, 3, 4. Но если взять множества
- $T_1 = \{1,2\}$
- $T_2 = \{1,2\}$
- $T_3 = \{1,2\}$
- $T_4 = \{3,4,5,6\}$
- $T_5 = \{3,4,5,6\}$
то такой выбор оказывается невозможным, а так как нельзя выбрать три различных элемента из множеств T1, T2, T3. Возникает вопрос: при каких условиях подмножества Si множества S обладают различными представителями $x_i$, т.е.$x_i ∈ S_i$ и $x_i ≠ x_j$, если $i ≠ j$. Заметим, что не требуется, чтобы множества $S_i и S_j$ были различными при $i ≠ j$.
Как легко убедиться, необходимое условие для существования различных представителей состоит в том, чтобы в совокупности всех элементов произвольных k множеств Si содержалось не менее k различных элементов. Оказывается, это условие является и достаточным.
Теорема 4.5. (теорема Холла). Подмножества $S_1, S_2,..., S_m$. конечного множества S имеют систему различных представителей тогда и только тогда, когда для каждого $k, 1≤ k≤ m,$. объединение любой k - выборки из этих множеств содержит не менее k элементов. Иными словами, система различных представителей для $S_1, S_2,..., S_m$. существует тогда и только тогда, когда $S{i1} ∪ S{i2} ∪ . . .∪ S{ik}$. состоит не менее чем из k элементов при k = 1,2,...,m, а $i_1, i_2,..., i_k$. –любая k-выборка из - 1, 2, ..., m.
Необходимость условий теоремы уже доказана.
Необходимость условий теоремы уже доказана. Заметим, что если каждое Si содержит единственный элемент xi, то доказательство достаточности очевидно и причем выбор системы различных представителей единственен. Для случая, когда Si содержит более одного элемента, достаточность условий примем без доказательства. Можно доказать более общую теорему.
Теорема 4.6. Пусть семейство множеств $S_1, S_2,..., S_m$. удовлетворяет необходимым условиям существования системы различных представителей и пусть каждое Si(1≤ i ≤ m) состоит не менее чем из t элементов. Тогда:
1) если t ≤ m, то имеется не менее чем t! систем различных представителей; 2) если $t > m$., то имеется не менее чем t! /(t–m)! систем различных представителей.
Алгоритм выбора системы различных представителей (с.р.п.).Условия теоремы Холла практически очень сложно проверить. Более того теорема дает условия существования решения, но не указывает правила нахождения с.р.п. Поэтому приведём алгоритм построения с.р.п., который одновременно будет проверять существование с.р.п.
Пусть задано n множеств $S_1, S_2,..., S_n, n≥1$.. Требуется найти для них с.р.п. или показать, что этой системы не существует. Пронумеруем множества $S_1, S_2,...,S_n$. и зафиксируем порядок, в котором они занумерованы. Произвольным образом выберем элемент первого множества а1 ∈ S1 в качестве его представителя. Поочередно будем выбирать представителей других множеств: а2 ∈ S2, а3 ∈ S3 ,..., заботясь о том, чтобы каждый из них был отличен от любого ранее выбранного. Если такие операции окажутся доведенными до аn ∈ Sn включительно, то получим искомую с.р.п.
Может случиться, что в ходе постепенного подбора дойдем до некоторого множества $S_t (t < n)$. , все элементы которого $b_1, b_2,..., b_{k(t)}$. уже были выбраны представителями других множеств. Это еще не означает, что с.р.п. не существует. Закрепим порядок нумерации элементов St. Будем брать поочередно все те множества $S_j, j < t$., представителями которых являются$b1, b2,..., bk(t)$. (элементы из St). В каждом Sj будем удалять все элементы, которые уже являются представителями множеств до тех пор, пока либо
1) встретится элемент bi1 ∈ Sj, который не является ещё представителем, либо
2) не существует элемент, который не является представителем.
2) не существует элемент, который не является представителем. Во случае 2) с.р.п. не существует.
Если же имеет случай 1), т.е. на некотором этапе найдётся $b{i1} ∈ S_j$., не являющийся до сих пор представителем. Положим, что представителем для Sj является новый элемент bi1. Далее начинаем назначать представителей для$S{j+1}$. и так далее. В результате либо имеется возможность дойти до Sn и получить с.р.п., либо встретить случай 2) и установить, что с.р.п. не существует.