Отображения, заданные на одном множестве

Важным частным случаем отображения является слу­чай, когда множества X и Y совпадают. При этом отобра­жение Г : ХХ будет представлять собой отображение множества X самого в себя и будет определяться парой (X, Г), где Г. Подробным изучением таких отображений за­нимается теория графов. Коснемся лишь некоторых опе­рации над подобными отображениями.

Пусть Г и - отображения множества X в X. Компо­зицией этих отображений назовем отображение Г, кото­рое в соответствии с правилом, приведенным в подразделе 1.4, опре­деляется так

(Г)х=Г(х),

В частном случае, если =Г, получаем отображения

Г²х=Г(Гх); Г³х=Г(Г²х)и т. д.

Таким образом, в общем случае для любого s2

Г^s х=Г(Г^s-1 x). (1.18)

Специальным определением введем соотношение

Г ⁰ х = х .

Это дает возможность распространить соотношение (1.18) и на отрицательные s. Действительно, согласно (1.18)

Г ⁰ х =Г (Г ^-1 x) =ГГ^-1 x =х.

Это означает, что Г^-1 x представляет собой обратное отображение. Тогда

Г^-1 x=Г^-1 (Г^-1 x)и т. д.

Пример 1.7.Пусть X — множество людей. Для каждого человека xХ обозначим через Гх множество егодетей. Тогда Г²х - множе­ство внуков х; Г³х - множество правнуков х;Г^-1х - множество ро­дителей х и т. д.

Изображая людей точками и рисуя стрелки, идущие из х в Гх, получаем родословное или генеалогическое дерево (рис. 1.4).

Пример 1.8.Рассмотрим шахматную игру. Обозначим через х не­которое положение (расположение фигур на доске), которое может создаться в процессе игры, через X множество всевозможных положений. Тогда Гх для любого хХ будет означать множество положе­ний, которые можно получить из х, делаяодин ход при соблюдении правил игры. При этом Гх =Æ, если х — матовое или патовое поло­жение; Г³х -множество положений, которые можно получить из х тремя ходами; Г^-1х -множество положений, из которых данное поло­жение может быть получено за один ход.

Рис. 1.4. Генеалогическое дерево

Для отображений, заданных на одном множестве, ча­сто используют некоторые другие названия, которые у нас встретятся в дальнейшем. Так, если элементы хХ представляют собой состоя­ния компьютерной сети, то отображение Гх будем рас­сматривать как множество состояний, в которые сеть может перейти из данного состояния. В этом случае удо­бен термин «преобразование состояния компьютерной сети». Для обозначения некоторых специальных видов отображений, заданных на одном и том же множестве, применяют также термин «отношение».