Естественно, графы представляются в виде некоторых наборов данных. Подобных представлений существует множество, у каждого есть свои достоинства и недостатки. Общий недостаток состоит в том, что предварительно надо занумеровать вершины (иногда и ребра), это приводит к сложностям, например, при проверке изоморфизма графов. Приведем три наиболее распространенных представления.
1. Матрица смежностиS(Г).
Это квадратная матрица размеров p´p (как обычно, p – число вершин). Для ее построения надо занумеровать вершины. Матрица S(Г) булева (ее элементы 0 или 1). S(Г)ij=1 тогда и только тогда, когда в графе существует дуга (ai,aj). Таким образом, каждой дуге графа соответствует 1 в матрице смежности и наоборот, на главной диагонали расположены нули. Матрица смежности неориентированного графа симметрическая. Матрицу смежности можно определить и для псевдографа, тогда на главной диагонали могут быть и единицы.
Такое представление неэкономно в случае, если в графе мало дуг (в матрице в основном нули).
2. Матрица инциденцийI(Г).
Размеры этой матрицы q´p. Для ее построения необходимо занумеровать и вершины, и дуги. В каждой строке матрицы для ориентированного графа присутствуют один элемент –1 , один элемент 1, остальные 0.Для неориентированного графа – две единицы, остальные нули. I(Г)ij=–1 (1), если i-я дуга исходит из j-й вершины (приходит в j-ю вершину), модификация для неориентированного графа очевидна. Это представление целесообразно использовать при малом числе дуг. Дополнительную сложность доставляет двойная нумерация.
3. Список дуг.
Это матрица размеров q´2. Каждая строка соответствует дуге. На первом месте номер начальной вершины дуги, на втором – конечной. Этот способ имеет те же недостатки, что и предыдущий, но экономнее.
Введенные матрицы S(Г) и I(Г) обладают рядом интересных свойств. Сформулируем две теоремы такого типа.
Теорема 15.Элемент Sn(Г)ij n-й степени матрицы S(Г) равен числу маршрутов длины n, соединяющих i-ю вершину графа с j-й. (Соответствующие понятия см. в следующем разделе).
Теорема 16.Пусть L(Г) – граф, смежный к неориентированному графу Г. Справедливо равенство S(L(Г))=I(Г)IТ(Г)-2Eq. Здесь IТ(Г) – транспонированная матрица, Eq – единичная матрица q´q, в правой части используется обычное умножение матриц.