ग्राफ़ रंग एल्गोरिथ्म

Question

विकि से http://en.wikipedia.org/wiki/Graph_coloring

इसके सरलतम रूप में, यह एक ग्राफ ऐसे कि कोई भी दो आसन्न कोने का हिस्सा एक ही रंग के कोने रंग का एक तरीका है; इसे वर्टेक्स रंग कहा जाता है। इसी तरह, एक बढ़त रंग प्रत्येक किनारे करने के लिए एक रंग प्रदान करती है ताकि कोई दो आसन्न किनारों शेयर एक ही रंग है, और का एक चेहरा रंग एक समतल ग्राफ प्रत्येक चेहरा या क्षेत्र के लिए एक रंग प्रदान करती है ताकि कोई दो चेहरे कि एक सीमा साझा करें रंग है।

को देखते हुए 'एन' रंग और 'मी' कोने, कितनी आसानी से एक ग्राफ रंग एल्गोरिथ्म एक प्रोग्रामिंग भाषा में लागू किया जा सकता?

भाषा कोई बाधा नहीं।

बस एक मस्तिष्क टीज़र।

(ग्राफ मान लें और शिखर वस्तुओं मौजूद हैं)

संपादित करें:
विकी पढ़ने के बाद, समस्या एन पी-सम्पूर्ण
गणित की पुस्तकों :)
मेरा बुरा फिर से समय है।
क्षमा करें।

बस उत्सुक,
क्या यह कोशिश की गई है? लिखने के कार्यक्रम के रूप में एक ही के लिए?
मैंने सुना है कि यह ऑप्टिकल नेटवर्क में उपयोग किया जाता है?

यह घन रंग के समान नहीं है ??
(घन के रंग चेहरे को रंग की न्यूनतम संख्या ताकि कोई दो पहलू एक ही रंग का हिस्सा?)

Answer 1

यह एक एनपी पूरा समस्या है, को हल करने के विभिन्न तरीके के बारे में अधिक जानकारी के लिए Wikipedia entry पढ़ें।

Answer 2

यदि आपको 2 रंग दिए गए हैं, और ग्राफ 2-रंगीन है (यानी यह bipartite graph है), तो आप इसे बहुपद रूप से बहुपद समय में कर सकते हैं।

मैंने इस प्रश्न के उत्तर के रूप में एक छद्म कोड दिया: Graph colouring algorithm: typical scheduling problem।

Answer 3

जैसा कि बताया गया है, सामान्य समस्या एनपी-पूर्ण है। द्विपक्षीय ग्राफ केवल 2 रंगों का उपयोग करके रंगीन हो सकते हैं।

यह भी सच है कि प्लानर ग्राफ़ (ग्राफ्स जिनमें K3,3 or K5 शामिल नहीं है, कुरतोव्स्की के प्रमेय के अनुसार उप ग्राफ के रूप में) 4 रंगों के साथ रंगीन हो सकते हैं।

Answer 4

मेरे मास्टर की थीसिस में मैं रंगीन एल्गोरिदम का परीक्षण करता हूं। सबसे सरल एल्गोरिदम एज बैकट्रैक है।

public boolean edgeBackTrace (List<Edge<T>> edgesList, Map<Edge<T>, List<Edge<T>>> neighborEdges) { 
    for (Edge<T> e : edgesList) { 
    e.setColor(0); 
    } 
    int i = 0; 
    while (true){ 
    Edge<T> edge = edgesList.get(i); 
    edge.setColor(edge.getColor() + 1); 
    if (edge.getColor().equals(4)) { 
     edge.setColor(0); 
     if (i == 0) { 
     return true; 
     } else { 
     i--; 
     } 
    } else { 
     boolean diferentColor = false; 

     for (Edge<T> e : neighborEdges.get(edge)) { 
     if (e.getColor().equals(edge.getColor())) { 
      diferentColor = true; 
     } 
     } 

     if (diferentColor == false) { 
     i++; 
     if (i == edgesList.size()) { 
      return false; 
     } 
     } 
    } 
    } 
} 

एल्गोरिथ्म ग्राफ रंग है, तो सच का एक मान देता है:

यह Java में मेरी कार्यान्वयन है। आप रंग, व्यक्तिगत किनारों के रूप में edgesList में देख सकते हैं।