Based on what we discussed in class, write Python code for the following algorithms, representing graphs as adjacency matrices. You may use the code in my graphs.py file. In particular, the spheres function will be very useful, as well as graph constructors for testing your code.

Exercise 0: Using the graph constructors in graphs.py, construct the following adjacency matrices.

• C5 - a cycle graph of order 5
• C10 - a cycle graph of order 5
• DC4 - a directed cycle graph of order 4
• K5 - a complete graph of order 5
• E3 - an empty graph on 3 vertices
• G1 - the sum (union) of K5 with E3
• G2 - the sum of C5 with DC4
• G3 - the sum of DC4 with DC4, with a directed edge from 0 to 4

Exercise 1: Write a function undirected(A) that returns the undirected graph associated with A. Do not modify A, but build a new matrix. Test this on DC4 and C5.

Exercise 2: Write a function component(A,i) that returns the connected component of vertex i (as a Python set) for a directed or undirected graph A. Test this on (G1,0), (G3,0) and (G3, 7).

Exercise 3: Write a function components(A) that returns all connected components of A (directed or undirected), as a list of sets. Test this on G1, G2 and G3.

Exercise 4: Write a function is_connected(A) that returns True if A is connected and False otherwise. Test this on G1, G2 and G3.

Exercise 5: Write a function distance(A,i,j) that returns the distance from vertex i to vertex j. If the distance is infinite, return -1. Test this on (C10,0,6), (G3, 1, 5) and (G3, 5, 1).

Exercise 6: Write a function diameter(A) that returns the diameter of A (directed or undirected). If the diameter is infinite, return -1. Test this on C5, C10, DC4, K5, G1 and G3.

Exercise 7: Write a function randtree(n) that returns the adjacency matrix of a random tree on n vertices. Here we generate a tree randomly by starting with 1 vertex, and at each stage add an new vertex and an edge from the new vertex to one of the previous vertices, chosen at random. To choose a vertex at random, use the function randint(a,b), which returns a random integer between a and b (inclusive). This function is in the random module, and you first need to input from random import randint to call it. Test this for n=5 a few times.

Exercise 8: Recall there are 3 possibilities for a tree of order 5 up to isomorphism. One can distinguish among these trees by looking at diameter (or other things, such as maximum degree, or number of leaves). Generate 100 random trees on 5 vertices, and count the number of times each type of tree occurs. Use this to estimate the probability for generating each type of tree. With these probabilities, estimate the expected diameter.

Exercise 9: For each of the following values of n, generate 100 random trees of order n, and compute the average diameter: n = 5, 10, 20, 50, 100.