![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
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.
Дата публикования: 2014-11-03; Прочитано: 478 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!