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

115 j Теорема 4.6. Пусть семейство множеств Sj, S „, удовлетворяет ( леобходимым условиям существования системы различных представителей и пусть каждое < т) состоит не менее чем из t элементов. Тогда: 1) если t < т, то имеется не менее чем t! систем различных представителей; 2) если t > т, то имеется не менее чем t! /(t~m)! систем различных Представителей. Алгоршпм выбора системы различных представителей (с.р.п.). условия теоремы Холла практически очень сложно проверить. Более того теорема дает условия существования решения, но не указывает правила лахождения с.р.п. Поэтому приведём алгоритм построения с.р.п., который одновременно будет проверять существование с.р.п. Пусть задано п множеств Si, Ss,..., S, „ п>1. Требуется найти для них с-р-п. или показать, что этой системы не существует. Пронумеруем множества Si, S2,...,S „ и зафиксируем порядок, в котором они занумерованы. Произвольным образом выберем элемент первого множества a j е S/ в качестве его представителя. Поочередно будем выбирать представителей д р у г и х множеств: й2 S S2, Qj £ S 3 з а б о т я с ь о том, чтобы каждый из них б ы л отличен от любого ранее выбранного. Если такие операции окажутся доведенными до а„ е S „ включительно, то получим искомую с.р.п. Может случиться, что в ходе постепенного подбора дойдем до некоторого множества S, (t < п ), все элементы которого bi, й?,..., Ьщ уже б ы л и выбраны представителями других множеств. Это еще не означает, что с.р.п. не существует. Закрепим порядок нумерации элементов S,. Будем брать поочередно все те множества Sj,j < t, представителями которых являются Ь], (элементы из S,). В каждом Sj будем удалять все элементы, которые у ж е являются представителями множеств до тех пор, пока либо ]) встретится элемент Ьц е Sj, который не является ещё представителем, либо 2) не существует элемент, который не является представителем. Во случае 2) с.р.п. не существует. Если же имеет случай 1), т.е. на некотором этапе найдётся й,/ е Sj, не являющийся до сих пор представителем. Положим, что представителем для 5, является новый элемент Ьц. Далее начинаем назначать представителей для и так далее. В результате либо имеется возможность дойти до S „ и получить с.р.п., либо встретить случай 2) и установить, что с.рл. не существует.