CODEWITHSUNDEEP
graphgraph-algorithm
affanBajwa
affanBajwa

Reputation: 168

Graph coloring with only 3 colors example

Today in a class Quiz this question was given in quiz. Although i solved it with 4-colors not a big deal but my teacher told me that it can be solved with three colors. I have spent several hours finding solution using three colors even on internet i have searched a lot. Can any one help me in it.enter image description here

Note:This question is from book Introduction to design and analysis of algorithm by Anany Levitin Third edition Chapter 1 Fundamental Data Structures Page:25

Upvotes: 0

Views: 448

Answers (1)

Sufian Latif
Sufian Latif

Reputation: 13356

You can create a graph from the map, where the nodes will represent the regions, and there will be an edge between two nodes if their corresponding regions share a border in the map. After the transformation, the graph would look like this:

    b
   /|\
  / | \
 a--c--d
 | / \ |
 |/   \|
 e-----f

Then you can apply graph-coloring algorithms on the graph.

And no, this graph cannot ne colored using three colors only. You must use a fourth color to color it completely.

Upvotes: 1

Related Questions