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

Матрица смежности – это квадратная матрица А = , число строк и столбцов в которой равно числу вершин графа n, а элементы определяются по правилу

а_ij =

где e_ij – ребро (дуга), соединяющее вершины i и j.

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

Два графа эквивалентны, если равны их матрицы смежности.

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

Вот пример матрицы смежности

A _{6 6} = .

Для неорграфа матрица смежности симметрична относительно главной диагонали. Для орграфа матрица смежности не симметрична.

Для мультиграфа и псевдографа:

a_ij =

m (x_i, x_j) –число ребер между вершинами х_i и х_j.

Если на вершинах графа заданы веса, то вводится дополнительный массив W длины n, в котором элемент w (i) задает значение веса вершины графа.

Если на ребрах (дугах) заданы веса, то для их задания применяется матрица смежности, но значения элементов равны весам связей.

Для мультиграфа, псевдографа с весами на ребрах и дугах используется трехмерная матрица, где третья размерность используется для записи веса ребра, дуги, петли.

Матрица инцидентности S = , имеет n строк и m столбцов, где n – число вершин в графе, m – число ребер (дуг) в графе. Элементы этой матрицы определяются по следующим правилам.

Для неорграфа

s_ij =

Вот пример матрицы инцидентности неорграфа.

S _{6 7} = .

Для орграфа учитывается ориентация:

s_ij =

Здесь каждый столбец содержит один элемент, равный +1, и один элемент, равный –1, либо константу.

Два графа эквивалентны, если равны их матрицы инцидентности.

Для псевдографа показанного на рис. 2.11, получим такую матрицу (номера строк и столбцов соответствуют индексам вершин, ребер и дуг):

S _{6 9} = .

Матрица S задает граф с точностью до изоморфизма.

основное преимущество матрицы А перед матрицей S в том, что за один шаг алгоритма можно получить ответ на вопрос: есть ли ребро из вершины х_i в х_j?

Основной недостаток матрицы А – большой объем памяти независимо от числа ребер: n ².

Если заданы веса, то используются дополнительные векторы весов вершин и ребер (дуг).

Рисунок 2.11