Обратные отображения

Обратным отображением 1-го порядка для вершины х_iявляется множество элементов x_jтаких, что существует дуга(x_j, х_i), принадлежащая множеству дуг графа, т. е. Г^-1(х_i) = { x_j: дуга (х_j, х_i) А }.

Обратные отображения 2-го, 3-го и т. д. n-го порядка определяются следующим образом:

Г^-2(x_i)= Г^-(Г^-1(x_i)),

Г^-3(x_i)= Г^-(Г^-2(x_i)),

...

Г^-n(x_i)= Г^-(Г^(n-1)(x_i)).

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

Г^-1(x₁)=x₅,

Г^-2(x₁)= Г^-(Г^-1(x₁))=Г^-(x₅)= x₂,x₄,

Г^-3(x₁)= Г^-(Г^-2(x₁))=Г^-(x₂x₄)= x₁,

Г^-4(x₁)= Г^-(Г^-3(x₁))=Г^-(x₁)= x₅ и т.д.

П р и м е ч а н и я:

1. Когда отображение действует не на одну вершину, а на множество вершин Х_q = { х₁, х₂,..., х_q }, то под Г(Х_q) понимают объединение

Г(х₁) Г(х₂) ... Г(х_q).

2. Многозначное отображение для неориентированного графа строится, если представить каждое ребро двумя противоположно направленными дугами (рис. 3.2).

Рис. 3.2. Граф: а – неориентированный; б – тождественный ему ориентированный