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