Kirchoff's Theorem, coded in python using numpy.

What: Algorithm to find number of spanning trees for a connected graph.

Why: To get number of possible routes with unrepeating edges.

Kirchoff's Theorem:

For a given connected graph G with n labeled vertices, let λ1, λ2, ..., λn−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is:

t(G) = 1/n (λ1λ2λ3λ4...λn-1).

English Translation: Kirchoff's Theorem calculates number of spanning trees that can be made by a given unweighted (the one without arrows and numbers on edges) using some matrix transformations.

We will explore these transformations one by one and then code it in python.

You can download the jupyter notebook from the bottom of the page.

Input:

Line 1: Vertices seperated by space,

Line 2: Edges seprated by space.

Step 1: In a 2 dimentional matrix of n x n, where n are the edges, represent every edge that exists as 1 and rest as 0. (i.e adjacency matrix)

For optimizing this process we will not make a adjacency matrix as all one's will be replaced by some other values instead anyways.

n = len(vertices) # dimension of matrix
matrix = np.zeros((n, n), dtype= int)

Step 2: Replace all the diagonal elements with the degree of vertices.

To get the degree of vertices we simply count the number of times a vertice appears in the edges and store it in a list.

The following code will calculate the degree of vertices:

def get_degree_of_vertices(vertices, edges):
 degree_list = []
 for vertice in vertices:
 count = sum(vertice in edge for edge in edges)
 degree_list.append(count)
 return degree_list

Replacing diagonal elements of matrix with degree of vertice:

degree_list = get_degree_of_vertices(vertices, edges)
for i in range(n): # insert degree of vertex for diagonal elements
    matrix[i, i] = degree_list[i]

Step 3: Replace all non-daigonal 1's with -1.

for edge in edges:
	x = ord(edge[0]) - ord(vertices[0]) 
	y = ord(edge[1]) - ord(vertices[0]) 
	matrix[x, y] = -1 
	matrix[y, x] = -1

Step 4: Calculate Co-factor of any element we will always calculate it for matrix[0, 0].

We need to get minor of matrix[0, 0] before calculating the determinant, which can be done easily using:

np.delete(np.delete(arr, i, axis=0), j, axis=1)

Determinant can be calculated by a numpy function as follows:

round(np.linalg.det(min_mat))

Note: I am rounding off the value because the function returns an approximate float value.

The cofactor aquired is the maximum number of spanning trees that can be created for that graph.

Copy-Paste Code:

#Kirchoff's Theorem for undirected graphs
import numpy as np

def get_degree_of_vertices(vertices, edges):
 degree_list = []
 for vertice in vertices:
 count = sum(vertice in edge for edge in edges)
 degree_list.append(count)
 return degree_list

def get_matrix(vertices , edges):
 vertices = sorted(vertices)
 n = len(vertices) # dimension of matrix
 
 matrix = np.zeros((n, n), dtype= int) #creating matrix with all zeroes 
 degree_list = get_degree_of_vertices(vertices, edges) # getting degree of all vertices
 
 # STEP 2 
 for i in range(n): # insert degree of vertex for diagonal elements
 matrix[i, i] = degree_list[i] 
 
 # STEP 3
 for edge in edges:
 x = int(edge[0]) - int(vertices[0]) # represent vertice as index of matrix, smallest alphabet is 0
 y = int(edge[1]) - int(vertices[0]) 
 
 matrix[x, y] = -1 #if edge exists insert -1
 matrix[y, x] = -1

 return matrix

def matrix_minor(arr, i, j):
 return np.delete(np.delete(arr, i, axis=0), j, axis=1)

def get_number_of_spanning_trees(vertices, edges):
 
 matrix = get_matrix(vertices, edges)
 min_mat = matrix_minor(matrix, 0 ,0)
 
 return round(np.linalg.det(min_mat))

def main():
 vertices = input('Enter the vertices: ').split()
 edges = input('Enter the edges: ')

 for i in range(len(vertices)):
 edges = "".join(edges.replace(vertices[i], str(i)))
 vertices[i] = str(i)
 edges = edges.split()
 
 print(get_number_of_spanning_trees(vertices, edges))

if __name__ == '__main__':
 main()

Download:

Kirchoff's Theorem:

Input:

Comments