This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Graph Coloring – Edge Coloring”.
1. Which of the following refers to the minimum number of colors, with which the edges of the graph can be colored?
a) Independence number
b) Vertex chromatic number
c) Edge chromatic number
d) Domination number
View Answer
Explanation: The idea of edge coloring is to color all the edges of the graph in such a way that, all the incident edges receive distinct colors. The edge chromatic number is the minimum number of colors required for proper edge coloring.
2. In the edge coloring of a graph, which edges should be colored with different colors?
a) All adjacent edges
b) Opposite pair edges
c) Only 2 edges
d) Only 2 adjacent edges
View Answer
Explanation: An edge coloring of a graph is to color the edges of the graph in such a way that any two adjacent edges should receive different colors. There are several different types of graph coloring, one of them is edge coloring.
3. What is the edge chromatic number for the graph given below?
a) 2
b) 3
c) 4
d) 5
View Answer
Explanation: Edge chromatic number is the minimum number of colors used to color all the edges of the graph distinctly. The edge chromatic number is also equal to the maximum degree of the graph. The degree of node E is 4, which means 4 distinct edges are incident to vertex E. All these edges need to be colored distinctly. Hence, the edge chromatic number of the graph is 4.
4. Consider the following pseudocode for the edge coloring problem of a graph. Which of the following best suits the blank?
Start traversing the graph using BFS traversal Pick up any vertex from the graph __________________________ Traverse one its edges Repeat until all the edges of the graph are covered
a) Assign different colors to all the adjacent vertices
b) Delete all the connected edges
c) Assign a color to only one of its edge
d) Assign different colors to the connected edges, and mark those edges as colored
View Answer
Explanation: To find the edge chromatic number of the graph, start traversing the graph using BFS traversal. Pick up any vertex from the graph, and assign different colors to all the connected edges, and mark those edges as colored. Then traverse one of its edges and repeat until all the edges of the graph are covered.
5. The number of colors required to color the edges of a simple graph is equal to the maximum degree of a graph.
a) True
b) False
View Answer
Explanation: The maximum number of edges incident to any single vertex is the maximum degree of a graph. All these edges of the graph should be colored with different colors from each other. Hence, for any graph, the edge chromatic number is K, where K is the maximum degree of the graph.
6. Which among the following is the NP-complete problem?
a) Graph Coloring
b) Finding largest element in an array
c) Finding smallest element in an array
d) Finding power set
View Answer
Explanation: NP-complete problems are the problem for which the polynomial-time algorithm hasn’t been discovered yet. Graph coloring problem is NP-complete problem, but there are some approximation algorithms to solve graph coloring problem.
7. An even length cyclic graph has the edge chromatic number of 3.
a) True
b) False
View Answer
Explanation: In cyclic graph, coloring can be done in such a way that, all the edges can be colored by 2 alternate colors around the cycle. Hence, the edge chromatic number of an even length cyclic graph is 2, while the odd length cyclic graph has 3 as its edge chromatic number.
8. Which of the following is an application of the graph coloring problem?
a) Dynamic memory allocation
b) Scheduling exam timetable
c) Designing a network
d) Finding cycle in a graph
View Answer
Explanation: The graph coloring approach can be used to schedule an exam timetable. There are different students enrolled in different subjects. The exams should be scheduled in such a way that, no two exams should be scheduled together for a common student. Hence, in this case, the minimum number of exam time slots is the chromatic number of the graph.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Computer Science Books
- Practice Computer Science MCQs
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
- Check Programming Books
