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

Структуры данных для представления графа

Существует много способов представления графов в машинной памяти. Выбор той или иной структуры данных для представления графа зависит от многих причин. Одной из них является специфика задачи, которая должна решаться при помощи теории графов.

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

С помощью различных матриц можно описывать ориентированные и неориентированные графы, используя алгебраический аппарат. Эти мат­рицы задают отношения инциденций между вершинами и ребрами и, в более общем случае, между циклами, разрезами, цепями и соответствующими ребрами. Они являются удобной формой представления структурных свойств графа.

При описании неориентированных графов элементами  матрицы инциденций  могут быть только нули и единицы. Сложение чисел всегда будет производиться по модулю 2. В этом случае 1+1 = 0 (по модулю 2),                      1 + 0 = 0  + 1 = 1 и 0 + 0 = 0. Та­ким образом, для выполнения операции сложения по модулю 2 необходимо просто сложить соответствующие элементы, затем разделить результат на 2 и остаток записать как результат сложения по модулю 2. Такой выбор элементов матриц позволяет определить наличие некоторого свойства между двумя элементами (тогда соответствующий элемент равен 1) или его отсутствие                                (тогда элемент равен 0).

Матрицы перемножаются и складываются как обыч­но, однако результат всегда записывается по моду­лю 2.

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

Конечно, с такими матрицами работать гораздо труд­нее. Однако принципиально к матрицам ориентирован­ных графов применима теория, аналогичная теории для неориентированных графов.

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

Рекомендуемые материалы

Пусть G - граф, имеющий п вершин и m ребер. Графу G можно сопоставить матрицу инциденций раз­мером п ´ т, строки и столбцы которой соответствуют вершинам и ребрам графа соответственно. Элемент матрицы a_i принимает значение 1 или 0 в зависимости от того, инцидентно j-e ребро i-й вершине или нет. Для петли все элементы столбца считаются равными 0. Например, двухкомпонентный граф, показанный на рис. 6,  имеет следующую матрицу инциденций.

Рис. 6.  Двухкомпонентный граф

Некоторые интересные свойства графа проявляются в его матрице инциденций. Например, так как ребро графа инцидентно точно двум вершинам, то каждый столбец матрицы инциденций содержит равно два единичных элемента. Единственное исключение составляет петля, так как она (дважды) инцидентна одной и той же вершине. Следовательно, столбец, соответствующий петле, состоит из нулевых элементов. Таким образом, матрица инциденций не указывает на существование петель, так как мы не знаем, соответствует ли нулевой столбец петле или нет.

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

При соответствующей нумерации ребер и вершин графа каждая его компонента соответствует подматрице матрицы инциденций, которая в этом случае имеет блоч­ную структуру следующего вида:

Здесь A_i - матрица инциденций, соответствующая i-й ком­поненте графа.

 Блочно-диагональное представление та­кого типа всегда можно получить последовательной ну­мерацией ребер и вершин внутри каждой компоненты и между компонентами, как показано в примере, или непосредственно с помощью перестановки строк и столб­цов матрицы инциденций. Таким образом, матрица инциденций обеспечивает полное описание.

Элементы матрицы инциденций ориентированного графа принимают значения 0, 1, -1. Элемент равен нулю, если вершина не инцидентна дуге, +1, если дуга ориентирована от вершины, и -1 в противном случае. На рис. 7 показан граф, матрица инциденций которого приведена ниже.

Рис. 7. Ориентированный граф

 Матрица циклов

Циклы C_i графа, изображенного на рис. 8, (перенумерованные, как показано на рис. 9), можно представить матрицей, каждая строка которой характеризует один из циклов:

Рис. 8. Несвязный циклический граф

Рис. 9. Нумерация циклов в графе

 Матрица разрезов

Если задан связный граф G = (V, E) и множество его вершин разбито на два непустых подмножества W и W’, то множество ребер, соединяющих W с W’, называется разрезом. То есть, разрез (и в частности, простой разрез) является множеством ребер, соединяющих W и W’ , где {W, W’} является разбиением вершин связного графа на два непересекающихся непустых множества. Удаление разреза приводит к тому, что граф распадается на две или более компоненты. Удаление простого разреза разделяет граф точно на две компоненты.

В ориентированном графе дуги разреза могут быть разделены на два множества: дуги, направленные из W в W’, и дуги, направленные из W’ в W. Удаление первого множества разрывает все пути из W к W’, в то время как удаление последнего разрывает все пути из  W’ к W.

Опишем теперь простые разрезы графа, изображен­ного на рис. 10, с помощью матрицы разрезов, каждая строка которой характеризует один простой разрез. В данном случае мы имеем следующие простые разрезы:

K₁ = {e₂}, K₂ = {e₃, e₇}, K₃ = {e₄, e₅},

K₄ = {e₃, e₄, e₅}, K₅ = {e₃, e₅, e₆}, K₆ = {e₄, e₆, e₇}, K₇ = {e₅, e₆, e₇}.

При этом матрица разрезов будет иметь вид:

Рис. 10. Простые разрезы графа

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

Для ориентированных и неориентированных графов можно определить матрицу смежности вершин (или про­сто матрицу смежности). Элемент на пересечении i-й строки и j-го столбца этой матрицы равен числу ребер, инцидентных одновременно i-й и j-й вершинам (или на­правленных от вершины i к вершине j в случае ориен­тированного графа). Таким образом, для ориентирован­ного графа, изображенного на рис. 8, можно построить  матрицу смежности следующего вида:

В общем случае имеет место следующая теорема, касающаяся матрицы  смежности V графа.

Теорема. Матрица Vⁿ дает число ориентирован­ных маршрутов длины п между любыми двумя верши­нами ориентированного графа.

Доказательство. Если а_ik – число  дуг, соеди­няющих v_i с v_k, а а_kj – число  дуг, соединяющих v_k с v_j, то а_ikа_kj есть число различных ориентированных марш­рутов, каждый из которых состоит из двух дуг, соеди­няющих v_i с v_j, и проходящих через v_k. Если это произ­ведение просуммировать по всем k, т. е. по всем про­межуточным вершинам, то получим число ориентирован­ных маршрутов длины 2 между вершинами v_i и v_j. Используем теперь а_ij для получения а_ijа_jm. В результате найдем число различных ориентированных маршрутов длины 3 между вершинами v_i и v_m проходящих через v_j, и так далее. Таким образом, если  предположить, что теорема верна для , то элементы матрицы         дадут число ориентированных маршрутов длины п между соответствующими вершинами.

Вместе с этой лекцией читают "9 Метод конечных разностей".

Матрица вершин, как в случае ориен­тированных, так и в случае неориентированных графов имеет неотрицательные элементы. Нулевой элемент оз­начает, что вершина, соответствующая строке рассмат­риваемого элемента, не связана ребром с вершиной, со­ответствующей столбцу. Однако эти вершины могут быть связаны путем (или цепью) определенной длины. Может оказаться, что V^m>0 для некоторого целого m ³ 1 , т. е. после возведения V в степень m все ее эле­менты становятся положительными.

В этом случае каждая вершина достижима из лю­бой другой вершины ориентированным маршрутом, со­стоящим из т дуг, и граф, соответствующий V^m, явля­ется полным (действительно, он имеет дугу, направлен­ную от любой другой) и имеет петли у каждой вершины.

 Матрица путей

Для связного графа, вершины которого перенумеро­ваны, можно построить матрицу путей (или цепей) Р следующим образом: строки матрицы должны соответствовать путям из первой вершины в последнюю, а столбцы – ребрам  графа. Следовательно, элемент мат­рицы принимает значение 1 или 0 в зависимости от того, принадлежит ли данное ребро данному пути или нет. Например, граф, изображенный на рис. 11, имеет матрицу путей между вершинами v₁ и v₅:

Рис.11. Граф для иллюстрации матрицы путей