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

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 array M containing 0's and 1's. The entry Mi]Ll equals 1 if i,je 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 {? is equivalent to an edge i), and that no vertex can ever be adjacent to itself. This means that for all i,je {0,1, ,n-1), M i] MUlil, and that Mi o 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 thern does a very large amount of printing! ? def has isolated (M) n len(M) # n is the number of vertices of the graph found isolated False for i in range(n): # i " ?, 1, n-1 , count 0 for j in range (n): # j-0, 1, n-1 , count count MEi] [j] if count = 0: True found-isolated break if found isolated: 13 14 15 for k in range (2 *n): print ('Degree too small')

Explanation / Answer

(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.