3. Алгоритмы на графах

   1. Графы. Представления графов. Связность и расстояние

Конечный граф G = (V, E) состоит из конечного множества вершин V = {V₁, V₂ … V_m} и конечного множества ребер E = {e₁, e₂ … e_n}. Каждому ребру соответствует пара вершин. Если ребро определяется e = (v, w), то говорят, что оно инцидентно вершинам v и w. Графы бывают ориентированными, если ребра — дуги и не ориентированными в противном случае [4].

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

Граф называется простым, если он не имеет ни петель, ни параллельных ребер.

Представление графа матрицей смежности

Рис. 3.1. Ориентированный граф и его матрица смежности

У неориентированного графа матрица смежности симметричная, и для ее представления достаточно хранить только верхний треугольник, что экономит память.

Матрица весов

Граф, в котором ребру (i, j) сопоставлено число w_ij, называется взвешенным графом, а число w_ij называется весом ребра (i, j). В сетях связи или транспортных сетях эти веса представляют некоторые физические величины, такие как стоимость, расстояние, эффективность, емкость, надежность и т.д. Простой взвешенный граф может быть представлен своей матрицей весов W = [w_ij], где w_ij есть все ребра, соединяющие вершины i и j. Веса несуществующих ребер обычно полагают равными  или 0 в зависимости от приложений.

Список ребер

Иногда более эффективно представлять ребра графа парами вершин. Это представление можно реализовать двумя массивами g = (g₁, g₂, …, g_m) и h = (h₁, h₂, …, h_m).

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

g = (1, 2, 2, 2, 2, 3, 3, 4, 5, 5, 5, 7, 7)

h = (6, 1, 3, 4, 6, 4, 5, 5, 3, 6, 7, 1, 6)

При этом легко представимы петли и параллельные ребра.

Структуры смежности

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

Структура ориентированного графа (рис. 3.1) такова:

1: 6

2: 1, 3, 4, 6

3: 4, 5

4: 5

5: 3, 6, 7

6:

7: 1, 6

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

Хранение списков в виде структуры смежности желательно для алгоритмов, в которых в графе добавляются или удаляются вершины.

Связность и расстояние

Говорят, что вершины x и y в графе смежны, если существует ребро, соединяющее их. Говорят, что два ребра смежны, если они имеют общую вершину. Путь — это последовательность смежных ребер (v₁, v₂), (v₂, v₃) …, в которой все вершины v_1,v₂, …, v_k — различны, исключая возможно, случай v₁ = v_k. Записывается путь из v₁ в v_k как (v₁, v₂, v₃, …, v_k). Число ребер в пути называется длиной пути. Расстояние от вершины a до вершины b определяется как длина кратчайшего пути (т.е. пути наименьшей длины) из a в b.

Цикл — это путь, в котором первая и последняя вершины совпадают.

Подграф графа G = (V, E) есть граф, вершины и ребра которого принадлежат G.

Неориентированный граф G связан, если существует хотя бы один путь в G между каждой парой вершин v_i и v_j. Ориентированный граф G связан, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным.

Сильно связан тот ориентированный граф, если для каждой пары вершин v_i и v_j существует по крайней мере один ориентированный путь из v_i в v_j и по крайней мере один из v_j в v_i.