Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 36 стр.

                                    36
каждом. Вершины R называются юношами и соответствуют строкам A.
Вершины C называются девушками и соответствуют столбцам A. В G
имеется ребро (ri, cj), если aij ≠ 0.
    (2) Пусть M – паросочетание в G. Вначале M = ι, но в ходе работы
алгоритма M становится непустым. Теперь при фиксированном G и текущем
M мы приписываем ориентацию ребрам G: каждое ребро из M направлено от
юноши к девушке, а каждое из оставшихся ребер G – от девушки к юноше.
Пусть G =(V , E ) – полученный этим способом ориентированный граф.
Именно такой способ построения G мотивируется следующим его
свойством: ребра любого ориентированного пути в G попеременно
принадлежат E – M и M. Поэтому если в G найден путь, связывающий
свободную девушку со свободным юношей (имеется в виду свобода по
отношению к M), то этот путь необходимо увеличивающий.
    (3) Пусть L0 – множество свободных девушек. Тогда нужно построить
подструктуру уровней ориентированной смежности с корнем в L0, пользуясь
поиском в ширину. Нет необходимости строить всю подструктуру.
Достаточно сохранять ребра, идущие от каждого уровня Li к уровню Li+1. При
этом нужны только уровни L0, L1, …, Lp, где p = min{i | Li 1 {свободные
юноши}≠ ι}.
    Построенная подструктура представляет собой ациклический орграф с
девушками в четных уровнях и юношами – в нечетных. Каждый путь от
свободной девушки к свободному юноше – это кратчайший увеличивающий
путь для M, причем его длина равна p. Чтобы найти максимальное множество
путей с различными вершинами, обращается ориентация каждого ребра, и на
подструктуре, отправляясь от свободных юношей уровня Lp, выполняется
поиск в глубину. Заметим, что если бы ориентация ребер не обращалась, а
поиск начинался от свободных девушек уровня L0, то пришлось бы
исследовать много ребер, ведущих к несвободным юношам уровня Lp, что
потребовало бы значительно большей вычислительной работы. Наконец,
если {P1, P2, …, Pt} – найденное множество путей, то можно увеличить
текущее паросочетание M и новое паросочетание имеет кардинальное число
|M| + t.
    Если разреженная матрица порядка n имеет z ненулевых элементов, то
алгоритм, строящий внутри фазы максимальное множество путей, требует
памяти и времени O(n, z). Поскольку кардинальное число наибольшего
паросочетания не превышает n, то фаз будет не больше чем 2n1/2 + 2.
Следовательно, весь алгоритм вычисления наибольшего паросочетания
требует времени не более O(n3/2, zn1/2) и памяти не более O(n, z). Если z =
O(n), что часто выполняется для разреженных матриц, то эти оценки
превращаются в O(n3/2) для времени и O(n) для памяти.

       3.2.6 Алгоритм Сарджента – Уэстерберга
      Несимметричная разреженная матрица, имеющая полную трансверсаль
(т.е. диагональ без нулей) может быть симметрично переупорядочена к
блочной нижней треугольной форме, если известны сильные компоненты