Provides algorithms supporting the computation of graph polynomials.
Graph polynomials are polynomial-valued graph invariants that encode a wide variety of structural information. Examples include the Tutte polynomial, chromatic polynomial, characteristic polynomial, and matching polynomial. An extensive treatment is provided in .
For a simple example, the
method can be used to compute the characteristic polynomial from the adjacency
matrix of a graph. Consider the complete graph
>>> import sympy >>> x = sympy.Symbol("x") >>> G = nx.complete_graph(4) >>> A = nx.adjacency_matrix(G) >>> M = sympy.SparseMatrix(A.todense()) >>> M.charpoly(x).as_expr() x**4 - 6*x**2 - 8*x - 3
Y. Shi, M. Dehmer, X. Li, I. Gutman, “Graph Polynomials”
Returns the Tutte polynomial of
Returns the chromatic polynomial of