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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

35
|MρP|=|M|+1. Найдем наибольшее
паросочетание в графе G = (V, E).
Отправляясь от пустого паросочетания M
0
= ι, мы будем вычислять
последовательность паросочетаний M
0
, M
1
, M
2
, … с возрастающими
кардинальными числами, пока не будет достигнуто наибольшее
паросочетание. Каждое паросочетание M
i +1
получается из предыдущего
паросочетания M
i
посредством построения увеличивающего пути P
i
. Именно,
M
i +1
= M
i
ρP
i
, i = 0, 1, 2, … . Если G – ассоциированный с разреженной
матрицей двудольный граф , то это в точности та процедура, на которой
основан алгоритм Холла. Для матрицы порядка n с числом ненулевых
элементов z этот алгоритм требует O(nz) операций .
В отличие от алгоритма Холла, алгоритм Хопкрофта – Карпа использует
только кратчайшие увеличивающие пути. Если P
i
– кратчайший
увеличивающий путь паросочетания M
i
и M
i+1
= M
i
ρP
i
, i = 0, 1, 2, … , то
имеют место следующие утверждения :
(а) |P
i+1
| ≥ |P
i
|, т.е. кратчайший увеличивающий путь для M
i+1
не может
иметь меньше ребер , чем кратчайший увеличивающий путь для M
i
.
(б) Для всех j и k таких , что | P
j
| = |P
k
|, пути P
j
и P
k
не имеют общих
вершин .
(в) Для всех j и k таких , что j < k и |P
j
| = |P
k
|, P
k
является кратчайшим
увеличивающим путем паросочетания M
j
.
(г) Если m – кардинальное число наибольшего паросочетания , то
количество различных целых чисел в последовательности |P
0
|, |P
1
|, |P
2
|, … не
может превышать 2m
1/2
+ 2.
Кроме того, если m – кардинальное число наибольшего паросочетания , а M –
произвольное паросочетание, для которого |M| < m, то справедливо и
( д) Существует увеличивающий путь длины , не превышающей 2|M|/(m -
|M|) +1.
В силу этих свойств вычисление последовательности паросочетаний
разбивается не более чем на 2 m
1/2
+ 2 фаз . Все увеличивающие пути,
разыскиваемые внутри фазы, имеют различные вершины и одинаковую
длину . Кроме того, все эти пути – кратчайшие увеличивающие для того
паросочетания , с которым начинается данная фаза. Итак , вместо того чтобы
вычислять всю последовательность паросочетаний , Хопкрофт и Карп
предлагают следующий алгоритм:
Шаг 0 (Инициализация ). Положить M ← ι.
Шаг 1 (Поиск путей ). Найти максимальное множество {P
1
, P
2
, … , P
t
}
кратчайших увеличивающих путей паросочетания M , не имеющих общих
вершин . Если таких путей нет , то остановка.
Шаг 2 (Увеличение паросочетания ). Положить M ← MρP
1
ρP
2
ρ … ρP
t
и
перейти к шагу 1.
Покажем , как использовать этот алгоритм для разреженных матриц .
Пусть A – квадратная разреженная матрица порядка n. Процедура отыскания
трансверсали состоит в следующем :
(1) Построить ассоциированный с A двудольный граф G = (V, E). Граф G
неориентированный и имеет два множества вершин R и C, по n вершин в 
                                     35
|MρP|=|M|+1. Найдем наибольшее паросочетание в графе G = (V, E).
Отправляясь от пустого паросочетания M0 = ι, мы будем вычислять
последовательность паросочетаний M0, M1, M2, … с возрастающими
кардинальными числами, пока не будет достигнуто наибольшее
паросочетание. Каждое паросочетание Mi+1 получается из предыдущего
паросочетания Mi посредством построения увеличивающего пути Pi. Именно,
Mi+1 = MiρPi, i = 0, 1, 2, … . Если G – ассоциированный с разреженной
матрицей двудольный граф, то это в точности та процедура, на которой
основан алгоритм Холла. Для матрицы порядка n с числом ненулевых
элементов z этот алгоритм требует O(nz) операций.
    В отличие от алгоритма Холла, алгоритм Хопкрофта – Карпа использует
только кратчайшие увеличивающие пути. Если Pi – кратчайший
увеличивающий путь паросочетания Mi и Mi+1 = MiρPi, i = 0, 1, 2, …, то
имеют место следующие утверждения:
    (а) |Pi+1| ≥ |Pi|, т.е. кратчайший увеличивающий путь для Mi+1 не может
иметь меньше ребер, чем кратчайший увеличивающий путь для Mi.
    (б) Для всех j и k таких, что |Pj| = |Pk|, пути Pj и Pk не имеют общих
вершин.
    (в) Для всех j и k таких, что j < k и |Pj| = |Pk|, Pk является кратчайшим
увеличивающим путем паросочетания Mj.
    (г) Если m – кардинальное число наибольшего паросочетания, то
количество различных целых чисел в последовательности |P0|, |P1|, |P2|, … не
может превышать 2m1/2 + 2.
Кроме того, если m – кардинальное число наибольшего паросочетания, а M –
произвольное паросочетание, для которого |M| < m, то справедливо и
    (д) Существует увеличивающий путь длины, не превышающей 2|M|/(m -
|M|) +1.
    В силу этих свойств вычисление последовательности паросочетаний
разбивается не более чем на 2m1/2 + 2 фаз. Все увеличивающие пути,
разыскиваемые внутри фазы, имеют различные вершины и одинаковую
длину. Кроме того, все эти пути – кратчайшие увеличивающие для того
паросочетания, с которым начинается данная фаза. Итак, вместо того чтобы
вычислять всю последовательность паросочетаний, Хопкрофт и Карп
предлагают следующий алгоритм:
    Шаг 0 (Инициализация). Положить M← ι.
    Шаг 1 (Поиск путей). Найти максимальное множество {P1, P2, …, Pt}
кратчайших увеличивающих путей паросочетания M, не имеющих общих
вершин. Если таких путей нет, то остановка.
    Шаг 2 (Увеличение паросочетания). Положить M ← MρP1ρP2ρ … ρPt и
перейти к шагу 1.
    Покажем, как использовать этот алгоритм для разреженных матриц.
Пусть A – квадратная разреженная матрица порядка n. Процедура отыскания
трансверсали состоит в следующем:
    (1) Построить ассоциированный с A двудольный граф G = (V, E). Граф G
неориентированный и имеет два множества вершин R и C, по n вершин в

Страницы