#All positive edges in columns have a 1 and -1 entry. Standardize makes any #positive edge column have the 1 come before the -1 when reading the column #top to bottom. All negative edges in columns have two 1 entries or two -1 entries. #Standardize makes any negative edge column have two 1s. A negative loops has #one 1 or -1 entry in its edge column. Standardize makes all negative loop #columns have one 1. Standardizing our edges into one convention makes finding a #positive edge to delete-contract more efficient. def standardize(G): G_rows=G.nrows() G_cols=G.ncols() for j in range(0,G_cols): for i in range(0,G_rows): if G[i,j] == 1: break if G[i,j] == -1: G.add_multiple_of_column(j,j,-2) break return G #If there is a mutiedge in the Peterson graph, meaning a column is repeated, then #delete the column and return a new incidence matrix. def check(Gin): G=standardize(Gin) # G_cols=G.ncols() G_rows=G.nrows() l=G.columns() for i in range(0,G_cols-1): for j in range(i+1,G_cols): if G.column(G_cols-1-i)== G.column(G_cols-1-j): l.pop(G_cols-1-i) break B=matrix(l) C=B.transpose() return C #Returns an ordered pair of the incidence matrix of the graph with an edge #deleted and the incidence matrix of the graph with an edge contracted. def DC(G): rows=G.nrows() cols=G.ncols() #If a single edge, return an empty graph with the same number of vertices for #the graph with the edge deleted. Return an empty graph with one #less vertex for the graph with the edge contracted. if cols == 1: C=matrix(QQ,rows,1,range(0)) H=matrix(QQ,rows-1,1,range(0)) return (C,H) #Else, find the first positive edge in the matrix when reading the matrix #from left to right. Delete and contract this edge returning new incidence matrices. else: j=0 #Increment through the columsn looking for a positive edge while j