Обратное соответствие

Поскольку представляет собой множество таких вершин , для которых в графе G существует дуга (х_i, х_j), то через естественно обозначить множество вершин х_k, для которых в G существует дуга (х_k, х_i). Отношение принято называть обратным соответствием. Для графа, изображенного на рис (а), имеем

и т. д.

Для неориентированного графа для всех .

Когда отображение Г действует не на одну вершину, а на множество вершин , то под ) понимают объединение

-

т. е. является множеством таких вершин , что для каждой из них существует дуга (х_i, х_j) в G, где .

Пример.

Для графа, приведенного на рис. (а), и .

Отображение Г(Г(х_i)) записывается как Г²(х_i). Аналогично «тройное» отображение Г(Г(Г(х_i))) записывается как Г³(х_i) и т. д.

Пример.

Для графа, показанного на рис. (а), имеем:

Г²(х₁) = Г(Г(x₁)) = Г({х₂, х₅}) = {x₁, x₃, x₄}

Г³(х₁) = Г(Г²(x₁)) = Г({x₁, x₃, x₄}) = {x₁, x₂, x₅} и т. д.

Аналогично понимаются обозначения Г^-2 (x_i), Г^-3(x_i) и т. д

Дата добавления: 2015-07-07