Lesson 10

The proven theorem allows computing \(\tau(G)\) in time \(O(n^{3})\) (and even in time \(O(n^{\omega})\), where \(\omega < 2{,}38\) is the exponent of matrix multiplication).

from networkx import Graph, laplacian_matrix
from numpy.linalg import det
from numpy import delete

g = Graph([(1, 2), (2, 3), (3, 4), (4, 1), (2, 4)])
m = laplacian_matrix(g).A
m = delete(arr=m, obj=0, axis=0)
m = delete(arr=m, obj=0, axis=1)
print(round(det(m)))

8