Упорядочение вершин и дуг орграфов
Перейдём к упорядочению вершин и дуг орграфа.
Будем говорить, что вершина хi предшествует вершине хj, если существует путь из хi в хj.
В этом случае вершину хi называют предшествующей вершине хj, а хj – последующей за хi.
Рассмотрим связный граф без контуров.
Под упорядочением вершин графа будем понимать такое разбиение его вершин, на группы (ранги, слои), при котором:
1) вершины первой группы не имеют предшествующих, а вершины последней – последующих; вершины любой другой группы не имеют предшествующих в следующей группе;
2) вершины одной и той же группы не соединяются дугами.
Для графов без контуров описанное разбиение всегда возможно.
Рассмотрим матричный способ упорядочения вершин на примере графа, изображённого на рис. 7 (матрица смежности его вершин помещена в табл. 1).
Обозначим через vx1; …; vx6 векторы, являющиеся строками матрицы смежности (табл. 3).
Таблица 3
| x1 | x2 | x3 | x4 | x5 | x6 | vxi | Группа | |
| x1 x2 x3 x4 x5 x6 | vx1 vx2 vx3 vx4 vx5 vx6 | I II III II IV V | ||||||
| v1 | ||||||||
| v2 | - | |||||||
| v3 | - | - | - | |||||
| v4 | - | - | - | - | ||||
| v5 | - | - | - | - | - |
Вычислим компоненты вектора v1 = vx1 +…+ vx6 и припишем их снизу к матрице смежности.
Компоненты этого вектора представляют не что иное, как полустепени захода вершин графа (сравните с табл. 1).
В частности, полустепень захода вершины х1 оказалась равной нулю, т.е. в вершину х1 не заходит ни одна дуга.
Значит, вершина х1 не имеет предшествующих: она образует I группу.
Исключим из дальнейшего рассмотрения вершину х1 и дуги (х1; х2) и (х1; х4), исходящие из неё.
После этого вычислим компоненты вектора v2 = v1 - vx1 и запишем их во второй дополнительной строке табл.3.
Здесь появилось ещё два нуля, соответствующие вершинам х2 и х4.
Эти нули свидетельствуют о том, что в вершины х2 и х4 не заходит ни одна дуга, т.е. вершины х2 и х4 не имеют предшествующих в графе без вершины х1 и дуг (х1; х2) и (х1; х4).
Следовательно, вершины х2 и х4 образуют следующую, II, группу.
Затем находим вектор v3 = v2 – (vx2 + vx4) с одной нулевой компонентой, соответствующей вершине х3, образующей III группу.
И, наконец, определяем вектор v5 = v4 - vx5 с единственной компонентой, которая равна нулю и отвечает вершине х6, составляющей V группу.
Т. о. описанный процесс заканчивается, когда получают вектор с компонентами, равными нулю или вычеркнутыми.
В результате упорядочения вершин получаем граф (рис. 8), изоморфный данному.
Рисунок 8
При необходимости надо перенумеровать вершины, начав с вершин I группы.
Внутри группы вершины нумеруются в произвольном порядке.
Если орграф упорядочен правильно и вершины перенумерованы в натуральном порядке, то стрелки всех дуг направлены вправо, а номера начал дуг меньше номеров их концов.
На рис. 8 вершинам изоморфного графа даны новые обозначения: а1; …; а6.
Матричный способ упорядочения дуг графа опирается на понятие предшествования дуг и производится аналогично упорядочению вершин.
Вначале составляется матрица смежности дуг (табл. 2 и рис. 7).
После этого находится вектор
(табл. 4) и определяются дуги (в нашем случае u1 и u5), соответствующие нулевым компонентам этого вектора.
Таблица 4
| ul | u1 | u2 | u3 | u4 | u5 | u6 | u7 | u8 | vui | Группа |
| u1 u2 u3 u4 u5 u6 u7 u8 | vu1 vu2 vu3 vu4 vu5 vu6 vu7 vu8 | I II IV II I III II II | ||||||||
| v1 | ||||||||||
| v2 | - | - | ||||||||
| v3 | - | - | - | - | - | - | ||||
| v4 | - | - | - | - | - | - | - |
Они образуют I группу.
Затем рассматривается граф без дуг I группы и находится вектор v2 как разность вектора v1 и суммы векторов vui, соответствующих дугам I группы.
Дуги, соответствующие нулевым компонентам вектора v2, образуют II группу (в нашем примере это дуги u2, u4, u7 и u8) и т. д.
Так продолжают до тех пор, пока не приходят к вектору vk, у которого часть нулевых компонент, а остальные вычеркнуты.
В результате получают орграф с упорядоченными дугами, изоморфный данному.
При необходимости дуги изоморфного орграфа надо перенумеровать в натуральном порядке.
В рассматриваемом примере дугам изоморфного орграфа (рис. 9) даны новые обозначения t1; …; t8.
Рисунок 9
Рассмотренные вопросы находят применение в сетевом планировании и управлении большими комплексами взаимосвязанных работ.