Компьютерные представления графов

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

1. Матрица смежности S (Г).

Это квадратная матрица размеров p´p (как обычно, p – число вершин). Для ее построения надо занумеровать вершины. Матрица S (Г) булева (ее элементы 0 или 1). S (Г) _ij =1 тогда и только тогда, когда в графе существует дуга (a_i,a_j). Таким образом, каждой дуге графа соответствует 1 в матрице смежности и наоборот, на главной диагонали расположены нули. Матрица смежности неориентированного графа симметрическая. Матрицу смежности можно определить и для псевдографа, тогда на главной диагонали могут быть и единицы.

Такое представление неэкономно в случае, если в графе мало дуг (в матрице в основном нули).

2. Матрица инциденций I (Г).

Размеры этой матрицы q´p. Для ее построения необходимо занумеровать и вершины, и дуги. В каждой строке матрицы для ориентированного графа присутствуют один элемент –1, один элемент 1, остальные 0.Для неориентированного графа – две единицы, остальные нули. I (Г) _ij =–1 (1), если i- я дуга исходит из j- й вершины (приходит в j- ю вершину), модификация для неориентированного графа очевидна. Это представление целесообразно использовать при малом числе дуг. Дополнительную сложность доставляет двойная нумерация.

3. Список дуг.

Это матрица размеров q´ 2. Каждая строка соответствует дуге. На первом месте номер начальной вершины дуги, на втором – конечной. Этот способ имеет те же недостатки, что и предыдущий, но экономнее.

Введенные матрицы S (Г) и I (Г) обладают рядом интересных свойств. Сформулируем две теоремы такого типа.

Теорема 15. Элемент Sⁿ (Г) _ij n- й степени матрицы S (Г) равен числу маршрутов длины n, соединяющих i- ю вершину графа с j -й. (Соответствующие понятия см. в следующем разделе).

Теорема 16. Пусть L (Г) – граф, смежный к неориентированному графу Г. Справедливо равенство S (L (Г))= I (Г) I ^Т(Г)-2 E_q. Здесь I ^Т(Г) – транспонированная матрица, E_q – единичная матрица q ´ q, в правой части используется обычное умножение матриц.