Open with one click!
3+4
7
#MANY/Most of what we'll code are built-in to Sage #in particular, testing whether a graph is bipartite is built-in pete = graphs.PetersenGraph() pete.show()
#pete has a 5-cycle. it is NOT bipartite pete.is_bipartite()
False
#the cycle on 4 vertices IS bipartite #call it c4 c4 = graphs.CycleGraph(4)
c4.show()
c4.is_bipartite()
True
#PROBLEM 5. #Now load that file. Run: load(‘graphs.sage’). load("graphs.sage")
my_graphs
[Complete graph: Graph on 3 vertices, Complete graph: Graph on 4 vertices, Complete bipartite graph of order 2+3: Graph on 5 vertices, Path graph: Graph on 5 vertices, Petersen graph: Graph on 10 vertices, Icosahedron: Graph on 12 vertices, Dodecahedron: Graph on 20 vertices, Tetrahedron: Graph on 4 vertices, Octahedron: Graph on 6 vertices, Graph on 5 vertices, Bucky Ball: Graph on 60 vertices, Graph on 6 vertices, Graph on 5 vertices, Cycle graph: Graph on 5 vertices]
#let's see what graphs are in my_graphs for g in my_graphs: print(g.name()) g.show()
Complete graph
Complete graph
Complete bipartite graph of order 2+3
Path graph
Petersen graph
Icosahedron
Dodecahedron
Tetrahedron
Octahedron Octahedron
Bucky Ball
Cycle graph
Bucky Ball
Cycle graph
Petersen graph
Icosahedron
Dodecahedron
Tetrahedron
#NOTE: added new code to graphs.sage #need to re-load in order to access this code load("graphs.sage")
#see if it loaded is_complete(pete)
False
#PROBLEM 7. #How can we test is a graph is complete in Sage? #is complkete is NOT built-in#PROBLEM 9. How can we test if two graphs are isomorphic in Sage?
#PROBLEM 9. #How can we test if two graphs are isomorphic in Sage? bull.show()
#bull and milkbone are NOT isomorphic (milkbome is a tree, but bull has a cycle milkbone.is_isomorphic(bull)
False
#PROBLEM 10. #How can we find the complement of a graph in Sage? #let's find the complement of pete pete.show()
pete.complement()
complement(Petersen graph): Graph on 10 vertices
#we need to give this graph a name if we're going to use it pete_complement = pete.complement()
pete_complement.show()
#PROBLEM 11. #How can we produce an induced subgraph with a particular subset V #lets find the induced subgraph of pete with vertex set [0,1,5,6] pete_sub = pete.subgraph([0,1,5,6])
pete_sub.show()
#PROBLEM 12. #How can we find the vertices of a given graph G? pete.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
#PROBLEM 3. #How can we find the edges of a given graph G? pete.edges()
[(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None), (3, 4, None), (3, 8, None), (4, 9, None), (5, 7, None), (5, 8, None), (6, 8, None), (6, 9, None), (7, 9, None)]
#recall: the 3rd spot in those tuples is for an edge-weight - we'll need that for Dijkstra's algorithm #is we don't want the edge labels/weights, use labels=False pete.edges(labels=False)
[(0, 1), (0, 4), (0, 5), (1, 2), (1, 6), (2, 3), (2, 7), (3, 4), (3, 8), (4, 9), (5, 7), (5, 8), (6, 8), (6, 9), (7, 9)]
#PROBLEM 14. #How can we test if two graphs are identical? #the bull and the milkbone are not isomorphic (they different numbers of vertices) so they can't be identical #for 2 graphs to be identocal they must have the same vertex set AND same edge set #what does the following comparison mean? pete == pete
True
g = pete g.show()
g == pete
True
#we'll write a test for whether 2 graphs are identical [1,2,3] == [3,2,1]
False
#different lists! (remember how the data structure works - lists are things where order matters def is_identical(g,h): Vg = g.vertices() Vh = h.vertices() if len(Vh) != len(Vg): return False #if these lists are the same lenght, just check is every v in Vg is also in Vh #if there's a single vertex that's different return False for v in Vg: if v not in Vh: return False #so now we have same vertex sets. are the edge sets the same? Eg = g.edges(labels=False) Eh = h.edges(labels=False) if len(Eg) != len(Eh): return False #so now we just if every single edge (v,w) in Eg is also in Eh for (v,w) in Eg: if not ((v,w) in Eh or (w,v) in Eh): return False #all tests passed. return True! return True
#is pete identical to itself? is_identical(pete,pete)
True
is_identical(bull,milkbone)
False
#PROBLEM 15. #How can we find the degrees of a graph? pete.degree()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
milkbone.degree()
[1, 3, 3, 1, 1, 1]
milkbone.show()
#PROBLEM 16. #How can we find the maximum degree? #IDEA: find the degrees, return the max #max of a list is built-in max([3,4,5,7,49,1])
49
min([4,5,6,2,8])
2
def max_degree(g): degrees = g.degree() #gives a list of all the degrees of every vertex return max(degrees)
#for pete the max is 3 max_degree(pete)
3
max_degree(milkbone)
3
max_degree(bull)
3
#PROBLEM 17. #How can we find the minimum degree? def min_degree(g): degrees = g.degree() #gives a list of all the degrees of every vertex return min(degrees)
min_degree(milkbone)
1
min_degree(pete)
3
min_degree(bull)
1