Алгоритм построения максимального независимого множества

Рассмотрим алгоритм построения максимального потока для указанной выше сети как последовательность действий непосредственно с заданной (0, 1)-матрицей, то есть не строя сеть фактически.

Сначала построим какое-нибудь независимое множество элементов. Можно, например, просматривать столбцы по порядку и в каждом находить первый попавшийся единичный элемент. Найденный элемент зачисляется в независимое множество, а строка и столбец, в которых он находится, вычеркиваются из матрицы. Если в каком либо столбце нет единичных элементов, то переходим к следующему.

Пусть на этом шаге построено независимое множество

. (3)

Если (в каждой строке выбран какой-то элемент) или (в каждом столбце выбран какой-то элемент), то, очевидно, построено максимальное независимое множество и алгоритм закончен.

В противном случае начинаем процесс расстановки отметок, позволяющий либо увеличить независимое множество (3), либо убедиться, что оно максимальное.

Пометим каким-то образом, например, звездочкой «пустые» строки, то есть строки, в которых нет элемента, входящих в независимое множество (3). Далее, как в общем алгоритме, выполняем циклически шаги просмотра вершин, то есть строк и столбцов. После каждого шага ряды матрицы делятся на три группы: непомеченные, помеченные и не просмотренные, помеченные и просмотренные. Ряды из последней группы в последующих шагах не участвуют.

Описание шага алгоритма. Берем очередной помеченный, но не просмотренный ряд. Если этим рядом является строка с номером , то помечаем отметкой все непомеченные столбцы, имеющие 1 в данной строке. Если этим рядом является столбец с номером , то находим в независимом множестве элемент и помечаем отметкой строку .

Имеется два варианта остановки описанного процесса.

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

– номер такого столбца;

– отметка столбца ;

– отметка строки ; (то есть )

– отметка столбца ;

– отметка строки ; (то есть )

…

– отметка строки ;

– отметка столбца ,

где строка помечена звездочкой. Тогда элементы

в независимом множестве можно заменить на элементы

,

увеличив на 1 число независимых элементов.

II. Просмотрены все ряды, то есть помеченных и не просмотренных рядов больше нет. В этом случае совокупность помеченных столбцов и не помеченных строк образует покрывающее множество рядов. Число рядов равно числу элементов в независимом множестве, откуда по теореме Кёнига-Эгервари следует, что оно максимально.

Пример. Определить словарный ранг матрицы

.