Для алгебраического задания графов используются матрицы смежности и инцидентности.
Матрица смежностиA = ( aij)определяется одинаково для ориентированного и неориентированного графов. Это квадратная матрица порядка n, где n - число вершин, у которой
aij =
Пример 3.5.
Матрица смежности графа, изображенного на рис. 3.1, имеет вид:
A =
Пример 3.6.
Матрица смежности ориентированного графа, изображенного на рис. 3.2, имеет вид:
A =
Матрица смежности полностью задает граф.
Матрицей инцидентностиB = (bij) ориентированного графа называется прямоугольная матрица (n ´ m), где n – число вершин, m – число ребер, у которой
bi =
Для неориентированного графа матрица инцидентности B задается следующим образом:
bi =
Пример 3.7.
Матрица инцидентности графа, изображенного на рис. 3.1, имеет вид:
B =
Пример 3.8.
Матрица инцидентности ориентированного графа, изображенного на рис. 3.2, имеет вид:
B =
Матрица инцидентности, также, как и матрица смежности, полностью задает граф.
Матрицы смежности и инцидентности удобны для задания графов на ЭВМ.
|
|