Cтраница 3
Если на каком-либо этапе поиска возникнет ситуация, предусмотренная случаем 2, то элементы вершин поискового графа исчерпывают как элементы, способные выступать в роли представителей, так и все элементы первых q множеств. Возникает ситуация, при которой q первых множеств, а также множество 5 1 образуют q - j - 1 множеств, которые содержат только q различных элементов; таким образом, в случае 2 нарушается условие теоремы Холла. [31]
Dqr не меняя представителей других г - 1 - q множеств. Действительно, сделаем представителем множества Dl элемент CQ - - - -, представителем множества D - элемент Ci-i... Это доказывает теорему Холла. [32]