# из элементов, которые

из элементов, которые необходимо разбить на n классов Ki по принадлежности к строке результирующей таблицы. Эти множества удовлетворяют теореме Холла, то есть любые q множеств содержат элементы не менее чем q классов. S1 6 15 10 8 S2 5 13 1 11 S3 2 9 12 14 S4 7 3 16 4 6 8 8 10 15 10 1 11 11 5 5 13 9 2 14 2 12 2 16 - 3 - 4 7 Начинаем работу. Первая итерация (первый столбец правой таблицы). Из S1 выбираем 6?K2, из S2 - 1?K1, из S3 - 9?K3, так как 2 выбрать нельзя, класс K1 занят, из S4 - 16, так как 3, 4 и 7 выбирать не имеем права по той же причине. Вторая итерация. По этой же логике из S1 - 8, S2 - 11, S3 - 2. Выбрать из S4 нечего - все классы заняты. Строим чередующуюся цепочку (глава 3, построение паросочетания в двудольном графе), она начинается в S4 и состоит из ребер (S4,3), (3,S3), (S3,14). Эти ребра на рисунке, приведенном ниже, помечены одинарными стрелками. Меняем представителя у S3 на 14 из K4, и для S4 появляется представитель - 3 из K1 (третий столбец правой таблицы).

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа