Incidence Matrix¶
In graph theory, the incidence matrix of an undirected graph is a matrix that represents the relationship between vertices and edges. This matrix has rows corresponding to the number of vertices and columns corresponding to the number of edges.
Each entry in the matrix is either 0 or 1. An entry of 1 in row i and column j indicates that vertex i is incident with edge j. For directed graphs, the matrix may use -1 and 1 to represent edge directions.
Example code for generating an incidence matrix:
# Initialize incidence matrix
def create_incidence_matrix(vertices, edges):
# sakht matrix sefr
matrix = [[0] * len(edges) for _ in vertices]
for idx, edge in enumerate(edges):
u, v = edge
matrix[u][idx] = 1 # reshteh u
matrix[v][idx] = 1 # reshteh v
return matrix
Properties: - The sum of entries in any column is 2 for undirected graphs. - For graphs without loops, every column has exactly two 1s.
Incidence Matrix
---------------
In simple graphs, the incidence matrix is an n × m matrix where :math:`a_{ij}` is 1 if vertex i is an endpoint of edge j, and 0 if vertex i is not an endpoint of edge j.
All entries of this matrix are either 0 or 1.
If multiple edges exist, the incidence matrix remains unaffected, as it simply adds more columns without altering the matrix's structure or general definition.
However, loops change the situation slightly: the vertex with a loop receives the value 2 instead of 1, meaning :math:`a_{ij}` becomes 2 if vertex i has loop j.
In directed graphs, the incidence matrix takes a different structure. Here, :math:`a_{ij}` is 1 if edge j originates from vertex i or is a loop, -1 if edge j terminates at vertex i, and 0 otherwise.
The sum of all values in the incidence matrix of a directed graph gives the number of loops.
.. figure:: /_static/IncidenceMatrixDirected.png
:width: 80%
:align: center
:alt: IncidenceMatrixDirected
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
