Задание графа с помощью отображения

Иногда бывает удобно дать графу другое определение. Можно считать, что множество направленных дуг А, соединяющих элементы множества Х, отображает это множество само в себя. Граф G можно считать заданным, если даны множество его вершин Х и способ отображения Г множества Х в Х, т.е. G=(X,Г).

Для графа (рис. 2.1) отображение Г определяется следующим образом:

Г(х₁) = {x₂}; Г(х₂) = {x₃}; Г(х₃) = {x₁}.

В случае неориентированного графа или смешанного графа, содержащего и дуги, и неориентированные ребра (например, граф, изображенный на рис. 2.2), предполагается, что отображение задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой неориентированного ребра двумя противоположно направленными дугами, содержащими те же самые вершины. Так, например, для графа (рис. 2.2) имеем

Г(х₁) = {2x₂,x₃}; Г(х₂) = {x₃}; Г(х₃) = {x₁,x₂}. (2.1)

Задание графа с помощью обратного отображения

Поскольку Г(х_i) представляет собой множество таких вершин x_jÎ X, для которых в графе G существует дуга (x_i,x_j), то через Г^-1(x_i) естественно обозначить обратное отображение, т.е. множество вершин x_k, для которых в G существует дуга (x_к,x_i). Граф можно задавать с помощью обратного отображения вершин. Тогда, например, для графа (рис. 2.2) можно записать