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

Графы можно задавать тремя способами: геометрически, аналитически и матрично.

Рис. 1.9

1. При геометрическом представлении вершины графа изображаются точками или кружочками, а связи между вершинами – линиями. Если задаётся орграф, то связи называются дугами, если неограф – рёбрами (рис. 1.9).

2. При аналитическом задании граф задаётся совокупностью множеств вершин и рёбер: G=<V, U>, гдеV={v₁, …v_N},U={u₁,…u_R} (вершины и рёбра пронумерованы).

3. При матричном способе представления граф может быть задан матрицей смежности, матрицей инцидентности или матрицей весов.

Матрица инцидентностиI(G)размерностьюNRсостоит из нулей и единиц и определяет инцидентность вершин и рёбер графа. Элементы матрицыI(G)для неографа определяются так:

При этом матрица I(G) обладает следующими свойствами:

Каждый столбец матрицы I(G) содержит только две единицы (граф без петель). Для орграфа в матрице инцидентности I(i, j)= 1 в зависимости от направления дуги: “+1” если вершина v_i является началом дуги u_j, “-1” если v_j – конец u_j.

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

Матрица смежностиS(G)имеет размерностьNNи определяет отношение между вершинами графа. Элементы матрицыSопределяются так:

Рис. 1.10 Рис. 1.11

Для неографа матрица Sявляется симметричной, для ориентированного – нет. В клетке матрицыS(i, j)ставится 1, если дуга имеет направлениеv_i v_j . В случае графа с кратными рёбрами в соответствующей клетке матрицыSуказывается кратность соответствующего ребра или его вес.

Например, для графа G₁(рис. 1.10) матрица инцидентности имеет вид:

Матрица смежности:

Список концов ребер:

Для орграфа на рис. 1.11 матрица инцидентности:

Матрица смежности:

Список концов ребер:

u1	u2	u3	u4	u5
v1	v2	v3	v1	v4
v2	v3	v1	v1	v2

В прикладных задачах, решаемых с помощью сетевых моделей, ребра графа часто имеют одну или несколько характеристик физического или экономического характера: длина, пропускная способность, стоимость и т. п. В этом случае граф определяется одной или несколькими матрицами размера NN. В общем случае они называются матрицами весов ребер, хотя могут иметь и специальные названия (например, матрица стоимостей).