Дискретная математика

И4 § 8. Системы различных представителей Пусть даны пять множеств S!={1, 2, 3}, S2={1, 2. 4h Si4l 2, 5}, S4^{3, 4, 5, 6}, Ss43, 4, 5, 6}. Требуется выбрать пять различньк элементов Х;, Х2,-м таких, что XieSi, т.е. требуется выбрать представителей заданных множеств, причём выбранные представители должны быть разными элементами. Например, дня приведённого примера в качестве представителей можно выбрать следующие элементы: 1, 2, 5, 3, 4. Но если взять множества Т,={1, 2}. Т2Ч1 2}, ТН1. 2}, Т4={3. 4. 5. 6}, Ts=={3, 4, 5, 6}, то такой выбор оказывается невозможным, а так как нельзя выбрать три различных элемента из множеств Г/, Т2, Т3. Возникает вопрос: при каких условиях подмножества S, множества 5' обладают различными представителями Xi, т.е. х,- е Si и Xi ^Xj, если i Заметим, что не требуется, чтобы множества 5", и Sj были различными при Как легко убедиться, необходимое условие для существования различных представителей состоит в том, чтобы в совокупности всех элементов произвольных к множеств 5,- содержалось не менее к различных элементов. Оказывается, это условие является и достаточным. Теорема 4.5. (теорема Холла). Подмножества Si, Sz,-, S „, конечного множества 5 имеют систему различных представителей тогда и только тогда, когда для каждого к, 1< к< т, объединение любой к - выборки из этих множеств содержит не менее к элементов. Иными словами, система различных представителей для Si, S2,..., существует тогда и только тогда, когда Sii uSi2и . . . uSik состоит не менее чем из к элементов при к = а i], 12,..., -любая ^-выборка из 1,2,..., т. Необходимость условий теоремы уже доказана. Заметгол, что если каждое Si содержит единственный элемент х,-, то доказательство достаточности очевидно и причем выбор системы различных представителей единственен. Для случая, когда Si содержит более одного элемента, достаточность условий примем без доказательства. Можно доказать более общую теорему.