Graph Coloring: Consider a graph with 5 nodes corresponding to variables numbere
ID: 3862284 • Letter: G
Question
Graph Coloring: Consider a graph with 5 nodes corresponding to variables numbered
1, 2, 3, 4, 5 and edges between the following nodes: 1-2, 2-3, 3-4, 4-5, 1-5, 1-4, 2-4, 3-5.
Each variable can take three values: A, B, or C.
Two variables corresponding to node which are connected by an edge must have different values.
a. What is the domain for each variable?
b. Draw the constraint graph.
c. Solve this problem by hand by using the “minimum remaining value” heuristic to choose the next node to expand in the search tree. Break ties using the “degree heuristic”. Use the “least-constraining-value” heuristic to pick a value. Any remaining ties can be broken arbitrarily. At each step explain your reasoning.
d. Assume that node 1 has value C and node 5 has value B. Apply forward checking to reduce the domains of (some) of the other variables. Explain your answer.
e. Use arc-consistency (repeatedly) to further reduce the domains of the remaining variables. Explain your answer.
Explanation / Answer
a. What is the domain for each variable?
D=[A,B,C].
c. Solve this problem by hand by using the “minimum remaining value” heuristic to choose
the next node to expand in the search tree. Break ties using the “degree heuristic”.
Use the “least-constraining-value” heuristic to pick a value. Any remaining ties can be broken arbitrarily.
At each step explain your reasoning
Solution : - 4-A, 1-B, 2-C, 3-B, 5-C. There are many solutions because many ties need to be broken arbitrarily
d. Assume that node 1 has value C and node 5 has value B. Apply forward checking to reduce the domains
of (some) of the other variables. Explain your answer.
Solution : - : D2=[A,B], D3=[A,C], D4=[A]
e.Use arc-consistency (repeatedly) to further reduce the domains of the
remaining variables. Explain your answer.
D3=[C], D2=[B].
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.