-
Приведение графа к ярусно-параллельной форме. Пример.
Эти рассуждения имеют смысл для ориентированных графов без контуров.
Граф находится в ярусно-параллельной форме (ЯПФ), если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в i-том ярусе - вершины, в которые заходят дуги только из предыдущих ярусов, причем хотя бы одна дуга из (i - 1)-го яруса.
Пусть дан произвольный граф без циклов.
a
h
b
g
c
f
d
e
|
|
a |
b |
c |
d |
e |
f |
g |
h |
|
a |
|
|
1 |
|
|
|
|
|
|
b |
|
|
|
|
|
|
|
|
|
c |
|
1 |
|
|
|
|
|
|
|
d |
|
|
|
|
1 |
|
|
1 |
|
e |
1 |
|
|
|
|
|
1 |
|
|
f |
|
|
1 |
|
|
|
|
|
|
g |
|
1 |
1 |
|
|
|
|
|
|
h |
1 |
|
|
|
|
1 |
|
|
Алгоритм приведения к ЯПФ:
0. Строим матрицу смежности графа.
1. Матрица смежности графа просматривается, и в очередной ярус выбираются вершины с нулевой полустепенью захода, соответствующие нулевым столбцам.
2. Строки, соответствующие выбранным на предыдущем шаге вершинам, обнуляются.
3. Осуществляется возврат к шагу 1, до полного исчерпания матрицы.
4. Прорисовываются дуги.
В результате, вышеприведенный граф примет вид:
d
e
h
g
f
a
c
b
Ширина яруса определяется числом вершин в ярусе.
Ширина графа в ЯПФ определяется шириной самого большого яруса.