Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины.
Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).
Отображением вершины хi — Г(хi) является множество вершин, в которые существуют дуги из вершины хi, т. е. Г(хi) = { хj: ∃ дуга (хi, хj) ∈ A}.
Так для орграфа на рис.2 описание заданием множества вершин и соответствия выглядит следующим образом:
G4=(X, Г)),
где X = {хi}, I = 1, 2,..., 4 – множество вершин, Г(х1) = { х2 }, Г(х2) = { х3, х4 }, Г(х3) = {х3}, Г(х4) = { х1, х2 } – отображения.
Для неориентированного или смешанного графов предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого ориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Например, для графа на рис.1,б Г(х2) = { х1, х3, х5 }, Г(х4) ={ х3, х5} и т. д.
Алгоритмы на графах