Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Project: Test
Views: 60
import itertools def get_edge_index(G, i, j): count = 0; for e in G.edge_iterator(): #print "x[" + str(count) + "]: " + str(e) if (i in e) and (j in e): #print "edge(" + str(i) + "," + str(j) + ") = " + str(e) + " = x[" + str(count) + "]" return count; #end if count = count + 1; #end for return (-1) #end if debug # create a domination-critical graph, example 15 from "an algebraic exploration of dominating # sets and Vizing's conjecture" g = Graph(); g.add_edges([(0,2),(0,5),(0,4), (1,5),(2,3),(2,5),]); #g.show() #print "Graph has " + str(g.order()) + " vertices and " + str(g.size()) + " edges" n = 4; k = 2; g = graphs.CompleteGraph(n); g.show() print "Graph has " + str(g.order()) + " vertices and " + str(g.size()) + " edges" print "Display variable -> edge dictionary" count = 0 for e in g.edge_iterator(): print "x[" + str(count) + "] = (" + str(e[0]) + "," + str(e[1]) + ")" count = count + 1; #end for P = PolynomialRing(QQ, g.size(), 'x', order="lex") # over F2 x = P.gens() I = list(); # create an empty list for e in range(0, g.size()): #print "Constructing boolean polynomials, one per edge" # for each edge, create the polynomial eij^2 - eij I.append( x[e]^2 - x[e] ); #end for #print "|I| = " + str(len(I)) # ask if there is a dominating set of size k ilist = list(IntegerRange(g.order())) L = list(itertools.combinations((ilist), k)) #L tp = 1; for si in range(0, len(L)): curset = L[si] #print "processing curset = " + str(curset) # for each vertex, is it in or out of S in_s = 0; for i in range(0,g.order()): if i not in curset: #print "processing i = " + str(i) in_p = 1; for j in range(0, g.order()): #print "processing j = " + str(j) if j in curset: ein = get_edge_index(g, i, j) if (ein >= 0): #print "edge(" + str(i) + "," + str(j) + ") = x[" + str(ein) + "]" in_p = in_p*(x[ein] - 1); #end if #end for #print str(factor(in_p)) if in_p != 1: in_s = in_s + in_p; #print str(in_s) #end if #print str(in_s) #end if #end for if in_s != 0: tp = tp*in_s; #print str(tp) #break; #end if #break; #end for I.append(tp); #print "|I| = " + str(len(I)) myI = ideal(I); print "Beginning grobner basis calculation..." B = myI.groebner_basis(); #print "|B| = " + str(len(B)) for i in range(0, len(B)): #print "factoring B[" + str(i) + "]" print str(factor(B[i])) #end for #print "Beginning variety calculation..." #V = myI.variety() #V #print "Finished variety calculation..."
Graph has 4 vertices and 6 edges Display variable -> edge dictionary x[0] = (0,1) x[1] = (0,2) x[2] = (0,3) x[3] = (1,2) x[4] = (1,3) x[5] = (2,3) Beginning grobner basis calculation... x0 * (x0 - 1) (x4 - 1) * (x3 - 1) * (x2 - 1) * (x1 - 1) * (x0 - 1) (x5 - 1) * (x3 - 1) * (x2 - 1) * (x1 - 1) * (x0 - 1) (x5 - 1) * (x4 - 1) * (x2 - 1) * (x1 - 1) * (x0 - 1) (x5 - 1) * (x4 - 1) * (x3 - 1) * (x1 - 1) * (x0 - 1) (x5 - 1) * (x4 - 1) * (x3 - 1) * (x2 - 1) * (x0 - 1) x1 * (x1 - 1) (x5 - 1) * (x4 - 1) * (x3 - 1) * (x2 - 1) * (x1 - 1) x2 * (x2 - 1) x3 * (x3 - 1) x4 * (x4 - 1) x5 * (x5 - 1)
#P = PolynomialRing(QQ, 12, 'x', order="lex") over F2 # x = P.gens() # g2 = (x[1] - 1)*(x[2] - 1)*(x[3]-1)*(x[7]-1)*(x[8]-1) # g4 = (x[4] - 1)*(x[8] - 1)*(x[9]-1) # f = x[4]*x[9]*g2 - x[1]*x[2]*x[3]*x[7]*g4 # f