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

                                    40
    Шаг      0       (Инициализация). Положить Ee ← ι, Vv ← ι, i ← 0.
    Шаг 1 (Выбор начальной вершины). Выбрать произвольную вершину v ⌠
Vv. Если такой нет, то – остановка.
    Шаг 2 (Посещение вершины). Опустить v в стек и маршрут. Положить
Vv←Vv″{v}, i ← i +1, Номер(v) ← i, Связка(v) ← i.
    Шаг 3 (Исследование ребра). Найти в списке смежности вершины v ребро
(v→ω)⌠ Ee. Возможны следующие случаи:
    (3а) Найдено ребро (v → ω), причем ω ⌠ Vv, т.е. (v → ω) – древесное
ребро. Положить Ee ← Ee ″ (v → ω), v ← ω и перейти к шагу 2.
    (3б) Найдено ребро (v → ω), причем ω 0 Vv. Положить Ee ← Ee ″ (v → ω) и
перейти к шагу 4 для пересчета признака Связка(v).
    (3в) Вершина v не имеет неисследованных выходов и Связка(v) <
Номер(v). Перейти к шагу 5 для возвращения.
    (3г) Вершина v не имеет неисследованных выходов и Связка(v) =
Номер(v). Перейти к шагу 6 для сборки сильной компоненты.
    Шаг 4 (Пересчет признака Связка). Если Номер(ω) < Номер(v) и ω
находится в стеке, то положить Связка(v) ← min [Связка(v), Связка(ω)] и
перейти к шагу 3. В противном случае, сразу перейти к шагу 3.
    Шаг 5 (Возвращение). Поднять v из маршрута. Положить: u ← вершина
на верхе маршрута, Связка(u) ← min [Связка(u), Связка(v)], v ← u. Перейти к
шагу 3.
    Шаг 6 (Формирование сильной компоненты). Поднять v и все вершины
над v из стека и поместить их в текущую сильную компоненту. Поднять v из
маршрута. Если маршрут пустой, перейти к шагу 1. В противном случае
положить v←вершина на верхе маршрута и перейти к шагу 3.
    Этот алгоритм требует памяти и времени O (|V|, |E|).

      3.2.8 Стратегия Марковица
     Стратегия Марковица заключается в том, чтобы на каждом шаге брать
в качестве главного ненулевой элемент, для которого минимально
произведение числа остальных ненулевых элементов той же строки и числа
остальных ненулевых элементов того же столбца активной подматрицы.
   Нижеизложенные стратегии применимы к любой матрице A, но если A
большая и известно, что она разложима, то почти наверное имеет смысл
вначале привести ее к блочной нижней треугольной форме, а уже затем
использовать эти методы для каждого блока по отдельности.
   Алгоритм Марковица локален в том смысле, что минимизирует на
каждом шаге заполнение и число операций, не считаясь с возможностью, что
другая последовательность предыдущих главных элементов могла бы
породить еще меньшее общее заполнение и потребовать меньшего общего
числа операций.
   Рассмотрим следующую картину гауссова исключения. В начале k-го
шага мы принимаем за главный элемент a kk(k ) и нормируем строку k активной
подматрицы делением всех ее элементов на a kk(k ) . Векторы r и c имеют