Отношения строгого порядка следования вершин в ориентированном связном графе без циклов

 

Для удобства работы с графами, в том числе для выполнения на них различных расчетов, вершины графа должны быть упорядочены и перенумерованы. Упорядочению подлежат только ориентированные связные графы без циклов.

Для упорядочения вершин используется метод разбиения множества N на слои. Каждый слой - это подмножество множества N, отвечающее следующему условию: все вершины данного слоя имеют предков только в предыдущих слоях, или, что то же самое,- все вершины данного слоя имеют потомков только в последующих слоях. Как следствие, отметим, что вершины внутри одного слоя не связаны между собой дугами.

Разбиение на слои выполняется двумя способами:

- исключением предков,

- исключением потомков.

Рассмотрим второй способ.

1. Выделим вершины, не имеющие потомков. Очевидно, что это завершающие вершины графа и их следует отнести к последнему слою.

2. Исключим из рассмотрения (на рисунке – вычеркнем) найденные вершины и все дуги, ведущие к ним. В результате такого усечения получим подграф, т. е. частичный граф по отношению к исходному. В нем снова выделим вершины, не имеющие потомков, и отнесем их уже к предпоследнему слою.

3. Продолжим эту процедуру до тех пор, пока не просмотрим все вершины исходного графа.

Заметим, что приведенный алгоритм формирует слои, начиная с последнего. Алгоритм исключения предков аналогичен, но формирует слои, начиная с первого.

Рассмотренный алгоритм может быть реализован не только на рисунке, задающем граф, но и с помощью его матрицы репрезентативности, что для больших графов значительно удобнее, а также позволяет использовать для упорядочения ЭВМ.

Чтобы определить на первом шаге, какие вершины не имеют потомков, нужно просто сложить единицы по строкам матрицы. Суммы покажут, сколько потомков есть у каждой вершины, и там, где суммы равны нулю, – потомков нет.

Чтобы на втором шаге исключить из рассмотрения найденные вершины соответствующие строки вычеркиваются. Чтобы исключить ведущие в них дуги из матрицы вычеркиваются столбцы с номерами этих вершин. В усеченной матрице, соответствующей усеченному графу, снова выполняется суммирование по строкам и по новым нулевым суммам отыскиваются вершины предпоследнего слоя. Так продолжается до окончания рассмотрения всех вершин.

Алгоритм исключения предков аналогичен, но суммирование для определения числа предков производится по столбцам матрицы. Заметим, что два этих подхода могут дать неодинаковые результаты разбиения множества вершин на слои. Приведенный выше матричный алгоритм упорядочения вершин графа носит имя Де-Мукрона.

После упорядочения вершин производится их перенумерация. Вершины графа обозначаются, как правило, числами натурального ряда, причем от слоя к слою нумерация монотонно возрастает, а внутри слоя она безразлична.

 

Пример.

Пусть задан граф (рис. 3.4) размерностью n = 10, k = 18. Требуется упорядочить его вершины методом Де-Мукрона и перенумеровать их.

Составим матрицу смежности вершин графа размерностью 10´10 и дополним ее нужным количеством столбцов, содержащих суммы для реализации метода исключения потомков, и строк - для метода исключения предков (табл.3.2).

                                 А

                                                                 Г

         Б                 

                                                                               Е

   В                               Д

 

                                                   З

           Ж                                                       И

 

                                                           К

 

Рис. 3.4. Исходный граф для упорядочения вершин

 

Изобразим упорядоченный граф с учетом того, что формирование слоев методом исключения потомков идет от конца к началу, а затем произведем перенумерацию его вершин. Результат представлен на рис. 3.5. Упорядочение методом исключения предков дало другой результат, представленный на рис. 3.6.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: