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

 

Конечный граф 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.

 

Остовные деревья

 

Связанный неориентированный ациклический граф называется деревом. В связанном неориентированном графе G существует по крайней мере один путь между каждой парой вершин. Поэтому, если G — дерево, то между каждой парой вершин существует в точности один путь.

Таким образом, дерево с n вершинами содержит в точности n -1 ребер и значит деревья есть минимально связанные графы. Удаление из дерева любого ребра превращает его в несвязанный граф, разрушая единственный путь между по крайней мере одной парой вершин.

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

Во взвешенном графе часто бывает нужно определить остовное дерево (лес) с минимальным общим весом ребер, т.е. дерево (лес), у которого сумма весов всех его ребер минимальна. Такое дерево называется минимумом остовных деревьев. Процедура при этом такова. На каждом шаге выбирается новое ребро с наименьшим весом (наименьшее ребро), не образующее циклов с уже выбранными ребрами; этот процесс продолжается до тех пор, пока не будет выбрано | v |–1 ребер, образующих остовное дерево Т, где v — число узлов дерева. Этот процесс известен как жадный алгоритм.

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

Прохождение графа начинается с некоторой произвольной вершины а в заданном графе. Пусть (a, b) — ребро с наименьшим весом, инцидентное a; ребро (a, b) включается в дерево. Затем среди всех ребер, инцидентных либо а, либо b, выбирается ребро с наименьшим весом, и оно включается в частично построенное дерево. В результате в дерево добавляется новая вершина, например c. Повторяя процесс, ищем наименьшее ребро, соединяющее a, b или c с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из G не будут включены в дерево, т.е. пока дерево не станет остовным.

 

 

Примеры. В основе — граф рис. 3.1.

1. Жадный алгоритм

6 — начало:

å = 1,7

Алгоритм ближайшего соседа

å = 1,7

                                          Рис. 3.2. Алгоритмы на графах

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