Задание графов соответствием

Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины.

Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).

Отображением вершины х_i — Г(х_i) является множество вершин, в которые существуют дуги из вершины х_i, т. е. Г(х_i) = { х_j: дуга (х_i, х_j) A}.

Так для орграфа на рис. 1.3 описание заданием множества вершин и соответствия выглядит следующим образом: G₄=(X, Г),

где X = {х_i}, I = 1, 2,..., 4 – множество вершин, Г(х₁) = { х₂ }, Г(х₂) = { х₃, х₄ }, Г(х₃) = { х₃ }, Г(х₄) = { х₁, х₂ } – отображения.

Для неориентированного или смешанного графов предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Например, для графа на рис. 1.2,б Г(х₂) = { х₁, х₃, х₅ }, Г(х₄) ={ х₃, х₅} и т. д.