Представления графов

Из определения графа следует, что каждый граф G=(V,E) можно задать, непосредственно перечислив его множество вершин V и множество ребер E. Однако такое представление неудобно для решения многих задач о графах. Например, чтобы проверить наличие ребра между двумя вершинами, придется, вообще говоря, просмотреть все множество E. Хорошее представление, по крайней мере, должно позволить легко переходить от вершины к ее соседу и перечислять всех ее соседей.

В этом параграфе мы рассмотрим три разных способа представления графов, которые более эффективны при решении типичных для теории графов задач

Матрица (таблица) смежности

Определение 9.5. Матрицей смежности ориентированного (или неориентированного) графа G=(V,E) с n вершинами V= { v₁, … , v_n} называется булева матрица A_G размера n × n с элементами

Это представление позволяет легко проверять наличие ребер между заданными парами вершин. Для поиска всех соседей, в которые ведут ребра из вершины v_i, необходимо просмотреть соответствующую ей i-ю строку матрицы A_G, а чтобы найти вершины, из которых ребра идут в v_i, необходимо просмотреть ее i-ый столбец. Требуемая для A_G память - по порядку n² битов - не может быть уменьшена для графов, у которых "много" ребер. Но для разреженных графов с числом ребер существенно меньшим по порядку n² в матрице смежности много "ненужных" нулей. Для таких графов более эффективными могут оказаться другие представления.

Матрица (таблица) инцидентности

Определение 9.6. Матрицей инцидентности ориентированного (или неориентированного) графа G=(V,E) с n вершинами V= { v₁, … , v_n} и m ребрами E={e₁, …, e_m} называется матрица B_G размера n × m с элементами

Таким образом, в матрице инцидентности B_G любому ребру e_j = (v_i,v_k) соответствует j-ый столбец, в котором в i-ой строке стоит 1, а в k-ой - -1. Ребра-петли выделяются числом 2. Для проверки наличия ребра между двумя вершинами v_i и v_k требуется просмотреть i-ю и k-ую строки B_G, поиск всех соседей вершины требует просмотра соответствующей строки. Если m >> n, то это требует существенно больше времени, чем при использовании матрицы смежности. Поэтому при практическом решении задач на графах матрица инцидентности почти не используется.

Списки смежности

Определение 9.7. Пусть G=(V,E) - ориентированный граф, v - вершина из V. Список смежности L_v для вершины v включает все смежные с ней вершины, т.е.

Представление графа G=(V,E) c n вершинами V= { v₁, … , v_n} с помощью списков смежности состоит из списков смежности всех вершин: L_v1, L_v2, … , L_vn.

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

Пример 9.1. Рассмотрим следующий граф G=(V,E):

Он показан на рис. 9.2.

Построим для него определенные выше представления.

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

2. Матрица инцидентности.

3. Списки смежности.

Граф достижимости

Один из первых вопросов, возникающих при изучении графов, это вопрос о существовании путей между заданными или всеми парами вершин. Ответом на этот вопроc - введенное выше отношение достижимости на вершинах графа G=(V,E): вершина w достижима из вершины v, если v = w или в G есть путь из v в w. Иначе говоря, отношение достижимости является рефлексивным и транзитивным замыканием отношения E. Для неориентированных графов это отношение также симметрично и, следовательно, является отношением эквивалентности на множестве вершин V. В неориентированном графе классы эквивалентности по отношению достижимости называются связными компонентами. Для ориентированных графов достижимость, вообще говоря, не должна быть симметричным отношением. Симметричной является взаимная достижимость.

Определение 9.8. Вершины v и w ориентированного графа G=(V,E) называются взаимно достижимыми, если в G есть путь из v в w и путь из w в v.

Ясно, что отношение взаимной достижимости является рефлексивным, симметричным и транзитивным и, следовательно, эквивалентностью на на множестве вершин графа. Классы эквивалентности по отношению взаимной достижимости называются компонентами сильной связности или двусвязными компонентами графа.

Рассмотрим вначале вопрос о построении отношения достижимости. Определим для каждого графа его граф достижимости ( называемый иногда также графом транзитивного замыкания), ребра которого соответствуют путям исходного графа.

Определение 9.9. Пусть G=(V,E) - ориентированный граф. Граф достижимости G^*=(V,E^*) для G имеет то же множество вершин V и следующее множество ребер E^* ={ (u, v) | в графе G вершина v достижима из вершины u}.

Пример 9.3. Рассмотрим граф G из примера 9.2.

Рис. 9.2.  Граф G

Тогда можно проверить, что граф достижимости G* для G выглядит так (новые ребра-петли при каждой из вершин 1-5 не показаны):

Рис. 9.3.  Граф G*

Каким образом по графу G можно построить граф G^*? Один способ заключается в том, чтобы для каждой вершины графа G определить множество достижимых из нее вершин, последовательно добавляя в него вершины, достижимые из нее путями длины 0, 1, 2 и т.д.

Мы рассмотрим другой способ, основанный на использовании матрицы смежности A_G графа G и булевых операций. Пусть множество вершин V={v₁, … , v_n}. Тогда матрица A_G - это булева матрица размера n × n.

Ниже для сохранения сходства с обычными операциями над матрицами мы будем использовать "арифметические" обозначения для булевых операций: через + будем обозначать дизъюнкцию , а через · - конъюнкцию .

Обозначим через E_n единичную матрицу размера n × n. Положим . Пусть Наша процедура построения G^* основана на следующем утверждении.

Лемма 9.2. Пусть . Тогда

Доказательство проведем индукцией по k.

Базис. При k=0 и k=1 утверждение справедливо по определению и .

Индукционный шаг. Пусть лемма справедлива для k. Покажем, что она остается справедливой и для k+1. По определению имеем:

Предположим, что в графе G из v_i в v_j имеется путь длины k+1. Рассмотрим кратчайший из таких путей. Если его длина k, то по предположению индукции a_{ij}^{(k)}=1. Кроме того, a_jj⁽¹⁾=1. Поэтому a_ij^(k) a_jj⁽¹⁾=1 и a_ij^(k+1)=1. Если длина кратчайшего пути из из v_i в v_j равна k+1, то пусть v_r - его предпоследняя вершина. Тогда из v_i в v_r имеется путь длины k и по предположению индукции a_ir^(k)=1. Так как (v_r,v_j) E, то a_{rj}^{(1)}=1. Поэтому a_ir^(k) a_rj⁽¹⁾=1 и a_ij^(k+1)=1.

Обратно, если a_ij^(k+1)=1, то хотя бы для одного r слагаемое a_ir^(k) a_rj⁽¹⁾ в сумме равно 1. Если это r=j, то a_ij^(k)=1 и по индуктивному предположению в G имеется путь из v_i в v_j длины k. Если же r j, то a_ir^(k)=1 и a_rj⁽¹⁾=1. Это означает, что в G имеется путь из v_i в v_r длины k и ребро (v_r,v_j) E. Объединив их, получаем путь из v_i в v_j длины k+1.

Из лемм 9.1 и 9.2 непосредственно получаем

Следствие 1. Пусть G=(V,E) - ориентированный граф с n вершинами, а G^* - его граф достижимости. Тогда A_{G*} = . Доказательство. Из леммы 5.1 следует, что, если в G имеется путь из u в v u, то в нем имеется и простой путь из u в v длины n-1. А по лемме 5.2 все такие пути представлены в матрице .

Таким образом процедура построения матрицы смежности A_G* графа достижимости для G сводится к возведению матрицы в степень n-1. Сделаем несколько замечаний, позволяющих упростить эту процедуру.

1. Для возведения матрицы в произвольную степень n достаточно выполнить возведений в квадрат:

где k - это наименьшее число такое, что 2^k n.

2. Так как на диагонали в матрице стоят единицы, то для любых i < j все единицы матрицы сохраняются в матрице , в частности, и в матрице .

3. Если при вычислении элемента a_ij⁽²⁾ матрицы по стандартной формуле

обнаруживается такое r, что a_ir = 1 и a_rj =1, то и вся сумма a_ij⁽²⁾ =1. Поэтому остальные слагаемые можно не рассматривать.

Пример 9.3. Рассмотрим в качестве примера вычисление матрицы графа достижимости A_G* для графа G, представленного на рис.9.2. В этом случае

Так как у G имеется 6 вершин, то . Вычислим эту матрицу:

и (последнее равенство нетрудно проверить). Таким образом,

Как видим, эта матрица действительно задает граф , представленный на рис.9.3.