Матричное представление графа

Для алгебраического задания графа удобно использовать матрицу смежности. Матрицей смежности графа, содержащего n вершин, называется квадратная матрица, А размером (nxn), в которой элементы a_ij, стоящие на пересечении i-й строки и j-го столбца, численно равны количеству дуг графа, идущих из i-й вершины в j-ю. Для графа (рис. 2.2) матрица смежности имеет вид.

A (1,1)={a}=.

Матрица смежности полностью определяет структуру графа. Множество столбцов, имеющих в строке x_i значения a_ij0, есть множество Г (х_i) с соответствующими коэффициентами (2.1), а множество строк i, имеющих в столбце x_j значения a_ij0, совпадает с множеством Г^-1(х_j) с соответствующими коэффициентами (2.2). Согласно определению матрицы смежности неориентированным графам соответствуют симметричные матрицы смежности. Матрица смежности для многоуровневого графа строится аналогично.

В графе (рис. 2.3) каждая вершина x_ij имеет два индекса: i — номер уровня; j — номер вершины данного уровня.

Рис. 2.3.

Матрица смежности для графа (рис. 2.3) имеет вид A (2,2)={a}=.

где индексы i, j характеризуют начальную вершину x_ij, а индексы k, l — конечную вершину x_kl.