Определим 3 вида матриы ассоциир. графу G=(X,E): матрица смежности; матрица инцидентности; матрица Киргоффа.
Матрица смежности: A с индексами n*n. Элементы:1 если вершины смежны, 0 если не смежны. Свойства: квадратная; бинарная; Симметричная относительно главной диагонали; элементы на главной=0; сумма элементив некоторой строки(столбца) определяет степень вершины сообтветствующей данной строке(столбцу).
Матрица инцидентности: I с индексами n x m. Элементы: 1 если вершина смежна ребру, 0 в противном случае. Свойства: Сумма элементов каждой строки определяет степень вершины сообветствующей данной строки; сумма элементив каждого столбца=2.
Матрица Киргоффа: B с индексами n*n. Элементы: -1 если вершины смежны; d(x) степень вершины если на главной диагонали; 0 в противном случае. Свойства: квадратная; симетричная относительно главной; элементы главной диагонали это степень соответствующей строке вершины; сумма всех элементов=0.
2 матричное представление графа. Определения и свойства матриц
Матричное представление графов
Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.
Матрица инцидентности((vertex-edge) incidence matrix)
- (0,1)-матрица I(G) размером n m (n - число вершин, m - число ребер/дуг графа G), (i,j)-й элемент которой равен 1, если вершина v инцидентна ребру e в неориентированном графе или если v есть начало дуги e , равен -1, если вершина v есть конец дуги e (только для орграфов), и равен 0 в остальных случаях.
Матрица инцидентности определяет граф с точностью до изоморфизма.
Матрица смежности(Adjacency matrix, vertex incidence matrix)
- (0,1)-матрица A(G) размером n n (n - число вершин в G), (i,j)-й элемент a которой равен 1, если вершины v и v смежны, т.е. соединены дугой (или ребром) (v , v ), и равен 0 в противном случае. Для неориентированного графа М.с. есть симметричная матрица с нулями на главной диагонали. В М.с. для мультиграфов и псевдографов (i,j)-й элемент равен числу ребер, соединяющих вершины v и v (при этом петля считается как два ребра).
М.с. определяет граф (орграф, мультиграф, псевдограф) с точностью до изоморфизма.
Свойства
Матрица смежности неориентированного графа симметрична, а значит обладает действительными собственными значениями и ортогональным базисом из собственных векторов. Набор её собственных значений называется спектром графа, и является основным предметом изучения спектральной теории графов.
Два графа G1 и G2 с матрицами смежности A1 и A2 являются изоморфными если и только если существует перестановочная матрица P, такая что
PA1P-1 = A2.
Из этого следует, что матрицы A1 и A2 подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны.
Степени матрицы
Если A — матрица смежности графа G, то матрица Am обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.