2.1.5. Матричный способ задания графов

Определения

Матрица инциденций

Простому графу G можно сопоста­вить матрицу инциденций [B]: прямоугольную матрицу размерности mxn, строки которой соответствуют вершинам, а столбцы - рёбрам графа.

Элемент матрицы инцидентности в i-ой строке и j-ом столбце равен числу раз инцидентности i-ой вершины и j-ого ребра.

Для простого графа матрица инциденций имеет вид:

Строки матрицы инциденций [B] называютвекторами инциденций графаG.

Свойства матрицы инциденций:

1. Количество единиц в строке равно степени deg (V_i);

2. Количество единиц в столбце графа равно 2

Матрица смежности

Матрица смежности вершин графа(или простоматрица смежности) [A] – квадратная матрицаn×n, строки и столбцы которой соответствуют вершинам графа.

Элемент матрицы смежностидляi-ой строки иj-го столба равен числу ребер междуi-ой иj-ой вершинами.

Элементы матрицы [A] простого графа равны:

[A] =

Свойства матрицы смежности:

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

2. Для простого графа главная диагональ - нулевая.

Справедливо следующее ут­верждение:Любой симметричной матрице с элементами множества {0,1} можно поставить в соответствие граф.

Матрица Лапласа (Кирхгоффа)

Матрицей Лапласа графа G является квадратная матрица [L] порядка [n n], где n – число вершин.

Элементы матрицы [L] равны:

Матрица Лапласа [L] и матрица смежности [A] графаGсвязаны между собой:

[L] = [D] - [A],

где [D] – диагональная матрица, элементыd_iiкоторой равны степеням вершинV_i.

Пример

Рис.2.1.8. Матрица Лапласа графаG

2.1.6. Битовые цепочки, таблицы инциденций

и метод координатного хранения

Определение

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

Достаточно представления только половины матрицы, т.к. вторая половина матрицы симметрична первой.

Хранение графа в памяти компьютера потребует ещё меньше места, если для графового числа использовать методы сжатия.

Определения

Строка таблицы инцидентностисодержит вершинуV_icперечислением всех инцидентных ей вершин графа.

Данная форма записи графа особенно удобна для разреженных графов (т.е. графов с большим числом вершин и всего несколькими рёбрами).

Определения

Для разреженных матриц смежности (т.е. матриц с преобладающим числом нулей) с числом единиц NNZиспользуетсяметод координатного хранения(X-Y) матрицы в виде двух строкIROWиICOL. В строкиIROWиICOLзаписываются адреса строк и столбцов матрицы связности, имеющие ненулевые элементы.

2.2. Операции над графами

2.2.1. Простейшие операции

Определения

Простейшими операциями над графами являются:

• Добавление вершины: к заданному множеству вершин графа (V₁,V₂,…,V_n) добавляется новая вершинаV_n+1, смежная с вершинами (V₁,V₂,…,V_n).

• Добавление ребра: для заданной пары вершинvиuдобавляется ребро {v,u}.

• Удаление вершины: из графа вершина удаляется вместе с инцидентными ей рёбрами;

• Удаление ребра: в графе удаляется ребро без инцидентных ему вершин;

• Стягивание вершин: заданное множество вершин соединяется в одну, а полученные из ребер петли удаляются;

• Подразбиениеребра: удаляется заданное ребро {u,v} и добавляется путь, имеющий один конец наu, а второй конец – наv.