double arrow

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

Это булева матрица графа порядка n2.

Просматривая строки и столбцы матриц смежности, находим соответствующие множества смежности; сумма единиц равна степени вершины. Для орграфов соответственно множество потомков и множество предшественников (родителей). — В каждой строке матрицы смежности орграфа количество единиц равно d+, а в каждом столбце количество единиц равно d.

Сложность – O(n2).

Ранг матрицы смежности называется рангом графа. Обозначение: rank G. Характеристические числа графа – характеристические числа его матрицы смежности.

Для изоморфных графов матрицы смежности отличаются перестановками строк и столбцов – следовательно, характеристические многочлены изоморфных графов совпадают.

rank A=3, cA(l)=l(l+1)2(l–2); rank B=3, cB(l)=l(l–1)(l2+l+1).

Транзитивное замыкание графа:

Орграфа:


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: