Алгоритм приведения графа к ярусно-параллельной форме.

Ярусно-параллельная форма графов

Граф, не имеющий контуров, может быть представлен в ярусно-параллельной форме. Ярусно-параллельная форма – это такой вид графа, у которого в верхний нулевой ярус помещены вершины, имеющие только исходящие дуги; в нижний ярус помещены вершины, имеющие только входящие дуги. На k-том ярусе помещены вершины, которые имеют входящие дуги из предыдущих ярусов, среди которых хотя бы одна дуга из (k-1)-того яруса.

Количество вершин в ярусе определяет ширину яруса. Наибольшая ширина яруса определяет ширину графа в ярусно-параллельной форме. Количество ярусов определяет высоту графа в ярусно-параллельной форме.

 

1. Составляется матрица смежности графа.

2. Матрица смежности просматривается в поисках нулевых столбцов. Вершины, которым соответствуют нулевые столбцы, помещаются в нулевой ярус.

3. Из матрицы смежности столбцы и строки, соответствующие вершинам нулевого яруса.

4. Повторяется п.2 данного алгоритма до тех пор, пока не будут охвачены все вершины.

5. По исходной матрице смежности восстанавливаются дуги между вершинами.

 

ПРИМЕР

Привести граф к ярусно-параллельной форме.

 

 

Рис. 3.8 Граф

 

1. Матрица смежности имеет вид:

 

 

2. В нулевой ярус помещаются вершины 3 и 8.

3. Из матрицы смежности вычеркиваются строки и столбцы, соответствующие вершинам 3 и 8:

 

 

4. В первый ярус помещаются вершины 4 и 5.

5. Из матрицы смежности вычеркиваются строки и столбцы, соответствующие вершинам 4 и 5:

 

 

6. Во второй ярус помещается вершина 1.

7. Из матрицы смежности вычеркиваются строка и столбец, соответствующие вершине 1:

 

8. В третий (последний) ярус помещаются вершины 2,6 и 7.

Таким образом, граф может быть представлен в ярусно-параллельной форме:

 

Рис. 3.9 Граф

 

Высота графа - 4 яруса; ширина -3.