Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм построения максимального независимого множества ⇐ ПредыдущаяСтр 2 из 2
Рассмотрим алгоритм построения максимального потока для указанной выше сети как последовательность действий непосредственно с заданной (0, 1)-матрицей, то есть не строя сеть фактически. Сначала построим какое-нибудь независимое множество элементов. Можно, например, просматривать столбцы по порядку и в каждом находить первый попавшийся единичный элемент. Найденный элемент зачисляется в независимое множество, а строка и столбец, в которых он находится, вычеркиваются из матрицы. Если в каком либо столбце нет единичных элементов, то переходим к следующему. Пусть на этом шаге построено независимое множество . (3) Если (в каждой строке выбран какой-то элемент) или (в каждом столбце выбран какой-то элемент), то, очевидно, построено максимальное независимое множество и алгоритм закончен. В противном случае начинаем процесс расстановки отметок, позволяющий либо увеличить независимое множество (3), либо убедиться, что оно максимальное. Пометим каким-то образом, например, звездочкой «пустые» строки, то есть строки, в которых нет элемента, входящих в независимое множество (3). Далее, как в общем алгоритме, выполняем циклически шаги просмотра вершин, то есть строк и столбцов. После каждого шага ряды матрицы делятся на три группы: непомеченные, помеченные и не просмотренные, помеченные и просмотренные. Ряды из последней группы в последующих шагах не участвуют. Описание шага алгоритма. Берем очередной помеченный, но не просмотренный ряд. Если этим рядом является строка с номером , то помечаем отметкой все непомеченные столбцы, имеющие 1 в данной строке. Если этим рядом является столбец с номером , то находим в независимом множестве элемент и помечаем отметкой строку . Имеется два варианта остановки описанного процесса. I. При просмотре столбца в нем оказался разрешенный элемент, не входящий в текущее независимое множество . Пусть – номер такого столбца; – отметка столбца ; – отметка строки ; (то есть ) – отметка столбца ; – отметка строки ; (то есть ) … – отметка строки ; – отметка столбца , где строка помечена звездочкой. Тогда элементы в независимом множестве можно заменить на элементы , увеличив на 1 число независимых элементов. II. Просмотрены все ряды, то есть помеченных и не просмотренных рядов больше нет. В этом случае совокупность помеченных столбцов и не помеченных строк образует покрывающее множество рядов. Число рядов равно числу элементов в независимом множестве, откуда по теореме Кёнига-Эгервари следует, что оно максимально. Пример. Определить словарный ранг матрицы .
|