1. Матрица инцидентности.

Это прямоугольная матрица размерности n х щ, где n – количество вершин, am – количество ребер. Значения элементов матрицы определяются следующим образом: если ребро xi и вершина vj инцидентны, то значение соотвествующего элемента матрицы равно единице, в противном случае значение равно нулю. Для ориентированных графов матрица инцидентности строится по следующему принципу: значение элемента равно – 1, если ребро xi исходит из вершины vj, равно 1, если ребро xi заходит в вершину vj, и равно О в противном случае.