ग्राफ रंगाई

ग्राफ रंगाई समस्या ग्राफ लेबलिंग का एक विशेष मामला है। इस समस्या में, प्रत्येक नोड को कुछ रंगों में रंगा जाता है। लेकिन रंगाई के कुछ प्रतिबंध हैं। हम किसी भी आसन्न शीर्षों के लिए समान रंग का उपयोग नहीं कर सकते।

इस समस्या को हल करने के लिए, हमें लालची एल्गोरिदम का उपयोग करने की आवश्यकता है, लेकिन यह न्यूनतम रंग के उपयोग की गारंटी नहीं देता।

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

इनपुट: ग्राफ का आसन्नता मैट्रिक्स। 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 आउटपुट: नोड: 0, रंग: 0 के साथ असाइन किया गया नोड: 1, रंग: 0 के साथ असाइन किया गया नोड: 2, रंग: 1 के साथ असाइन किया गया नोड: 3, रंग: 2 के साथ असाइन किया गया नोड: 4, रंग: 1 के साथ असाइन किया गया

एल्गोरिदम

graphColoring(graph)

इनपुट: दिया गया ग्राफ।

आउटपुट: प्रत्येक नोड को कुछ रंग असाइन किया गया।

शुरू     रंगों की एक सूची घोषित करें     प्रारंभ में पहले नोड के लिए रंग 0 सेट करें     एक सरणी colorUsed परिभाषित करें जो ट्रैक करे कि कौन सा रंग उपयोग किया गया है, और किन रंगों का कभी उपयोग नहीं किया गया।     पहले को छोड़कर ग्राफ में सभी शीर्षों i के लिए, करें       i को किसी भी रंग के लिए अनअसाइन के रूप में चिह्नित करें     किया     सभी शीर्षों के लिए colorUsed को गलत चिह्नित करें     पहले शीर्ष को छोड़कर ग्राफ में सभी शीर्षों u के लिए, करें       u के साथ आसन्न सभी शीर्ष v के लिए, करें         यदि color[v] अनअसाइन है, तो           colorUsed[color[v]] := सच       किया       रंग सूची में सभी रंगों col के लिए, करें         यदि रंग उपयोग नहीं किया गया है, तो           लूप रोकें       किया       color[u] := col       u के साथ आसन्न प्रत्येक शीर्ष v के लिए, करें         यदि color[v] अनअसाइन है, तो           colorUsed[color[v]] := गलत       किया     किया     ग्राफ में सभी शीर्षों u के लिए, करें       नोड और उसका रंग प्रदर्शित करें     किया अंत

उदाहरण

#include<iostream> #define NODE 6 using namespace std; int graph[NODE][NODE] = {     {0, 1, 1, 1, 0, 0},     {1, 0, 0, 1, 1, 0},     {1, 0, 0, 1, 0, 1},     {1, 1, 1, 0, 1, 1},     {0, 1, 0, 1, 0, 1},     {0, 0, 1, 1, 1, 0} }; void graphColoring() {     int color[NODE];     color[0] = 0;       //पहले नोड के लिए पहला रंग असाइन करें     bool colorUsed[NODE];       //जांचने के लिए उपयोग किया जाता है कि रंग उपयोग किया गया है या नहीं     for(int i = 1; i
आउटपुट
Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1