Граф (от греческого gr a jw - пишу) - множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно граф обозначают как G(V, E).

Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой.

Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги - ориентированным (или орграфом).

Пара вершин может быть соединена двумя или более ребрами (или, соответственно, дугами одного направления), такие ребра (или дуги) называются кратными.

Дуга (или ребро) может начинаться и заканчиваться в одной и той же вершине, в этом случае соотв. дуга (или ребро) называется петлей.

Вершины, соединенные ребром или дугой, называются смежными.

Ребра, имеющие общую вершину, тоже называются смежными.

Ребро (или дуга) и любая из его вершин называются инцидентными.

Принято говорить, что ребро (u, v) соединяет вершины u и v, а дуга (u, v) начинается в вершине u и кончается в вершине v.

Каждый граф можно представить в евклидовом пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или дугам - в последнем случае направление обычно указывается стрелочками). - такое представление называется укладкой графа.

Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. Для 2-мерного пространства это, вообще говоря, неверно. Допускают представление в виде укладки в 2-мерном пространстве графы, называемые плоскими.

Существуют и другие способы задания графов. Пусть v1, v2, ... vn- вершины графа G(V, E), а e1, e2, ... em - его ребра (дуги).

Матрицей смежности графа G называется матрица A=||aij||, i=1,...,n; j = 1, ..., n, у которой элемент aij равен числу ребер (или дуг), соединяющих вершины vi и vj (соответственно, идущих из вершины vi в вершину vj).

Матрицей инцидентности графа G называется матрица B=||bij||, i=1, .., n; j = 1, ..., m, у которой элемент bij равен 1, если вершина vi инцидентна ребру (дуге) ej и равен 0, если не инцидентна.

Наконец, граф можно задать посредством списков. Например,

вариант 1: списком пар вершин, соединенных ребрами (или дугами);

вариант 2: списком списков для каждой вершины множества смежных с ней вершин.