|
(Sage)
from sage.graphs.independent_sets import IndependentSets
from math import factorial
from time import time
#Function to calculate a binomial coefficient (n choose r)
def choose(n, r):
return factorial(n) / (factorial(r) * factorial(n - r))
#Function that checks if a polynomial has a certain root
def root_in_poly(poly, root):
root_list = poly.roots()
for tuple in root_list:
for elt in tuple:
if root == elt:
return True
return False
#Builds an independence polynomial for a graph
def build_ip(graph):
number_of = [0] * graph.order()
for set in IndependentSets(graph):
number_of[len_set] += 1;
poly = 0
for index in range(0, len(number_of)):
poly += (number_of[index]) * (x ** index)
return poly
ip_list = []
R.<x> = QQ[]
root = -1
for v in range(4, 10):
count = 0
for g in graphs(v):
if g.is_connected():
ip = build_ip(g)
if root_in_poly(ip, root):
ip_list.append(ip)
count += 1
print(v, ": ", count)
| 