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

                                     34
   Относительно      эффективности этого алгоритма заметим, что на
каждом шаге каждая строка просматривается самое большое дважды: первый
раз при поиске ненулевого элемента, стоящего правее позиции k, второй раз
при необходимости найти ненулевой элемент в непосещавшемся столбце с
номером от 1 до k. Поэтому если в матрице z ненулевых элементов, то на
шаге k выполняется O(z) операций, а в алгоритме в целом O(nz) операций.
Эта оценка достигается на специально сконструированных примерах, но на
практике число операций обычно является малым кратным z.

      3.2.5 Алгоритм Хопкрофта – Карпа
      Алгоритм Хопкрофта – Карпа находит максимальную трансверсаль
разреженной матрицы. Основная идея та же, что и в алгоритме Холла:
прослеживаются увеличивающие пути, и от шага к шагу улучшаются
назначения. Однако проводится тщательный анализ увеличивающих путей, и
их свойства используются, чтобы разбить последовательность назначений на
малое число фаз. Внутри каждой фазы одновременно находят много
коротких увеличивающих путей, все они имеют одинаковую, причем
минимальную длину, и с их помощью улучшается текущее назначение. Этим
способом повышается эффективность алгоритма.
   Рассмотрим неориентированный граф G = (V, E) и подмножества M φ E
его ребер. Подмножество M называется паросочетанием или назначением,
если никакая вершина G не инцидентна более чем одному ребру из M.
Паросочетание с наибольшим кардинальным числом m=|M| называется
наибольшим паросочетанием. Вершина, не инцидентная никакому ребру из
M, называется свободной. Путь в графе G, не имеющий повторяющихся
вершин, называется увеличивающим путем паросочетания M, если оба его
конца – свободные вершины, а ребра попеременно принадлежат E – M и M.
Увеличивающие пути служат для повышения кардинального числа
паросочетания. Если известен увеличивающий путь паросочетания M, то
можно получить новое паросочетание M' с числом ребер, на единицу
большим, чем у M (т.е. |M'| = |M| + 1). Для этого нужно взять все ребра пути,
не принадлежащие исходному паросочетанию M, и добавить все ребра M, не
вошедшие в увеличивающий путь. Это свойство имеет место для любого
увеличивающего пути, какова бы ни была его длина. В особенности нас
будут интересовать кратчайшие увеличивающие пути, т.е. пути, имеющие
наименьшее кардинальное число среди всех увеличивающих путей
паросочетания M. Чтобы более точно сформулировать сказанное, напомним
сперва некоторые обозначения, используемые в теории множеств.
Рассмотрим два множества: S и T. Запись S – T обозначает множество
элементов S, не принадлежащих T. Таким образом, S – T = =S–(S 1 T). Запись
SρT обозначает симметричную разность множеств S и T. Элемент
принадлежит SρT, если он находится либо в S, либо в T, но не в S 1 T.
Следовательно, SρT = S ″ T – S 1 T.
   Пусть теперь P обозначает множество ребер увеличивающего пути
паросочетания M в графе G. Тогда MρP также паросочетание, причем