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

Пусть S - конечное множество из m элементов, |S| = m. P(S) - множество всех его подмножеств.

Определение.

Пусть M(S)=(S₁ ,S₂ ,...,S_n) некоторая совокупность подмножеств из P(S), необязательно различных, a = (a₁ , ..., a_n) - последовательность элементов из S, такая, что все элементы a_i , i = 1,2,...,n , различны: . Если при этом , то говорят, что элемент a_i представляет множество S_i, а вся совокупность (a₁ , ..., a_n) называется системой различных представителей (с.р.п.) для M(S). 

Заметим еще раз, что в с.р.п. если ij то a_i  a_j , если даже S_i = S_j . Если множество появляется несколько раз, то всякий раз оно должно иметь представителя, отличного от всех других.

Сразу же оказывается, что с.р.п. может существовать не для всех совокупностей множеств. Если в конечной системе множества непусты и различны, то с.р.п., очевидно, существует. Возьмем более сложный случай:

S={a, b, c, d, f}

M(S): S₁={a, b, c, d}, S₂={a, b, f}, S₃= S₄={b, f}.

В этом случае существует две с.р.п.: (c, a, b, f), (d, a, f, b). Но стоит изменить лишь одно из подмножеств, например, вместо S₂ взять S₂ = (d, f) и мы уже не сможем получить ни одной с.р.п.

Теорема 1.20. Теорема о различных представителях.

Подмножества S₁, S₂ ,..., S_n имеют с.р.п. тогда и только тогда, когда удовлетворяется следующее:

условие С. Среди элементов любого конечного числа k множеств S_i имеется по меньшей мере k различных элементов; иными словами множество состоит не менее чем из k элементов для всех k = 1, 2, ... ,n.

Замечание. Если общее число множеств конечно, а сами множества бесконечны, то теорема остается в силе, так как можно, очевидно, отбросить все элементы, кроме n, в каждом S_i , не нарушая условия С.

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

Очевидно, что условие С есть необходимое условие, потому что если различные представители существуют, то для любых k множеств представителями будут k различных элементов, содержащихся в этих множествах.

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

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

Пронумеруем множества S₁, ... , S_n и зафиксируем порядок, в котором они занумерованы. Выберем произвольный элемент a₁ из S₁ в качестве его представителя. Поочередно будем выбирать представителей других множеств: заботясь лишь о том, чтобы каждый из них был отличен от любого другого, выбранного в качестве представителя, элемента. Если этот процесс удастся довести до S_n , то мы получим с.р.п.

Мы можем, однако, достичь множества S_r , все элементы которого b₁, b₂, ... , b_t были уже использованы как представители множеств S₁ , S₂ , ... , S_r-1 . Это, однако, еще не означает, что с.р.п. не существует. Тогда построим последовательность вспомогательных множеств T₀, T₁, ... .

Зафиксируем порядок нумерации элементов множества S_r :

S_r = {b₁, b₂, ... ,b_t }{a₁, a₂, ... , a_r-1}.

Определим множество T₀ состоящим из элементов множества S_r с фиксированным выше порядком нумерации элементов:

T₀ = {b₁ ,b₂, ... , b_t}.

Будем двигаться по списку элементов множества T₀ и последовательно строить вспомогательные множества T₁, T₂, ... , до тех пор, пока не обнаружим элемент, не использованный в качестве представителя или не исчерпаем все множества. Обозначим символом S(b_i) множество, представителем которого является элемент b_i .

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

T₁ = S(b₁) \ T₀ .

Множество T₁ может быть и пустым, но если оно не пусто, то модифицируем множество T₀, припиcав к списку его элементов непосредственно за b₁ , ... , b_t элементы множества T₁, обозначенные как b_t+1 , ... , b_s :

Далее, если i - ый элемент b_i есть представитель множества S_j = S(b_i), то мы построим множество T_i , состоящее из тех элементов S_j , которые еще не использованы, и запишем эти элементы после элементов, уже использованных:

T_i = S(b_i)\ T₀ ; T₀ = T₀ * T_i .

Так мы сможем поступать до тех пор, пока либо: 1) мы достигли некоторого элемента b_i  S_j (i > t, j < r), либо : 2) последовательность T₀ исчерпывается элементами b₁, ... , b_s как представителями множеств.

Во втором случае мы должны быть убеждены, что с.р.п. не существует. В самом деле, получена некоторая последовательность элементов b₁, ... , b_v , исчерпывающая множество всех различных представителей. Эти элементы являются представителями v множеств (v < n). По построению каждый элемент этих v множеств содержится в последовательности. Но тогда эти множества (v штук), а также множество S_r образуют v + 1 множество, которые содержат только v различных элементов, таким образом мы нашли множества, нарушающие условие C.

Если же имеет место случай 1), мы на некотором этапе находим элемент b_i = b_i1 (i₁ > t), который входит во множество S_j1 , представителем которого является выбранный ранее другой элемент b_i2 , причем i₂ < i₁ . Если i₂ > t, то значит b_i2  S_j2 , а представителем множества S_j2 является b_i3  S_j3 (i₃ < i₂) и так далее. Таким образом, возникает последовательность , индексы которой убывают , причем в этой последовательности каждый ее член входит во множество, представителем которого является следующий член. Но теперь мы можем заменить представителей: возьмем в качестве представителя - в качестве представителя - для . Элемент в результате такой замены освобождается для выбора в качестве представителя . Итак , мы, действуя тем же путем, найдем представителя S_r+1 и так далее. Наши построения закончатся либо выбором системы различных представителей, либо мы обнаружим систему множеств, для которой нарушается условие С. 

1.21. Пример.

Пусть имеется следующая система множеств:

S₁ = {1, 2}; S₂ ={2, 3}; S₃ = {3, 4}; S₄ ={5, 2}; S₅ ={4, 6}; S₆ = {1, 5}.

Будем обозначать выбор элемента b в качестве представителя множества S записью b = P(S).

Последовательно выберем следующих представителей множеств:

1 = P(S₁); 2 = P(S₂); 3 = P(S₃); 5 = P(S₄); 4 = P(S₅).

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

Строим последовательность множеств T₀ , T₁ , ... :

T₀ = {1, 5}

T₁ = S(1)\T₀ = {2} T₀ = {1, 5, 2}

T₂ = S(5)\T₀ = 

T₃ = S(2)\T₀ = {3} T₀ = {1, 5, 2, 3}

T₄ = S(3)\T₀ = {4} T₀ = {1, 5, 2, 3, 4}

T₅ = S(4)\T₀ = {6} T₀ = {1, 5, 2, 3, 4, 6}

Таким образом передвигаясь по элементам множества

мы, наконец, достигаем элемента 6, который не является представителем никакого множества. Мы нашли последовательность элементов 1, 5, 2, 3, 4, 6, такую что:

элемент 6S₅, а P(S₅)=4;

элемент 4 вошел в последовательность как элемент множества S₃, 4S₃ , а P(S₃)= 3;

элемент 3 вошел в последовательность как элемент множества S₂, 3S₂ , а P(S₂)= 2;

элемент 2 вошел в последовательность как элемент множества S₁, 2S₁ , а P(S₁)= 1.

Теперь мы можем заменить представителей, положив

6 = P(S₅); 4 = P(S₃); 3 = P(S₂); 2 = P(S₁);

освободившийся элемент 1 может быть использован в качестве представителя множества S₆. 