1) Граф можно задать списком вершин и ребер.
2) Можно задать и геометрически, нарисовав его на плоскости или любой другой поверхности и отождествив его вершины с точками на плоскости, а ребра с отрезками, соединяющими смежные (соседние) вершины.
3) Матрица смежности (соседства) вершин (p,q) – графа G=(V,E) с p вершинами есть квадратная симметричная матрица [p x p].
где aij:
- 1, если вершины Vi,Vj – соседние
- 0, в противном случае
Замечание: Всякому графу соответствует его бинарная симметричная матрица смежности. Всякая бинарная симметричная квадратная матрица с нулевой диагональю соответствует некоторому графу.
4) Матрица инциденций (соответствий) (p,q) – графа с p вершинами и q ребрами есть [p x q] матрица
где Bij:
1, если вершина Vi∈ ребру ej
0, в противном случае
Замечание: для всякого графа можно построить соответствующую ему бинарную матрицу инциденций.