ग्राफ कलरिंग कैलकुलेटर
वेल्श-पॉवेल एल्गोरिदम · क्रोमैटिक संख्या · वर्टेक्स कलरिंग
एक अदिशित ग्राफ (undirected graph) को किनारों की सूची (edge list) के रूप में दर्ज करें और तुरंत एक सही वर्टेक्स कलरिंग प्राप्त करें। यह वेल्श-पॉवेल ग्रीडी एल्गोरिदम का उपयोग करके क्रोमैटिक संख्या की ऊपरी सीमा की गणना करता है और रंगीन ग्राफ को कैनवास पर दिखाता है।
त्वरित उदाहरण (Quick Examples)
प्रति पंक्ति एक किनारा या अल्पविराम से अलग करके लिखें। नोड आईडी के बीच हाइफ़न या स्पेस का उपयोग करें। जैसे: 1-2, 1-3, 2-3 या प्रति पंक्ति A B। विज़ुअलाइज़ेशन के लिए अधिकतम 20 नोड्स।
शीर्ष रंग आवंटन (Vertex Color Assignments)
| शीर्ष (Vertex) | डिग्री (Degree) | रंग संख्या | रंग का नाम |
|---|
ग्राफ विज़ुअलाइज़ेशन (Graph Visualization)
ग्राफ के गुण (Graph Properties)
डिग्री अनुक्रम (Degree Sequence)
क्रोमैटिक संख्या सीमाएं (Chromatic Number Bounds)
ग्राफ कलरिंग (Graph Coloring) क्या है?
ग्राफ कलरिंग कॉम्बिनेटॉरिक्स और सैद्धांतिक कंप्यूटर विज्ञान में सबसे अधिक अध्ययन की जाने वाली समस्याओं में से एक है। इसके सबसे सामान्य रूप — वर्टेक्स कलरिंग (शीर्ष रंगाई) — में लक्ष्य प्रत्येक शीर्ष को एक "रंग" (एक परिमित सेट से एक लेबल) आवंटित करना होता है ताकि कोई भी दो आसन्न शीर्ष (adjacent vertices) एक ही रंग साझा न करें। इस बाधा को पूरा करने वाले रंग असाइनमेंट को उचित रंगाई (proper coloring) कहा जाता है।
ग्राफ कलरिंग का एक समृद्ध इतिहास है जो प्रसिद्ध नक्शा रंगाई समस्या से जुड़ा है: किसी मानचित्र को रंगने के लिए कितने रंगों की आवश्यकता होती है ताकि कोई भी दो पड़ोसी देश एक ही रंग साझा न करें? इस प्रश्न ने अंततः प्रसिद्ध फोर कलर थ्योरम को जन्म दिया।
क्रोमैटिक संख्या (Chromatic Number)
किसी ग्राफ G की क्रोमैटिक संख्या χ(G) एक उचित शीर्ष रंगाई के लिए आवश्यक रंगों की न्यूनतम संख्या है। यह ग्राफ सिद्धांत में सबसे बुनियादी मापदंडों में से एक है:
- बिना किनारों वाले ग्राफ में χ = 1 होता है।
- कम से कम एक किनारे वाले किसी भी ग्राफ में χ ≥ 2 होता है।
- द्विपक्षीय ग्राफ (bipartite graphs) में χ = 2 होता है।
- विषम चक्र (odd cycles) C2k+1 में χ = 3 होता है।
- पूर्ण ग्राफ (complete graphs) Kn में χ = n होता है।
- पेड़ों (trees) में χ = 2 होता है।
वेल्श-पॉवेल एल्गोरिदम (Welsh-Powell Algorithm)
वेल्श-पॉवेल एल्गोरिदम (1967) एक ग्रीडी वर्टेक्स कलरिंग एल्गोरिदम है जो एक विशेष शीर्ष अनुक्रम का उपयोग करके परिणाम को बेहतर बनाता है:
- चरण 1: सभी शीर्षों को उनकी डिग्री (पड़ोसियों की संख्या) के अनुसार अवरोही क्रम में व्यवस्थित करें।
- चरण 2: प्रत्येक शीर्ष के लिए, उसके पड़ोसियों द्वारा उपयोग न किया गया सबसे छोटा उपलब्ध रंग आवंटित करें।
- चरण 3: उपयोग किए गए अलग-अलग रंगों की कुल संख्या χ(G) की ऊपरी सीमा है।
ग्राफ कलरिंग के अनुप्रयोग (Applications of Graph Coloring)
- रजिस्टर आवंटन (Register Allocation): कंपाइलर में उन वेरिएबल्स को अलग-अलग सीपीयू रजिस्टरों में रखना होता है जो एक ही समय में सक्रिय होते हैं।
- शेड्यूलिंग (Scheduling): एक ही समय पर होने वाली परीक्षाओं या कार्यों को अलग-अलग टाइम-स्लॉट आवंटित करने के लिए।
- सुडोकू हल करना (Sudoku Solving): सुडोकू पहेली को हल करना वास्तव में एक ग्राफ के 9-कलरिंग की समस्या है।
- वायरलेस फ्रीक्वेंसी आवंटन: आसन्न सेल टावरों को अलग-अलग फ्रीक्वेंसी आवंटित करना ताकि हस्तक्षेप (interference) न हो।