3.5 Матрицы графов

 

Если граф G= (M, N) не имеет петель, то ему можно сопоставить ма­трицу B(G), в которой вершинам соответствуют строки, а дугам — столбцы. В каждом столбце j этой матрицы всего два элемента отличны от нуля: в строке beg j, соответствующей началу дуги (какой дуги? соответ­ствующей этому столбцу j), стоит 1, в строке end j стоит -1. Такая матрица и называется матрицей инцидентности  графа.

Пример.

Рис. 8. Граф и его матрица инцидентности.

 

Если граф G=(M, N) не имеет кратных дуг, то ему можно сопоставить ма­трицу A(G), называемую матрицей смежности. Это квадратная 0-1 матрица  размера |M|.  , если существует дуга из i-ой вершины в j-ю.