Data Structure Questions and Answers – Graph

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Graph”.

1. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
A) True
B) False

Explanation: The number of edges is equal to the sum of the degrees of the vertices.

2. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
A) 15
B) 3
C) 1
D) 11

Explanation: By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.

3. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is ___________
A) (n*n-n-2*m)/2
B) (n*n+n+2*m)/2
C) (n*n-n-2*m)/2
D) (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).

4. Which of the following properties does a simple graph not hold?
A) Must be connected

B) Must be unweighted
C) Must have no loops or multiple edges
D) Must have no multiple edges

Explanation: A simple graph may or may not be connected.

5. What is the maximum number of edges in a bipartite graph having 10 vertices?
A) 24
B) 21
C) 25
D) 16

Explanation:

Let’s say each set has n vertices. A different set will have 10-n vertices.
The total number of edges would be n*(10-n), and the answer would be obtained by differentiating with respect to n.

6. Which of the following is true?
A) A graph may contain no edges and many vertices
B) A graph may contain many edges and no vertices
C) A graph may contain no edges and no vertices
D) A graph may contain no vertices and many edges

Explanation: There must be at least one vertex in a graph.

7. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?
A) v=e
B) v = e+1
C) v + 1 = e
D) v = e-1

Explanation: The equation holds for any connected graph with no cycles.

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

Explanation: If all of a graph’s vertices are even, or only two of them are odd, the graph is eulerian.

9. A graph with all vertices having equal degree is known as a __________
A) Multi Graph
B) Regular Graph
C) Simple Graph
D) Complete Graph

Explanation: Standard graphs are defined by the given statement.

10. 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) No way to represent

Explanation: A graph is represented using the Adjacency Matrix, Adjacency List, and Incidence Matrix.

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

Explanation: A path is defined as a walk with distinct vertices, while a trail is defined as a walk with distinct edges.

12. In the given graph identify the cut vertices.

data-structure-questions-answers-graph-q2

A) B and E
B) C and D
C) A and E
D) C and B

Explanation: The graph becomes disconnected after eliminating either B or C.

13. For the given graph(G), which of the following statements is true?

data-structure-questions-answers-graph-q3

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

Explanation: After removing vertices B and C, the graph becomes disconnected.

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

Explanation: nC2 is the number of ways each vertex can be bound to the others.

15. The given Graph is regular.

data-structure-questions-answers-graph-q5

A) True
B) False

Explanation: The degrees of all the vertices in a normal graph are equal. Per vertex in the graph has a degree of three.

The set of ordered pairs (x, y) in which f(x) = y is the graph of a function f. These pairs are Cartesian coordinates of points in two-dimensional space and thus form a subset of this plane in the general case where x and f(x) are real numbers. The graph generally refers to the set of ordered triples (x, y, z) where f(x, y) = z, rather than the pairs ((x, y), z) as in the description above, in the case of functions of two variables, that is functions whose domain consists of pairs (x, y). This set is a surface for a continuous real-valued function of two real variables; it is a subset of three-dimensional space.

Leave a Reply

Your email address will not be published. Required fields are marked *