Упорядочение вершин и дуг орграфов

Перейдём к упорядочению вершин и дуг орграфа.

Будем говорить, что вершина х_i предшествует вершине х_j, если существует путь из х_i в х_j.

В этом случае вершину х_i называют предшествующей вершине х_j, а х_j – последующей за х_i.

 

Рассмотрим связный граф без контуров.

Под упорядочением вершин графа будем понимать такое разбиение его вершин, на группы (ранги, слои), при котором:

1) вершины первой группы не имеют предшествующих, а вершины последней – последующих; вершины любой другой группы не имеют предшествующих в следующей группе;

2) вершины одной и той же группы не соединяются дугами.

Для графов без контуров описанное разбиение всегда возможно.

 

Рассмотрим матричный способ упорядочения вершин на примере графа, изображённого на рис. 7 (матрица смежности его вершин помещена в табл. 1).

Обозначим через v _{x 1}; …; v _{x 6} векторы, являющиеся строками матрицы смежности (табл. 3).

 

Таблица 3

	x 1	x 2	x 3	x 4	x 5	x 6	v xi	Группа
x 1 x 2 x 3 x 4 x 5 x 6							v x 1 v x 2 v x 3 v x 4 v x 5 v x 6	I II III II IV V
v1
v2	-
v3	-	-		-
v4	-	-	-	-
v5	-	-	-	-	-

 

Вычислим компоненты вектора v ₁ = v _{x 1} +…+ v _{x 6} и припишем их снизу к матрице смежности.

Компоненты этого вектора представляют не что иное, как полустепени захода вершин графа (сравните с табл. 1).

В частности, полустепень захода вершины х ₁ оказалась равной нулю, т.е. в вершину х ₁ не заходит ни одна дуга.

Значит, вершина х ₁ не имеет предшествующих: она образует I группу.

Исключим из дальнейшего рассмотрения вершину х ₁ и дуги (х ₁; х ₂) и (х ₁; х ₄), исходящие из неё.

После этого вычислим компоненты вектора v ₂ = v ₁ - v _{x 1} и запишем их во второй дополнительной строке табл.3.

Здесь появилось ещё два нуля, соответствующие вершинам х ₂ и х ₄.

Эти нули свидетельствуют о том, что в вершины х ₂ и х ₄ не заходит ни одна дуга, т.е. вершины х ₂ и х ₄ не имеют предшествующих в графе без вершины х ₁ и дуг (х ₁; х ₂) и (х ₁; х ₄).

Следовательно, вершины х ₂ и х ₄ образуют следующую, II, группу.

Затем находим вектор v ₃ = v ₂ – (v _{x 2} + v _{x 4}) с одной нулевой компонентой, соответствующей вершине х ₃, образующей III группу.

И, наконец, определяем вектор v ₅ = v ₄ - v _{x 5} с единственной компонентой, которая равна нулю и отвечает вершине х ₆, составляющей V группу.

 

Т. о. описанный процесс заканчивается, когда получают вектор с компонентами, равными нулю или вычеркнутыми.

 

В результате упорядочения вершин получаем граф (рис. 8), изоморфный данному.

Рисунок 8

 

При необходимости надо перенумеровать вершины, начав с вершин I группы.

Внутри группы вершины нумеруются в произвольном порядке.

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

На рис. 8 вершинам изоморфного графа даны новые обозначения: а ₁; …; а ₆.

Матричный способ упорядочения дуг графа опирается на понятие предшествования дуг и производится аналогично упорядочению вершин.

Вначале составляется матрица смежности дуг (табл. 2 и рис. 7).

После этого находится вектор

(табл. 4) и определяются дуги (в нашем случае u ₁ и u ₅), соответствующие нулевым компонентам этого вектора.

 

Таблица 4

ul	u 1	u 2	u 3	u 4	u 5	u 6	u7	u 8	v ui	Группа
u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8									v u 1 v u 2 v u 3 v u 4 v u 5 v u 6 v u 7 v u 8	I II IV II I III II II
v1
v2	-				-
v3	-	-		-	-		-	-
v4	-	-		-	-	-	-	-

 

Они образуют I группу.

Затем рассматривается граф без дуг I группы и находится вектор v ₂ как разность вектора v ₁ и суммы векторов v _ui, соответствующих дугам I группы.

Дуги, соответствующие нулевым компонентам вектора v ₂, образуют II группу (в нашем примере это дуги u ₂, u ₄, u ₇ и u ₈) и т. д.

Так продолжают до тех пор, пока не приходят к вектору v _k, у которого часть нулевых компонент, а остальные вычеркнуты.

В результате получают орграф с упорядоченными дугами, изоморфный данному.

При необходимости дуги изоморфного орграфа надо перенумеровать в натуральном порядке.

В рассматриваемом примере дугам изоморфного орграфа (рис. 9) даны новые обозначения t ₁; …; t ₈.

Рисунок 9

 

Рассмотренные вопросы находят применение в сетевом планировании и управлении большими комплексами взаимосвязанных работ.