Способы задания графов

Граф можно задать аналитически как совокупность множества вершин V и множества ребер U: G=<V,U>, где V={V1,V2,…,V_N}, U={U1, U2, …, U_R}. Однако более наглядными являются графические способы задания графов.

Матрица инцидентности – это прямоугольная матрица I размерностью N x R, имеющая N строк и R столбцов, и определяющая инцидентность вершин и ребер графа:

Элементы матрицы I определяются так:

1, если вершина Vi инцидентна ребру Uj,

I(i,j) =

0, в противном случае.

В каждом столбце матрицы инцидентности ровно две единицы. У ориентированного графа I(i,j)=±1, в зависимости от направления дуги. Для записи информации об инцидентности вершин и ребер графа используется также список концов ребер, т.е. для каждого ребра задается пара его конечных вершин. Для орграфа первой указывается вершина, из которой выходит дуга.

Матрица смежности – это квадратная матрица размерностью N x N, элементы которой определяются так:

1, если Vi и Vj смежны,

S(i,j) =

0, в противном случае.

Для неориентированного графа матрица смежности S симметрична, для орграфа S(i,j)=1, если есть дуга от Vi к Vj. В случае мультиграфа в качестве S(i,j) задается кратность соответствующего ребра или его вес.

Ели число ребер в графе мало, матрица смежности содержит много нулей, и более удобным является задание списка смежных вершин.

На рис.1 приведены примеры задания орграфа.