Комбинаторные алгоритмы для программистов


Представления


Наиболее известный способ представления графа на бумаге состоит в геометрическом изображении точек и линий. В ЭВМ граф должен быть представлен дискретным способом, причем возможно много различных представлений. Простота использования, так же как и эффективность алгоритмов на графе, зависит от подходящего выбора представления графа. Рассмотрим различные структуры данных для представления графов.

Матрица смежностей. Одним из наиболее распространенных машинных представлений простого графа является матрица смежностей или соединений. Матрица смежностей графа

G = (V,E)
есть
\left| V \right| \times \left| V \right|
-матрица
A = [a_{ij} ]
, в которой
a_{ij} = 1
, если в
G
существует ребро, идущее из
i
-й вершины в
j
-ю, и
a_{ij} = 0
в противном случае. Орграф и его матрица смежностей представлены на рис. 12.1.

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

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

 \left[ {\begin{array}{*{20}c} 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 \end{array} } \right]

Заметим, что в матрице смежностей петля может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1, но это не принято, так как обычно удобно представлять каждый элемент матрицы одним двоичным разрядом.

Для задания матрицы смежностей требуется

\left| V \right|^2
двоичных разрядов. У неориентированного графа матрица смежностей симметрична, и для ее представления достаточно хранить только верхний треугольник. В результате экономится почти 50% памяти, но время вычислений может при этом немного увеличиться, потому что каждое обращение к
a_{ij}
должно быть заменено следующим: if
i >j
then
a_{ji}
else
a_{ij}
. В случае представления графа его матрицей смежностей для большинства алгоритмов требуется время вычисления, по крайней мере пропорциональное
\left| V \right|^2
.

Матрица весов. Граф, в котором ребру

(i,j)
сопоставлено число
w_{ij}
, называется взвешенным графом, а число
w_{ij}
называется весом ребра
(i,j)
. В сетях связи или транспортных сетях эти веса представляют некоторые физические величины, такие как стоимость, расстояние, эффективность, емкость или надежность соответствующего ребра. Простой взвешенный граф может быть представлен своей матрицей весов
W = \left[ {w_{ij} } \right]
, где
w_{ij}
есть вес ребра, соединяющего вершины
i
и
j
.


Начало  Назад  Вперед



Книжный магазин