 CoCalc Public FilesHandouts / s05-inclass.sagews
Author: Masrik Dahir
Views : 41
Compute Environment: Ubuntu 20.04 (Default)
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