Incidence Matrix in Python
In graph theory, an incidence matrix is a matrix that shows the relationship between vertices and edges in a graph. This matrix is a fundamental tool used in various applications, including network analysis, circuit design, and computer science. This article will cover the basics of incidence matrices, how to create and manipulate them using Python.
What is an Incidence Matrix?
An incidence matrix is a rectangular matrix with dimensions (V x E), where:
- V is the number of vertices in the graph.
- E is the number of edges in the graph.
Each element a_ij of the matrix represents the connection between the i-th vertex and the j-th edge:
- aij = 1 if the i-th vertex is incident to the j-th edge (i.e., the edge connects to the vertex).
- aij = 0 if the i-th vertex is not incident to the j-th edge.
Building an Incidence Matrix from a Graph
Here’s how to build an incidence matrix for a given graph:
- Identify the number of vertices (V) and edges (E).
- Create a (V x E) matrix filled with zeros.
- Iterate through each edge in the graph.
- For each edge, find the two vertices it connects.
- Set the corresponding elements in the matrix to 1 for those vertices and that edge.
Implementation of Incidence Matrix in Python
- Import numpy as np
- Define your graph as a dictionary
- Get the number of vertices (V) and edges (E)
- Create a zero-filled matrix of size (V x E)
- Iterate through edges and set corresponding elements to 1
- for i, edge in enumerate(edges)
- print the matrix
Below is the implementation of an incidence matrix in Python:
import numpy as np
def build_incidence_matrix(graph):
# A NumPy array representing the incidence matrix.
vertices = list(graph.keys())
edges = [(v1, v2) for v1 in vertices for v2 in graph[v1] if v1 < v2]
matrix = np.zeros((len(vertices), len(edges)))
for i, edge in enumerate(edges):
v1, v2 = edge
matrix[vertices.index(v1), i] = 1
matrix[vertices.index(v2), i] = 1
return matrix
# Example usage
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "E"],
"D": ["B"],
"E": ["C"],
}
incidence_matrix = build_incidence_matrix(graph)
print(incidence_matrix)
Output
[[1. 1. 0. 0. 0.] [1. 0. 1. 1. 0.] [0. 1. 1. 0. 1.] [0. 0. 0. 1. 0.] [0. 0. 0. 0. 1.]]
Contact Us