Matching polynomial¶
This module contains the following methods:
Compute the matching polynomial of a given graph. |
|
Compute the matching polynomial of the complete graph on \(n\) vertices. |
AUTHORS:
Robert Miller, Tom Boothby - original implementation
REFERENCE:
Methods¶
- sage.graphs.matchpoly.complete_poly(n)[source]¶
Compute the matching polynomial of the complete graph on \(n\) vertices.
INPUT:
n
– order of the complete graph
Todo
This code could probably be made more efficient by using FLINT polynomials and being written in Cython, using an array of fmpz_poly_t pointers or something… Right now just about the whole complement optimization is written in Python, and could be easily sped up.
EXAMPLES:
sage: from sage.graphs.matchpoly import complete_poly sage: f = complete_poly(10) sage: f x^10 - 45*x^8 + 630*x^6 - 3150*x^4 + 4725*x^2 - 945 sage: f = complete_poly(20) sage: f[8] 1309458150 sage: f = complete_poly(1000) sage: len(str(f)) 406824
>>> from sage.all import * >>> from sage.graphs.matchpoly import complete_poly >>> f = complete_poly(Integer(10)) >>> f x^10 - 45*x^8 + 630*x^6 - 3150*x^4 + 4725*x^2 - 945 >>> f = complete_poly(Integer(20)) >>> f[Integer(8)] 1309458150 >>> f = complete_poly(Integer(1000)) >>> len(str(f)) 406824
- sage.graphs.matchpoly.matching_polynomial(G, complement=True, name=None)[source]¶
Compute the matching polynomial of the graph \(G\).
If \(p(G, k)\) denotes the number of \(k\)-matchings (matchings with \(k\) edges) in \(G\), then the matching polynomial is defined as [God1993]:
\[\mu(x)=\sum_{k \geq 0} (-1)^k p(G,k) x^{n-2k}\]INPUT:
complement
– boolean (default:True
); whether to use Godsil’s duality theorem to compute the matching polynomial from that of the graphs complement (see ALGORITHM)name
– (optional) string for the variable name in the polynomial
Note
The
complement
option uses matching polynomials of complete graphs, which are cached. So if you are crazy enough to try computing the matching polynomial on a graph with millions of vertices, you might not want to use this option, since it will end up caching millions of polynomials of degree in the millions.ALGORITHM:
The algorithm used is a recursive one, based on the following observation [God1993]:
If \(e\) is an edge of \(G\), \(G'\) is the result of deleting the edge \(e\), and \(G''\) is the result of deleting each vertex in \(e\), then the matching polynomial of \(G\) is equal to that of \(G'\) minus that of \(G''\).
(the algorithm actually computes the signless matching polynomial, for which the recursion is the same when one replaces the subtraction by an addition. It is then converted into the matching polynomial and returned)
Depending on the value of
complement
, Godsil’s duality theorem [God1993] can also be used to compute \(\mu(x)\) :\[\mu(\overline{G}, x) = \sum_{k \geq 0} p(G,k) \mu( K_{n-2k}, x)\]Where \(\overline{G}\) is the complement of \(G\), and \(K_n\) the complete graph on \(n\) vertices.
EXAMPLES:
sage: g = graphs.PetersenGraph() sage: g.matching_polynomial() x^10 - 15*x^8 + 75*x^6 - 145*x^4 + 90*x^2 - 6 sage: g.matching_polynomial(complement=False) x^10 - 15*x^8 + 75*x^6 - 145*x^4 + 90*x^2 - 6 sage: g.matching_polynomial(name='tom') tom^10 - 15*tom^8 + 75*tom^6 - 145*tom^4 + 90*tom^2 - 6 sage: g = Graph() sage: L = [graphs.RandomGNP(8, .3) for i in range(1, 6)] sage: prod([h.matching_polynomial() for h in L]) == sum(L, g).matching_polynomial() # long time (up to 10s on sage.math, 2011) True
>>> from sage.all import * >>> g = graphs.PetersenGraph() >>> g.matching_polynomial() x^10 - 15*x^8 + 75*x^6 - 145*x^4 + 90*x^2 - 6 >>> g.matching_polynomial(complement=False) x^10 - 15*x^8 + 75*x^6 - 145*x^4 + 90*x^2 - 6 >>> g.matching_polynomial(name='tom') tom^10 - 15*tom^8 + 75*tom^6 - 145*tom^4 + 90*tom^2 - 6 >>> g = Graph() >>> L = [graphs.RandomGNP(Integer(8), RealNumber('.3')) for i in range(Integer(1), Integer(6))] >>> prod([h.matching_polynomial() for h in L]) == sum(L, g).matching_polynomial() # long time (up to 10s on sage.math, 2011) True
sage: for i in range(1, 12): # long time (10s on sage.math, 2011) ....: for t in graphs.trees(i): ....: if t.matching_polynomial() != t.characteristic_polynomial(): ....: raise RuntimeError('bug for a tree A of size {0}'.format(i)) ....: c = t.complement() ....: if c.matching_polynomial(complement=False) != c.matching_polynomial(): ....: raise RuntimeError('bug for a tree B of size {0}'.format(i))
>>> from sage.all import * >>> for i in range(Integer(1), Integer(12)): # long time (10s on sage.math, 2011) ... for t in graphs.trees(i): ... if t.matching_polynomial() != t.characteristic_polynomial(): ... raise RuntimeError('bug for a tree A of size {0}'.format(i)) ... c = t.complement() ... if c.matching_polynomial(complement=False) != c.matching_polynomial(): ... raise RuntimeError('bug for a tree B of size {0}'.format(i))
sage: from sage.graphs.matchpoly import matching_polynomial sage: matching_polynomial(graphs.CompleteGraph(0)) 1 sage: matching_polynomial(graphs.CompleteGraph(1)) x sage: matching_polynomial(graphs.CompleteGraph(2)) x^2 - 1 sage: matching_polynomial(graphs.CompleteGraph(3)) x^3 - 3*x sage: matching_polynomial(graphs.CompleteGraph(4)) x^4 - 6*x^2 + 3 sage: matching_polynomial(graphs.CompleteGraph(5)) x^5 - 10*x^3 + 15*x sage: matching_polynomial(graphs.CompleteGraph(6)) x^6 - 15*x^4 + 45*x^2 - 15 sage: matching_polynomial(graphs.CompleteGraph(7)) x^7 - 21*x^5 + 105*x^3 - 105*x sage: matching_polynomial(graphs.CompleteGraph(8)) x^8 - 28*x^6 + 210*x^4 - 420*x^2 + 105 sage: matching_polynomial(graphs.CompleteGraph(9)) x^9 - 36*x^7 + 378*x^5 - 1260*x^3 + 945*x sage: matching_polynomial(graphs.CompleteGraph(10)) x^10 - 45*x^8 + 630*x^6 - 3150*x^4 + 4725*x^2 - 945 sage: matching_polynomial(graphs.CompleteGraph(11)) x^11 - 55*x^9 + 990*x^7 - 6930*x^5 + 17325*x^3 - 10395*x sage: matching_polynomial(graphs.CompleteGraph(12)) x^12 - 66*x^10 + 1485*x^8 - 13860*x^6 + 51975*x^4 - 62370*x^2 + 10395 sage: matching_polynomial(graphs.CompleteGraph(13)) x^13 - 78*x^11 + 2145*x^9 - 25740*x^7 + 135135*x^5 - 270270*x^3 + 135135*x
>>> from sage.all import * >>> from sage.graphs.matchpoly import matching_polynomial >>> matching_polynomial(graphs.CompleteGraph(Integer(0))) 1 >>> matching_polynomial(graphs.CompleteGraph(Integer(1))) x >>> matching_polynomial(graphs.CompleteGraph(Integer(2))) x^2 - 1 >>> matching_polynomial(graphs.CompleteGraph(Integer(3))) x^3 - 3*x >>> matching_polynomial(graphs.CompleteGraph(Integer(4))) x^4 - 6*x^2 + 3 >>> matching_polynomial(graphs.CompleteGraph(Integer(5))) x^5 - 10*x^3 + 15*x >>> matching_polynomial(graphs.CompleteGraph(Integer(6))) x^6 - 15*x^4 + 45*x^2 - 15 >>> matching_polynomial(graphs.CompleteGraph(Integer(7))) x^7 - 21*x^5 + 105*x^3 - 105*x >>> matching_polynomial(graphs.CompleteGraph(Integer(8))) x^8 - 28*x^6 + 210*x^4 - 420*x^2 + 105 >>> matching_polynomial(graphs.CompleteGraph(Integer(9))) x^9 - 36*x^7 + 378*x^5 - 1260*x^3 + 945*x >>> matching_polynomial(graphs.CompleteGraph(Integer(10))) x^10 - 45*x^8 + 630*x^6 - 3150*x^4 + 4725*x^2 - 945 >>> matching_polynomial(graphs.CompleteGraph(Integer(11))) x^11 - 55*x^9 + 990*x^7 - 6930*x^5 + 17325*x^3 - 10395*x >>> matching_polynomial(graphs.CompleteGraph(Integer(12))) x^12 - 66*x^10 + 1485*x^8 - 13860*x^6 + 51975*x^4 - 62370*x^2 + 10395 >>> matching_polynomial(graphs.CompleteGraph(Integer(13))) x^13 - 78*x^11 + 2145*x^9 - 25740*x^7 + 135135*x^5 - 270270*x^3 + 135135*x
sage: G = Graph({0:[1,2], 1:[2]}) sage: matching_polynomial(G) x^3 - 3*x sage: G = Graph({0:[1,2]}) sage: matching_polynomial(G) x^3 - 2*x sage: G = Graph({0:[1], 2:[]}) sage: matching_polynomial(G) x^3 - x sage: G = Graph({0:[], 1:[], 2:[]}) sage: matching_polynomial(G) x^3
>>> from sage.all import * >>> G = Graph({Integer(0):[Integer(1),Integer(2)], Integer(1):[Integer(2)]}) >>> matching_polynomial(G) x^3 - 3*x >>> G = Graph({Integer(0):[Integer(1),Integer(2)]}) >>> matching_polynomial(G) x^3 - 2*x >>> G = Graph({Integer(0):[Integer(1)], Integer(2):[]}) >>> matching_polynomial(G) x^3 - x >>> G = Graph({Integer(0):[], Integer(1):[], Integer(2):[]}) >>> matching_polynomial(G) x^3
sage: matching_polynomial(graphs.CompleteGraph(0), complement=False) 1 sage: matching_polynomial(graphs.CompleteGraph(1), complement=False) x sage: matching_polynomial(graphs.CompleteGraph(2), complement=False) x^2 - 1 sage: matching_polynomial(graphs.CompleteGraph(3), complement=False) x^3 - 3*x sage: matching_polynomial(graphs.CompleteGraph(4), complement=False) x^4 - 6*x^2 + 3 sage: matching_polynomial(graphs.CompleteGraph(5), complement=False) x^5 - 10*x^3 + 15*x sage: matching_polynomial(graphs.CompleteGraph(6), complement=False) x^6 - 15*x^4 + 45*x^2 - 15 sage: matching_polynomial(graphs.CompleteGraph(7), complement=False) x^7 - 21*x^5 + 105*x^3 - 105*x sage: matching_polynomial(graphs.CompleteGraph(8), complement=False) x^8 - 28*x^6 + 210*x^4 - 420*x^2 + 105 sage: matching_polynomial(graphs.CompleteGraph(9), complement=False) x^9 - 36*x^7 + 378*x^5 - 1260*x^3 + 945*x sage: matching_polynomial(graphs.CompleteGraph(10), complement=False) x^10 - 45*x^8 + 630*x^6 - 3150*x^4 + 4725*x^2 - 945 sage: matching_polynomial(graphs.CompleteGraph(11), complement=False) x^11 - 55*x^9 + 990*x^7 - 6930*x^5 + 17325*x^3 - 10395*x sage: matching_polynomial(graphs.CompleteGraph(12), complement=False) x^12 - 66*x^10 + 1485*x^8 - 13860*x^6 + 51975*x^4 - 62370*x^2 + 10395 sage: matching_polynomial(graphs.CompleteGraph(13), complement=False) x^13 - 78*x^11 + 2145*x^9 - 25740*x^7 + 135135*x^5 - 270270*x^3 + 135135*x
>>> from sage.all import * >>> matching_polynomial(graphs.CompleteGraph(Integer(0)), complement=False) 1 >>> matching_polynomial(graphs.CompleteGraph(Integer(1)), complement=False) x >>> matching_polynomial(graphs.CompleteGraph(Integer(2)), complement=False) x^2 - 1 >>> matching_polynomial(graphs.CompleteGraph(Integer(3)), complement=False) x^3 - 3*x >>> matching_polynomial(graphs.CompleteGraph(Integer(4)), complement=False) x^4 - 6*x^2 + 3 >>> matching_polynomial(graphs.CompleteGraph(Integer(5)), complement=False) x^5 - 10*x^3 + 15*x >>> matching_polynomial(graphs.CompleteGraph(Integer(6)), complement=False) x^6 - 15*x^4 + 45*x^2 - 15 >>> matching_polynomial(graphs.CompleteGraph(Integer(7)), complement=False) x^7 - 21*x^5 + 105*x^3 - 105*x >>> matching_polynomial(graphs.CompleteGraph(Integer(8)), complement=False) x^8 - 28*x^6 + 210*x^4 - 420*x^2 + 105 >>> matching_polynomial(graphs.CompleteGraph(Integer(9)), complement=False) x^9 - 36*x^7 + 378*x^5 - 1260*x^3 + 945*x >>> matching_polynomial(graphs.CompleteGraph(Integer(10)), complement=False) x^10 - 45*x^8 + 630*x^6 - 3150*x^4 + 4725*x^2 - 945 >>> matching_polynomial(graphs.CompleteGraph(Integer(11)), complement=False) x^11 - 55*x^9 + 990*x^7 - 6930*x^5 + 17325*x^3 - 10395*x >>> matching_polynomial(graphs.CompleteGraph(Integer(12)), complement=False) x^12 - 66*x^10 + 1485*x^8 - 13860*x^6 + 51975*x^4 - 62370*x^2 + 10395 >>> matching_polynomial(graphs.CompleteGraph(Integer(13)), complement=False) x^13 - 78*x^11 + 2145*x^9 - 25740*x^7 + 135135*x^5 - 270270*x^3 + 135135*x