Приобрести книгу легче всего в издательстве. Схема проезда
Программы из книги.
Разберем на примере алгоритм решения задачи о паросочетаниях в двудольном графе.
Найдем наибольшее паросочетание в графе (рис. 5.4).
 Матрица смежности графа имеет вид  Выделим отдельные шаги алгоритма. 1. Составим таблицу с размерами матрицы смежности. Пометим недопустимые для паросочетания элементы, проставив какой-либо символ, например звездочку, в тех местах, где стоят нули матрицы. Получим  2. Двигаясь по матрице B в каком-либо порядке, например слева направо, сверху вниз, проставим на допустимые поля единицы, не допуская более одной единицы в строке и столбце. Так мы получим первый вариант паросочетания. Это будет максимальное (но не обязательно наибольшее) паросочетание:  3. Если во всех строках появились единицы, то задача решена, найдено наибольшее паросочетание. В нашем примере в пятой строке нет единицы. Пометим такие строки в специальном столбце, например справа от матрицы:  4. В помеченной строке (или строках) найдем незапрещенные места в непомеченных столбцах. В специальной строке (ниже матрицы) поместим в этих столбцах номера помеченной строки. Здесь это 5-я строка, а незапрещенное место находится в первом столбце. Поэтому ставим номер 5 в первый столбец в специальную строку. Первый столбец считается помеченным. Получаем  5. Ищем единицы в помеченных столбцах. Помечаем (справа) строки, в которых найдены единицы:  Первая строка оказалась помеченной. Далее возвращаемся к шагу 4. 4ў. В первой (помеченной) строке есть пять незапрещенных (без звездочки) мест в непомеченных столбцах. Проставляем ее номер (т.е. 1) в специальной строке:  Далее надо перейти к шагу 5 и искать единицы в помеченных столбцах, помечать строки, в которых найдены единицы, переходить к шагу 4 и т.д. Здесь мы приходим к ситуации, когда в пятом помеченном столбце нет единиц. Это сигнал к следующему этапу решения задачи. 6. Проставляем единицу в найденный столбец в первую строку. При этом обнаруживаем, что в этой строке уже есть единица - в первом столбце. Ее надо куда-то переставить. Указателем для перестановки служит специальная строка внизу. Она дает адрес: 5-я строка этого же столбца. Получаем  Если эта строка тоже занята, то единицу, которая стояла в строке раньше (в другом столбце), двигаем по ее столбцу туда, куда указывает номер в специальной строке внизу. Однако в нашем случае этого нет. Более того, убеждаемся, что мы нашли решение - совершенное (покрывающее все вершины) покрытие. Строим граф, являющийся ответом на поставленную задачу (рис. 5.5).   Сначала передвигаем единицу из четвертого столбца туда, куда указывает специальная строка (здесь она не изображена), т.е. в первую строку. Единицу, стоявшую в первой строке и первом столбце, двигаем опять вниз, на пятую строку. Вновь получаем совершенное паросочетание графа. Граф может и не иметь совершенного паросочетания. Поэтому в программе предусмотрен выход по условию, когда логическая переменная Usl станет ложной, а это произойдет, когда специальный столбец перестанет меняться. |
Программа для Maple