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

Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.

Матрица смежности – это квадратная матрица размерностью n x n, (где n – число вершин графа), однозначно представляющая его структуру.

A = {a_ij}, i, j = 1, 2,..., n, а каждый элемент матрицы определяется следующим образом:

a_ij = 1, если ∃ дуга (х_i, х_j),

a_ij = 0, если нет дуги (х_i, х_j).

Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n – количество вершин графа, а m – количество дуг графа. Обозначается матрица инциденций B = = {b_ij}, i = 1, 2,..., n, j = 1, 2,..., m.

Каждый элемент матрицы определяется следующим образом:

b_ij = 1, если х_i является начальной вершиной дуги a_j,

b_ij = –1, если х_i является конечной вершиной дуги a_j,

b_ij = 0, если х_i не является концевой вершиной дуги a_j или если a_j является петлей.

Рис.2. Орграф и его матричное представление: а – орграф; б – матрица смежности; в – матрица инциденций

На рис.2, а,б приведен граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов i-ой строки матрицы дает полустепень исхода вершины х_i, а сумма элементов i-го столбца дает полустепень захода вершины х_i. По матрице смежности можно найти прямые и обратные отображения. Рассмотрим i-ю строку матрицы. Если элемент a_ij=1, то элемент графа х_j входит в отображение Г(х_i). Например, в 2-й строке матрицы А (рис.2,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х₂) = { х₂, х₅}.

Для графа на рис.2,а матрица инциденций приведена на рис.4,в. Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент равный 1 и один – равный – 1, либо все элементы столбца равны 0.

Для неориентированного графа, матрица инциденций определяется так же, за исключением того, что все элементы, равные –1, заменяются на 1.