Understanding Incidence and Adjacency Matrices for Directed and Weighted Graphs

1 Incidence Matrix

For an undirected graph G, the incidence matrix B is defined such that B[i][j] = 1 if vertex i is incident to edge j, otherwise 0.

For a directed graph G, the incidence matrix B is defined as B[i][j] = 1 if vertex i is the tail (starting point) of edge j, B[i][j] = -1 if vertex i is the head (ending point) of edge j, and 0 otherwise.

2 Adjacency Matrix

For an undirected unweighted graph G with n vertices, the adjacency matrix A is an n×n matrix where A[i][j] = 1 if vertices i and j are adjacent, otherwise 0.

For a directed unweighted graph, the adjacency matrix A is defined such that A[i][j] = 1 if there is an edge from vertex i to vertex j, otherwise 0.

For an undirected weighted graph, the adjacency matrix A contains the edge weight w(i,j) at A[i][j] when an edge exists; if no edge exists, the entry can be 0 or a special value (e.g., ∞) depending on the algorithm.

The adjacency matrix for a directed weighted graph is defined analogously, with A[i][j] equal to the weight of the edge from i to j, and 0 or a sentinel value when no such edge exists.

Reference

Python数学实验与建模 / 司守奎, 孙玺菁, 科学出版社