M-कलरिंग समस्या

इस समस्या में, एक अनडायरेक्टेड ग्राफ दिया गया है। m रंग भी प्रदान किए गए हैं। समस्या यह ढूंढना है कि क्या नोड्स को m अलग-अलग रंगों के साथ असाइन करना संभव है, जैसे कि ग्राफ के कोई दो आसन्न वर्टेक्स एक ही रंग के न हों। यदि समाधान मौजूद है, तो प्रदर्शित करें कि कौन सा रंग किस वर्टेक्स पर असाइन किया गया है।

वर्टेक्स 0 से शुरू करके, हम एक-एक करके अलग-अलग नोड्स को रंग असाइन करने का प्रयास करेंगे। लेकिन असाइन करने से पहले, हमें जांचना होगा कि रंग सुरक्षित है या नहीं। एक रंग सुरक्षित नहीं है यदि आसन्न वर्टेक्स में वही रंग है।

इनपुट और आउटपुट

इनपुट: एक ग्राफ G(V, E) का एडजेसेंसी मैट्रिक्स और एक पूर्णांक m, जो इंगित करता है कि अधिकतम कितने रंगों का उपयोग किया जा सकता है।  मान लें अधिकतम रंग m = 3। आउटपुट: यह एल्गोरिदम वापस करेगा कि किस नोड को किस रंग के साथ असाइन किया जाएगा। यदि समाधान संभव नहीं है, तो यह false वापस करेगा। इस इनपुट के लिए असाइन किए गए रंग हैं: Node 0 -> color 1 Node 1 -> color 2 Node 2 -> color 3 Node 3 -> color 2 

एल्गोरिदम

isValid(vertex, colorList, col)

इनपुट - वर्टेक्स, जांचने के लिए colorList, और रंग, जिसे असाइन करने का प्रयास कर रहे हैं

आउटपुट - True यदि रंग असाइन करना वैध है, अन्यथा false

Begin 
  for all vertices v of the graph, do 
    if there is an edge between v and i, and col = colorList[i], then 
      return false 
  done 
  return true 
End

graphColoring(colors, colorList, vertex)

इनपुट - संभावित रंग, वह सूची जिसके लिए वर्टेक्स किस रंग से रंगे गए हैं, और शुरुआती वर्टेक्स

आउटपुट - True, जब रंग असाइन किए गए हों, अन्यथा false

Begin 
  if all vertices are checked, then 
    return true 
  for all colors col from available colors, do 
    if isValid(vertex, color, col), then 
      add col to the colorList for vertex 
      if graphColoring(colors, colorList, vertex+1) = true, then 
        return true 
      remove color for vertex 
  done 
  return false 
End

उदाहरण

#include #define V 4 using namespace std; bool graph[V][V] = { {0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0}, }; void showColors(int color[]) { cout << "Assigned Colors are: " <

आउटपुट
Assigned Colors are: 1 2 3 2