2015-05-30
788
Для алгебраического задания графа удобно использовать матрицу смежности. Матрицей смежности графа, содержащего n вершин, называется квадратная матрица А размером (nxn), в которой элементы aij, стоящие на пересечении i-й строки и j-го столбца, численно равны количеству дуг графа, идущих из i-й вершины в j-ю. Для графа (рис. 2.2) матрица смежности имеет вид
A(1,1)={a 
}=
| J=1 | J=2 | J=3 | |
| i=1 | |||
| i=2 | |||
| i=3 |
Матрица смежности полностью определяет структуру графа. Множество столбцов, имеющих в строке xi значения aij¹0, есть множество Г(хi) с соответствующими коэффициентами (2.1), а множество строк i, имеющих в столбце xj значения aij¹0, совпадает с множеством Г-1(хj) с соответствующими коэффициентами (2.2). Согласно определению матрицы смежности неориентированным графам соответствуют симметричные матрицы смежности. Матрица смежности для многоуровневого графа строится аналогично.
В графе (рис. 2.3) каждая вершина xij имеет два индекса: i – номер уровня; j – номер вершины данного уровня.
Рис. 2.3
Матрица смежности для графа (рис. 2.3) имеет вид A(2,2)={a 
}=
| K=1 | K=1 | K=1 | K=2 | K=2 | k=2 | ||
| L=1 | L=2 | L=3 | L=1 | L=2 | L=3 | ||
| I=1 | J=1 | ||||||
| I=1 | J=2 | ||||||
| I=1 | J=3 | ||||||
| I=2 | J=1 | ||||||
| I=2 | J=2 | ||||||
| I=3 | J=3 |
,
где индексы i, j характеризуют начальную вершину xij, а индексы k,l – конечную вершину xkl.
