Эти рассуждения имеют смысл для ориентированных графов без контуров.
Граф находится в ярусно-параллельной форме (ЯПФ),
если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в 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
Ширина яруса определяется числом вершин в ярусе.
Ширина графа в ЯПФ определяется шириной самого большого яруса.
e h
g f
c
b