Обратным отображением 1-го порядка для вершины хiявляется множество элементов xjтаких, что существует дуга(xj, хi), принадлежащая множеству дуг графа, т. е. Г-1(хi ) = { xj : дуга (хj, хi) А }.
Обратные отображения 2-го, 3-го и т. д. n-го порядка определяются следующим образом:
Г-2(xi)= Г-(Г-1(xi)),
Г-3(xi)= Г-(Г-2(xi)),
...
Г-n(xi)= Г-(Г(n-1)(xi)).
Для графа на рис. 3.1 обратные многозначные отображения вершины х1 находятся следующим образом:
Г-1(x1)=x5,
Г-2(x1)= Г-(Г-1(x1))=Г-(x5)= x2,x4,
Г-3(x1)= Г-(Г-2(x1))=Г-(x2x4)= x1,
Г-4(x1)= Г-(Г-3(x1))=Г-(x1)= x5 и т.д.
П р и м е ч а н и я:
1. Когда отображение действует не на одну вершину, а на множество вершин Хq = { х1, х2, ..., хq }, то под Г(Хq) понимают объединение
Г(х1) Г(х2) ... Г(хq).
2. Многозначное отображение для неориентированного графа строится, если представить каждое ребро двумя противоположно направленными дугами (рис. 3.2).
Рис. 3.2. Граф: а – неориентированный; б – тождественный ему ориентированный