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

                                   32
    (3а) Если такое ребро нашлось и ω ≠ t, положить Vv ← Vv ″ {ω},
Ee←Ee″(v→ω), опустить ω в стек и перейти к шагу 2 для продолжения
поиска.
    (3б) Если такое ребро нашлось и ω = t, положить Ee ← Ee ″ (v → ω),
опустить ω в стек и перейти к шагу 5 для сборки пути.
    (3в) Если v не имеет неисследованных выходов, ведущих к
непосещавшимся вершинам, перейти к шагу 4 для возвращения.
   Шаг 4 (Возвращение). Поднять стек на одну позицию. Если стек пуст, то
остановка. В противном случае перейти к шагу 2.
   Шаг 5 (Формирование пути). Поднять все содержимое стека, напечатать
путь, а затем перейти к шагу 1, чтобы начать новый путь.
   Алгоритм требует памяти и времени O(|V|, |E|).

       3.2.4 Алгоритм Холла
      Если у заданной n × n матрицы A все диагональные элементы не равны
нулю, то ей можно сопоставить орграф. Однако если на главной диагонали
имеются нули, то вначале переставляются строки и столбы с тем, чтобы
получить ненулевую диагональ. Найденная этим путем последовательность
ненулевых элементов называется трансверсалью. У невырожденной
матрицы A полная трансверсаль всегда существует. Однако, полную
трансверсаль может иметь и вырожденная матрица. Назовем структурно
вырожденной матрицу порядка n, которую нельзя переупорядочить так,
чтобы получилась полная трансверсаль. Если максимальная возможная
трансверсаль имеет длину k < n, то k – это структурный ранг, а n – k —
структурный дефект матрицы.
   Максимальную трансверсаль матрицы A можно найти посредством
алгоритма Холла. Опишем вариант с перестановками строк, который удобен
для разреженных матриц, хранимых в строчном формате. Алгоритм состоит
из n шагов. Цель k-го шага – поместить ненулевой элемент в k-ю позицию
диагонали. По завершении k шагов в первых k позициях главной диагонали
стоят ненулевые элементы. Теперь на шаге k + 1 имеются следующие
возможности:
 (а) Элемент ak+1, k+1 ≠ 0, в этом случае шаг k + 1 закончен.
 (б) Существует ненулевой элемент, строчный и столбцовый индексы
которого находятся в пределах от k + 1 до n. В таком случае перестановкой
строк и/или столбцов этот элемент можно перевести в (k + 1)-ю
диагональную позицию. Квадратная подматрица, расположенная на
пересечении строк и столбцов с номерами 1, …, k, не меняется при этих
перестановках, и ненулевые элементы в первых k позициях диагонали
останутся на своих местах.
 (в) Квадратная подматрица, стоящая на пересечении строк и столбцов с
номерами k + 1, …, n, – нулевая. Мы можем все же надеяться отыскать
комбинацию строчных перестановок, помещающую ненулевой элемент в (k +
1)-ю диагональную позицию. Чтобы найти требуемые перестановки,
проследим в матрице увеличивающий путь. Он начинается с позиции (k + 1, k