Порядковая функция на графе

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

Алгоритм упорядочения вершин сводится к следующему.

1. В подмножество нулевого уровня Щ включаются все вершины v_f, у которых С?^-1 (V/) = Ш, что означает, что из этого множества вершин дуги только выходят, а символ (?' означает обратное отображение.

При этом производится последовательная нумерация вершин / = 1, 2, …" /.

2. В множество первого уровня N включаются все вершины v" у которых (v,)c N₀, за исключением Afo:

Последовательная нумерация вершин продолжается с дальнейшим присвоением меток i=l + 1, / + 2, I + р.

3. В подмножество второго уровня N2 включаются все вершины V/, у которых G'¹ (у,) с (N₀, за исключением N₀ u N_t:

Реализуется дальнейшая нумерация / = / + р + 1, / + р + 2, …" I + р+ I

4. В подмножество третьего уровня Щ включаются все вершины v" у которых (?^_| (v,) с (N₀ kj N_x kj П₂), за исключением и /V, и N₂:

после чего процесс нумерации вершин продолжается.

5. Данный процесс ведется до тех пор, пока не будут пронумерованы все вершины графа. Множество вершин последнего уровня определится как.

где г — наименьшее целое число, такое, что (7(,/У,.) = 0, т. е. нет больше вершин, в которые бы отображалось N_r.

Пример (7). На рис. 5.21 показаны неупорядоченный и упорядоченный по уровням графы.

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

Пример. Исходный граф изображен на рис. 5.22.

Рис. 5.21. Порядковая функция на графе: а ~ неупорядоченный граф; б — уровни упорядоченного графа

Рис. 5.22. Исходный граф

Матрица смежности вершин этого графа с опущенными для простоты нулями, имеет вид:

Составляем строку До, в которой подсчитываем суммы элементов в соответствующих столбцах этой матрицы:

Нули в строке Aq дают вершины, которым не предшествует ни одна другая вершина. Таким образом, вершины Е и Н составляют уровень No;

Исключив из сумм строки До значения, записанные в строках Е и Н, получим строку Aj, в которой нули из До заменены знаком «+*.

Появившиеся в строке Д| нули дают вершины, которым не предшествует ни одна другая вершина, кроме ранее удаленных? и Я. Это вершины В_у /, У, которые образуют множество уровня N.

Далее из Aj вычтем суммы строк В, /, У, заменив все ранее появившиеся нули знаками «+», и получим строку Л2:

Новые нули, появившиеся в Aj, дают вершины, для которых не существует других предшествующих вершин, кроме удаленных Е, Я, В, /, У.

Вершины А, <7, N составляют уровень Этот процесс продолжается до тех пор, пока нс будет закончен перебор всех вершин исходного графа (матрицы):

После этого строится граф (рис. 5.23), с четко определенной порядковой функцией, когда вершины находятся на соответствующих им уровнях.

Рис. 5.23. Уровни упорядоченного графа.

Когда граф содержит по крайней мере один контур, найдется строка Д" в которой невозможно добиться появления нового нуля. Этот факт дает автоматическое средство для выявления контуров в графе.