3. 14 marks Graph algorithm Let G V.E) be a graph, and let V 0, be the vertices

Question

3. 14 marks Graph algorithm Let G V.E) be a graph, and let V 0, 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 MMil equals 1 if i.j E 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 { Jis equivalent to an edge {3 i), and that no vertex can ever be adjacent to itself. This means that for all i,j E 0,1,Mb M[ ], and that M[illi] = 0 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 a very large amount of printing! def has-isolated (H): 2 n- len(M) # n s the number of vertices of the graph found isolated False for i in range (n) : # i 0, 1, n-1 , countO for j in range (n) : if count 0: # j . 0, 1, n-1 , count count Mi] j] found isolated True break if found isolated: 13 14 15 for k in range (2 **) print ('Degree too small') (a) [3 marks] Prove that the worst-case running time of this algorithm ?s ?(2") (b) [3 marks] Prove that the best-case running time of this algorit Inn is ?(n2) (c) mark] Let n e N. Find a formula for t umber of adjacency matrices of size n-by-n that represent valid graphs. For example, a graph G (V, E) with V 4 has 64 possible adjaceney 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. (Eve 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 E N. Prove that the nuber of nby-n adjacency matrices that represent a graph with at least one ?solated vertex is at most n-2(n-1)(n-2)/2 (f) 3 marks Finally, let 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) The worst case happens when the last vertex is isolated.

In this case, the for loops runs  ?(n2 ) as these are nested .Now at last iteration count will be zero so, the loop will break and as found_isolated will be true so the last loop will run from 1 to 2n ( as (2 ** n) in python means 2n). Therefore it will take time  ?(2n ).

Therefore  ?(n2 + 2n ) = ?(2n ).

(b) Best case occurs when none of the vertices are isolated.In this, the nested loop will never break and will run for ?(n2 ). As the variable found_isolated will be false so, the last loop will never run.

So, the best case running time will be ?(n2 ).

(c) This is nothing but the number of undirected labeled graphs with n vertices which is given by the formula 2nC2

or 2n(n-1)/2 .

(d) The proof of this formula is that the number of edges in a complete graph/maximum number of edges with n vertices is 2n(n-1)/2   .so, there arises two cases for the number of valid graphs i.e either there can be an edge between two vertices or there cannot be in the complete graph.This gives rise to the formula 2n(n-1)/2

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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