Data Structures & Algorithms Multiple Choice Questions on “Properties of Bipartite Graphs”.
1. Which type of graph has no odd cycle in it?
a) Bipartite
b) Histogram
c) Cartesian
d) Pie
Answer: a
Clarification: The graph is known as Bipartite if the graph does not contain any odd length cycle in it. Odd length cycle means a cycle with the odd number of vertices in it.
2. What type of graph has chromatic number less than or equal to 2?
a) Histogram
b) Bipartite
c) Cartesian
d) Tree
Answer: b
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is chromatic number.
3. Which of the following is the correct type of spectrum of the bipartite graph? Answer: a 4. Which of the following is not a property of the bipartite graph? Answer: d 5. Which one of the following is the chromatic number of bipartite graph? Answer: a 6. Which graph has a size of minimum vertex cover equal to maximum matching? Answer: d 7. Which theorem gives the relation between the minimum vertex cover and maximum matching? Answer: a 8. Which of the following is not a property of perfect graph? Answer: d 9. Which of the following graphs don’t have chromatin number less than or equal to 2? Answer: d 10. Which of the following has maximum clique size 2? Answer: a 11. What is the chromatic number of compliment of line graph of bipartite graph? Answer: c 12. What is the clique size of the line graph of bipartite graph? Answer: c 13. It is possible to have a negative chromatic number of bipartite graph. Answer: b 14. Every Perfect graph has forbidden graph characterization. Answer: a 15. Which structure can be modelled by using Bipartite graph? Answer: a
a) Symmetric
b) Anti – Symmetric
c) Circular
d) Exponential
Clarification: The spectrum of the bipartite graph is symmetric in nature. The spectrum is the property of graph that are related to polynomial, Eigen values, Eigen vectors of the matrix related to graph.
a) No Odd Cycle
b) Symmetric spectrum
c) Chromatic Number Is Less Than or Equal to 2
d) Asymmetric spectrum
Clarification: A graph is known to be bipartite if it has odd length cycle number. It also has symmetric spectrum and the bipartite graph contains the total chromatic number less than or equal to 2.
a) 1
b) 4
c) 3
d) 5
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number.
a) Cartesian
b) Tree
c) Heap
d) Bipartite
Clarification: The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. Bipartite graph has a size of minimum vertex cover equal to maximum matching.
a) Konig’s Theorem
b) Kirchhoff’s Theorem
c) Kuratowski’s Theorem
d) Kelmans Theorem
Clarification: The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. Bipartite graph has a size of minimum vertex cover equal to maximum matching.
a) Compliment of Line Graph of Bipartite Graph
b) Compliment of Bipartite Graph
c) Line Graph of Bipartite Graph
d) Line Graph
Clarification: TThe Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is known as a perfect graph in graph theory. Normal line graph is not a perfect graph whereas line perfect graph is a graph whose line graph is a perfect graph.
a) Compliment of Line Graph of Bipartite Graph
b) Compliment of Bipartite Graph
c) Line Graph of Bipartite Graph
d) Wheel graph
Clarification: The perfect bipartite graph has chromatic number 2. Also, the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is known as perfect graph in graph theory. Wheel graph Wn has chromatin number 3 if n is odd and 4 if n is even.
a) Perfect graph
b) Tree
c) Histogram
d) Cartesian
Clarification: The perfect bipartite graph has clique size 2. Also, the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.
a) 0
b) 1
c) 2
d) 3
Clarification: The perfect bipartite graph has chromatic number 2. So the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph has chromatic number 2.
a) 0
b) 1
c) 2
d) 3
Clarification: The perfect bipartite graph has clique size 2. So the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.
a) True
b) False
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number. But the chromatic number cannot be negative.
a) True
b) False
Clarification: Berge theorem proves the forbidden graph characterization of every perfect graphs. Because of that reason every bipartite graph is perfect graph.
a) Hypergraph
b) Perfect Graph
c) Hetero Graph
d) Directed Graph
Clarification: A combinatorial structure such as Hypergraph can be made using the bipartite graphs. A hypergraph in graph theory is a type of graph in which edge can join any number of vertices.