WorksheetsPythonDS
Total questions: 13
Worksheet time: 7mins
Which of the following statements for a simple graph is correct?
a) Every path is a trail
b) Every trail is a path
c) Every trail is a path as well as every path is a trail
d) Path and trail have no relation
2. In the given graph identify the cut vertices
a) B and E
b) C and D
c) A and E
d) C and B
For the given graph(G), which of the following statements is true?
a) G is a complete graph
b) G is not a connected graph
c) The vertex connectivity of the graph is 2
d) The edge connectivity of the graph is 1
What is the number of edges present in a complete graph having n vertices?
a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient
How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ?
(A) n(n-l)/2
(B) 2^n
(C) n!
(D) 2^(n(n-1)/2)
20. The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is ____________
A. O(V)
B. O(E^2)
C. O(E)
D. O(V^2)
Which of the following ways can be used to represent a graph?
A. Adjacency List and Adjacency Matrix
B. Incidence Matrix
C. Adjacency List, Adjacency Matrix as well as Incidence Matrix
D. None of the mentioned
for which of the following combinations of the degrees of vertices would the connected graph be eulerian?
A. 1,2,3
B. 2,3,4
C. 2,4,5
D. 1,3,5
A complete graph can have ..............
a.n^2 spanning trees
b. n^(n-2) spanning trees
c.n^(n+1) spanning trees
d.n^n spanning trees
Graph traversal is different from a tree traversal, because:
a.trees are not connected
b.graphs may have loops
c.trees have root
d.None of these
The spanning tree of connected graph with 10 vertices contains ..............
a.9 edges
b.11 edges
c.10 edges
d. 9 vertices
If locality is a concern, you can use ................ to traverse the graph.
a.Breadth First Search
b.Depth First Search
c.Either BFS or DFS
d.None of these
Which of the following algorithms solves the all-pair shortest path problem?
a.Floyd's algorithm
b.Prim's algorithm
c.Dijkstra's algorithm
d.Warshall's algorithm
