Consider Constraint Satisfaction Problem for Coloring following map (Attach via Picture at the end of this question) (i.e like color graphing problem, see : http://db.cs.duke.edu/courses/spring01/cps271/LECTURES/cspII.pdf)
we want to color this map with 1 color, (the neighbors city should not get the same color), with this assumption, the Constraint Graph for this problem for K= 1 and K=3 has K-Consistency Property.
Why this example is True? why consistency is not hold for K=2? and why is hold for K=1 and K=3?
thanks to all.
I'm sorry, but I didn't understand your question. Some indications are missing here.
You say that the picture you attached depicts a graph. How is that? Are the nodes the intersections between the line and circular segments? What are the cities? And how do you want to color the map with 1 color with neighboring cities having a different color? What do you exactly want to color?
When you say K=1 do you mean that you are using 1 colour? In that case you cannot colour this, can you?
Ok, so I thought. So A, B and C do represent the cities. Your constraint graph is a K3 (i.e. a complete graph of three nodes). If you want to color it, you have no choice but to use three colors. You cannot color it with k
Hi Huimen,
so, after thinking again about your problem, I have a new answer for you.
You say to want to color your graph with one color, so every variable's domain will only contain one element which is that single color. The unary constraints would be that every node will be assigned a color, so your CSP is 1-consistent and 1-satisfiable.
Your CSP is not 2-consistent because there exist at least one 1-compound-label that cannot be extended to a two-compound-label that satisfies the constraint that every two neighbor cities should be assigned different colors.
However, your CSP is 3-consistent. Indeed, you need to be able to extend any two-compound-label for your CSP to be 3-consistent. Since there are none, the statement is always true, so your CSP is 3-consistent.
I hope this helped,
Best regards,
Imène.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering