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