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

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