3. 14 marks] Graph algorithm. Let G (V, E) be a graph, and let V 0,1,n-1 be the

Question

3. 14 marks] Graph algorithm. Let G (V, E) be a graph, and let V 0,1,n-1 be the vertices of the graph. One common way to represent graphs in a computer program is with an adjacency matrix a two-dimensional n-by-n array2 M containing 0's and 1's. The entry Miil equalsf i.j E, and 0 otherwise; that is, the entries of the adjacency matrix represent the edges of the graph. Keep in mind that graphs in our course are symmetric (an edge i,j is equivalent to an edge j, i), and that no vertex can ever be adjacent to itself. This means that for all i.je {0.1 n-1). M [i][j-= M, and that Ma0 The following algorithm takes as input an adjacency matrix M and determines whether the graph contains at least one isolated vertex, which is a vertex that has no neighbours. If such a vertex is found, it then does a very large amount of printing! a def has isolated (M): 2 n-len() # n is the number of vertices of the graph found isolatedFalse for i in range (n) : # t -0, 1, n-1 , count0 for j in range (n) : #1-0, 1, n-1 , count count M[i] [jl if count0 found isolated True break if found isolated: 14 for k in range (2**n) print ( 'Degree too small') (a) [3 marks] Prove that the worst-case running time of this algorithm is ?(2n) (b) 3 marks] Prove that the best-case running time of this algorithm is e(n2) (c mark] Let n e N. Find a formula for the number of adjacency matrices of size n-by-n that represent valid graphs. For example, a graph G (KE) with V-4 has 64 possible adjacency matrices Note: a graph with the single edge (1, 2) is considered different from a graph with the single edge (2,3), and should be counted separately. (Even though these graphs have the same "shape, the vertices that are adjacent to each other are different for the two graphs.) (d) [2 marks] Prove the formula that you derived in Part (c) (e) 2 marks Let n N. Prove that the nmbr of -by-n adjacency matrices that represent a graph with at least one isolated vertex is at most n 2)22 (f) [3 marks] Finally, et AC(n) be the average-case runtime of the above algorithm, where the set of inputs is simply all valid adjacency matrices (same as what you counted in part (c)) Prove that AC(n) e ?(n2)

Explanation / Answer

a)

procedure M(i, j):
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w ? i.adjacentVertex(v, e)
if vertex w is unexplored then
label e as a discovered edge
recursively call M(i, j)
else
label e as a back edge

b)

procedure M(i, j):
create a queue Q
enqueue v onto Q
mark v
while Q is not empty:
t ? Q.dequeue()
if t is what we are looking for:
return t
for all edges e in i.adjacentEdges(t) do
o ? i.adjacentVertex(t, e)
if o is not marked:
mark o
enqueue o onto Q
return null

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.