3+4

#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()

#the cycle on 4 vertices IS bipartite

#call it c4

c4 = graphs.CycleGraph(4)

c4.show()

c4.is_bipartite()

#PROBLEM 5. 
#Now load that file. Run: load(‘graphs.sage’).

load("graphs.sage")

my_graphs

#let's see what graphs are in my_graphs

for g in my_graphs:
    print(g.name())
    g.show()

#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)

#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)

#PROBLEM 10. 
#How can we find the complement of a graph in Sage?

#let's find the complement of pete

pete.show()

pete.complement()

#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()

#PROBLEM 3. 
#How can we find the edges of a given graph G?

pete.edges()

#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)

#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

g = pete
g.show()

g == pete

#we'll write a test for whether 2 graphs are identical

[1,2,3] == [3,2,1]

#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)

is_identical(bull,milkbone)    

#PROBLEM 15. 
#How can we find the degrees of a graph?    

pete.degree()

milkbone.degree()

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])

min([4,5,6,2,8])

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)

max_degree(milkbone)

max_degree(bull)

#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)

min_degree(pete)

min_degree(bull)