DavePearce / TuttePolynomial

Tutte Polynomial Computation
BSD 3-Clause "New" or "Revised" License
2 stars 2 forks source link

Improve Chromatic Polynomial Computation #9

Open DavePearce opened 1 year ago

DavePearce commented 1 year ago

Notes from Gary:

if vertices x and y have n edges joining them. their tutte polynomial is

T(G with n (x,y) edges, x,y) = G with one (x.y) edge, x, y) + (y^{n-1} + y^{n - 2} + ... + y^{2} + y^{1}) T(G with (x,y) contracted and multiple (x,y) edges deleted,x,y)

the polynomial can be stacked with the graph as a value n-i and then the final answer is multiplied by all these similar polynomials collected in the computation of the graph. we do this final multiplication process now but do not make sure there are no multiple edges to be considered in any delete/contract step

DavePearce commented 1 year ago

step_1 Step_2 step_3 step_4 step_5