Прямые отображения

Прямым отображением 1-го порядка вершины х_i является множество таких вершин графа, для которых существует дуга (х_i, x_j), т. е Г¹( х_i ) = {x_j : дуга (х_i, x_j) A} для графа G = (X, A), где X ={ х_i }, i =1, 2, ..., n – множество вершин, а A = {a_i}, i = = 1, 2, ..., m – множество дуг.

Прямое отображение 2-го порядка вершины х_i – это прямое отображение от прямого отображения 1-го порядка, т. е. Г⁺²( х_i ) = Г⁺( Г⁺¹ ( х_i ) ).

Аналогично можно записать для прямого отображения 3-го и т. д. n-го порядка.

Г⁺³(x_i)= Г⁺(Г⁺²(x_i))= Г⁺(Г⁺(Г⁺¹(x_i)))

...

Г⁺ⁿ(x_i)=Г⁺(Г^+(n-1)(x_i)).

 

Рис. 3.1. Орграф G

Прямые многозначные отображения для графа на рис. 3.1 находятся следующим образом:

Г⁺¹(x₁)=(x₂,x₃),

Г⁺²(x₁)=Г⁺(Г⁺¹(x₁))=Г⁺(x₂,x₃)=(x₃,x₅),

Г⁺³(x₁)=Г⁺(Г⁺²(x₁))=Г⁺(x₃,x₅)=(x₃,x₁) и т. д.