ग्राफ़ रंजन
ग्राफ़ को यथासंभव कम रंगों से रंगें
इस कैलकुलेटर के बारे में
ग्राफ़ रंजन कैलकुलेटर वर्णिक संख्या χ(G) निकालता है — किसी ग्राफ़ के शीर्षों को रंगने के लिए ज़रूरी सबसे कम रंग, ताकि कोई किनारा एक ही रंग के दो शीर्षों को न जोड़े — और एक इष्टतम रंजन दिखाता है। शीर्षों की संख्या और किनारों की सूची दर्ज करें; यह branch-and-bound खोज से χ की सटीक गणना करता है, अधिकतम घात Δ और सबसे बड़ा क्लीक ω (χ की एक निचली सीमा) बताता है, द्विभाजित और पूर्ण ग्राफ़ों को चिह्नित करता है, और रंगा हुआ ग्राफ़ बनाता है। शेड्यूलिंग, रजिस्टर आवंटन, मानचित्र रंजन और वर्णिक संख्याओं के अध्ययन के लिए उपयोगी।
ग्राफ़ को कैसे रंगें
- शीर्षों की संख्या दर्ज करें; उन्हें 1 से n तक क्रमांकित किया जाता है।
- किनारों को 1-2, 2-3 जैसे जोड़ों के रूप में लिखें — हर संबंध के लिए एक जोड़ा।
- वर्णिक संख्या χ(G) और हर शीर्ष को दिया गया रंग पढ़ें।
- χ की तुलना सबसे बड़े क्लीक ω से करके देखें कि इतने रंग क्यों ज़रूरी हैं, या खोजबीन के लिए कोई प्रीसेट लोड करें।
सामान्य उदाहरण
- एक त्रिभुज (K₃) को 3 रंग चाहिए — इसके शीर्षों का हर जोड़ा आसन्न है।
- सम चक्र द्विभाजित होते हैं और उन्हें केवल 2 रंग चाहिए; C₅ जैसे विषम चक्रों को 3 चाहिए।
- पूर्ण ग्राफ़ Kₙ को ठीक n रंग चाहिए।
- ω आकार का सबसे बड़ा क्लीक कम से कम ω रंगों को अनिवार्य करता है, इसलिए χ(G) ≥ ω।
- ग्रोट्ज़्श (Grötzsch) ग्राफ़ में कोई त्रिभुज नहीं है, फिर भी उसे 4 रंग चाहिए, इसलिए χ क्लीक संख्या से अधिक हो सकता है।
अक्सर पूछे जाने वाले प्रश्न
वर्णिक संख्या क्या है?
वर्णिक संख्या χ(G) वह सबसे छोटी रंग-संख्या है जिससे किसी ग्राफ़ के शीर्षों को इस तरह रंगा जा सके कि कोई भी किनारा एक ही रंग के दो शीर्षों को न जोड़े।
न्यूनतम रंग-संख्या कैसे निकाली जाती है?
चूँकि ग्राफ़ छोटा है, कैलकुलेटर सटीक खोज करता है: यह पहले 1 रंग आज़माता है, फिर 2, और इसी तरह आगे, और वह पहली संख्या लौटाता है जिसके लिए सही रंजन मौजूद हो। वह संख्या निश्चित रूप से वास्तविक न्यूनतम होती है।
अधिकतम घात और सबसे बड़ा क्लीक क्या हैं?
अधिकतम घात Δ किसी एक शीर्ष पर मिलने वाले किनारों की सबसे बड़ी संख्या है। सबसे बड़ा क्लीक ω शीर्षों का वह सबसे बड़ा समूह है जिसके सभी शीर्ष परस्पर आसन्न हैं; चूँकि उन सबका रंग अलग होना ज़रूरी है, इसलिए χ(G) कम से कम ω होता है।
त्रिभुज-रहित ग्राफ़ को भी कई रंगों की ज़रूरत क्यों पड़ सकती है?
बड़ा क्लीक कई रंगों को अनिवार्य करता है, लेकिन यही एकमात्र कारण नहीं है। विषम चक्रों और ग्रोट्ज़्श ग्राफ़ जैसे ग्राफ़ों को बिना किसी त्रिभुज के भी अतिरिक्त रंग चाहिए, इसलिए χ(G) क्लीक संख्या से बड़ा हो सकता है।
क्या ग्राफ़ के आकार की कोई सीमा है?
हाँ। सटीक ग्राफ़ रंजन संगणनात्मक रूप से कठिन है, इसलिए परिणामों को तुरंत और सटीक रखने के लिए कैलकुलेटर ग्राफ़ को 12 शीर्षों तक सीमित रखता है।