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

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

Граф, не имеющий контуров, может быть представлен в ярусно-параллельной форме. Ярусно-параллельная форма – это такой вид графа, у которого в верхний нулевой ярус помещены вершины, имеющие только исходящие дуги; в нижний ярус помещены вершины, имеющие только входящие дуги. На 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.