Data Structure

Graph

Question 1
Marks : +2 | -2
Pass Ratio : 100%
The given Graph is regular.
True
False
Explanation:
In a regular graph, degrees of all the vertices are equal. In the given graph the degree of every vertex is 3.
Question 2
Marks : +2 | -2
Pass Ratio : 100%
In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
True
False
Explanation:
The sum of the degrees of the vertices is equal to twice the number of edges.
Question 3
Marks : +2 | -2
Pass Ratio : 100%
What is the maximum number of edges in a bipartite graph having 10 vertices?
24
21
25
16
Explanation:
Let one set have n vertices another set would contain 10-n vertices.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
For the given graph(G), which of the following statements is true?
G is a complete graph
G is not a connected graph
The vertex connectivity of the graph is 2
The edge connectivity of the graph is 1
Explanation:
After removing vertices B and C, the graph becomes disconnected.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
What is the number of edges present in a complete graph having n vertices?
(n*(n+1))/2
(n*(n-1))/2
n
Information given is insufficient
Explanation:
Number of ways in which every vertex can be connected to each other is nC2.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
15
3
1
11
Explanation:
By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
Which of the following properties does a simple graph not hold?
Must be connected
Must be unweighted
Must have no loops or multiple edges
Must have no multiple edges
Explanation:
A simple graph maybe connected or disconnected.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G\'(Complement of G) is ___________
(n*n-n-2*m)/2
(n*n+n+2*m)/2
(n*n-n-2*m)/2
(n*n-n+2*m)/2
Explanation:
The union of G and G’ would be a complete graph so, the number of edges in G’= number of edges in the complete form of G(nC2)-edges in G(m).
Question 9
Marks : +2 | -2
Pass Ratio : 100%
Which of the following statements for a simple graph is correct?
Every path is a trail
Every trail is a path
Every trail is a path as well as every path is a trail
Path and trail have no relation
Explanation:
In a walk if the vertices are distinct it is called a path, whereas if the edges are distinct it is called a trail.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
In the given graph identify the cut vertices.
B and E
C and D
A and E
C and B
Explanation:
After removing either B or C, the graph becomes disconnected.