ग्राफ कलरिंग

File:Petersen graph 3-coloring.svg

3 रंगों के साथ पीटरसन ग्राफ का उचित शीर्ष रंग, न्यूनतम संभव संख्या।

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

वर्टेक्स कलरिंग का उपयोग प्रायः ग्राफ कलरिंग की समस्याओं को पेश करने के लिए किया जाता है, क्योंकि अन्य कलरिंग समस्याओं को वर्टेक्स कलरिंग इंस्टेंस में बदला जा सकता है। उदाहरण के लिए, एक ग्राफ़ का एक किनारा रंग उसके लाइन ग्राफ़ का सिर्फ एक शीर्ष रंग है, और एक समतल ग्राफ़ का एक चेहरा रंग उसके दोहरे का सिर्फ एक शीर्ष रंग है। हालांकि, गैर-शीर्ष रंग की समस्याओं को प्रायः कहा जाता है और उनका अध्ययन किया जाता है। यह आंशिक रूप से शैक्षणिक है, और आंशिक रूप से क्योंकि कुछ समस्याओं का उनके गैर-शीर्ष रूप में सबसे अच्छा अध्ययन किया जाता है, जैसा कि किनारे के रंग के मामले में है।

रंगों का उपयोग करने की परिपाटी एक मानचित्र के देशों को रंगने से उत्पन्न होती है, जहाँ प्रत्येक चेहरा सचमुच रंगीन होता है। यह विमान में एम्बेडेड ग्राफ के चेहरों को रंगने के लिए सामान्यीकृत किया गया था। प्लेनर द्वैत द्वारा यह कोने को रंगने लगा, और इस रूप में यह सभी रेखांकन के लिए सामान्य हो गया। गणितीय और कंप्यूटर अभ्यावेदन में, पहले कुछ सकारात्मक या गैर-नकारात्मक पूर्णांकों को "रंग" के रूप में उपयोग करना विशिष्ट है। सामान्य तौर पर, कोई भी परिमित सेट को "रंग सेट" के रूप में उपयोग कर सकता है। रंजक समस्या की प्रकृति रंगों की संख्या पर निर्भर करती है न कि वे क्या हैं।

ग्राफ़ कलरिंग कई व्यावहारिक अनुप्रयोगों के साथ-साथ सैद्धांतिक चुनौतियों का भी आनंद लेती है। शास्त्रीय प्रकार की समस्याओं के अलावा, ग्राफ़ पर, या जिस तरह से एक रंग सौंपा गया है, या यहाँ तक कि स्वयं रंग पर भी विभिन्न सीमाएँ निर्धारित की जा सकती हैं। यहां तक कि यह लोकप्रिय संख्या पहेली सुडोकू के रूप में साधारण जनता के बीच लोकप्रियता तक पहुंच गया है। ग्राफ कलरिंग अभी भी अनुसंधान का एक बहुत ही सक्रिय क्षेत्र है।

नोट: इस लेख में प्रयुक्त कई शब्दों को राफ सिद्धांत की शब्दावली में परिभाषित किया गया है।

इतिहास

See also: चार रंग प्रमेय का इतिहास and ग्राफ सिद्धांत का इतिहास

ग्राफ़ कलरिंग के बारे में पहला परिणाम नक्शों के रंग के रूप में लगभग अनन्य रूप से प्लानर ग्राफ़ से संबंधित है। इंग्लैंड की काउंटियों के मानचित्र को रंगने की कोशिश करते समय, फ्रांसिस गुथरी ने चार रंगों के अनुमान को स्वीकार किया, यह देखते हुए कि चार रंग नक्शे को रंगने के लिए पर्याप्त थे ताकि किसी भी क्षेत्र में एक समान सीमा साझा करने पर एक ही रंग न हो। मिलना। गुथरी के भाई ने यूनिवर्सिटी कॉलेज में उनके गणित के शिक्षक ऑगस्टस डी मॉर्गन को प्रश्न दिया, जिन्होंने 1852 में विलियम रोवन हैमिल्टन को लिखे एक पत्र में इसका उल्लेख किया। आर्थर केली ने 1879 में लंदन मैथमेटिकल सोसाइटी की बैठक में समस्या को उठाया। उसी वर्ष, अल्फ्रेड केम्पे ने एक पेपर प्रकाशित किया जिसमें परिणाम स्थापित करने का दावा किया गया था, और एक दशक तक चार-रंग की समस्या हल हो गई थी। उनकी उपलब्धि के लिए, केम्पे को रॉयल सोसाइटी का फेलो और बाद में लंदन मैथमेटिकल सोसाइटी का अध्यक्ष चुना गया। [1]

1890 में हेवुड ने बताया कि केम्पे का तर्क गलत था। हालांकि, उस पेपर में उन्होंने यह कहते हुए पांच रंग प्रमेय को साबित कर दिया कि केम्पे के विचारों का उपयोग करके प्रत्येक प्लानर मानचित्र को पांच से अधिक रंगों से रंगा जा सकता है। अगली शताब्दी में, रंगों की संख्या को चार तक कम करने के लिए बड़ी मात्रा में काम और सिद्धांत विकसित किया गया था, जब तक कि केनेथ एपेल और वोल्फगैंग हेइकेन द्वारा 1976 में चार रंग प्रमेय को अंततः सिद्ध नहीं किया गया था। साक्ष्य हेवुड और केम्पे के विचारों पर वापस चले गए और बड़े पैमाने पर हस्तक्षेपों के विकास की अवहेलना की। [2] चार रंग प्रमेय का प्रमाण पहला प्रमुख कंप्यूटर-एडेड प्रमाण होने के लिए भी उल्लेखनीय है।

1912 में, जॉर्ज डेविड बिरखॉफ ने रंगीन समस्याओं का अध्ययन करने के लिए रंगीन बहुपदों की प्रारम्भ की, जिन्हें टुट्टे से टुट्टे बहुपदों तक सामान्यीकृत किया गया था, बीजगणितीय ग्राफ सिद्धांत में महत्वपूर्ण संरचनाएं। केम्पे ने पहले ही 1879 में सामान्य, गैर-प्लानर मामले पर ध्यान आकर्षित किया था, [3] और 20 वीं शताब्दी की प्रारम्भ में उच्च क्रम सतहों के लिए प्लानर ग्राफ रंग के सामान्यीकरण पर कई परिणाम दिखाई दिए।

1960 में, क्लॉड बर्ज ने ग्राफ कलरिंग के बारे में एक और अनुमान तैयार किया, मजबूत सही ग्राफ अनुमान, जो मूल रूप से एक सूचना-सैद्धांतिक अवधारणा से प्रेरित था जिसे शैनन द्वारा प्रस्तुत ग्राफ की शून्य-त्रुटि क्षमता कहा जाता है। यह अनुमान 40 वर्षों तक अनसुलझा रहा, जब तक कि इसे 2002 में चुडनोव्स्की, नील रॉबर्टसन, सीमोर और थॉमस द्वारा एक प्रसिद्ध मजबूत पूर्ण ग्राफ प्रमेय के रूप में स्थापित नहीं किया गया।

1970 के दशक की प्रारम्भ से ग्राफ कलरिंग का एक एल्गोरिथम समस्या के रूप में अध्ययन किया गया है: क्रोमैटिक नंबर प्रॉब्लम (नीचे देखें) 1972 से कार्प की 21 np-पूर्ण समस्याओं में से एक है, और लगभग उसी समय बैकट्रैकिंग एक्सपोनेंशियल-टाइम एल्गोरिदम पर आधारित विभिन्न तरीके थे और ज़ीकोव (1949) के विलोपन-संकुचन पुनरावृत्ति पर। ग्राफ कलरिंग के प्रमुख अनुप्रयोगों में से एक, कंपाइलर्स में रजिस्टर आवंटन, 1981 में पेश किया गया था।

परिभाषा और शब्दावली

File:Graph with all three-colourings 2.svg

यह ग्राफ 12 अलग-अलग तरीकों से 3 रंगों का हो सकता है।

वर्टेक्स रंग

जब बिना किसी योग्यता के उपयोग किया जाता है, तो ग्राफ़ का रंग लगभग हमेशा एक उचित शीर्ष रंग होता है, अर्थात् ग्राफ़ के शीर्षों को रंगों के साथ लेबल करना, जैसे कि एक ही किनारे (ग्राफ़ सिद्धांत) को साझा करने वाले दो शीर्षों का रंग समान नहीं होता है। चूंकि एक पाश (ग्राफ सिद्धांत) (अर्थात् सीधे अपने आप में एक कनेक्शन) के साथ एक शीर्ष कभी भी ठीक से रंगीन नहीं हो सकता है, यह समझा जाता है कि इस संदर्भ में ग्राफ लूपलेस हैं।

वर्टेक्स लेबल्स के लिए रंगों का उपयोग करने की शब्दावली मैप कलरिंग पर वापस जाती है। लाल और नीला जैसे लेबल केवल तभी उपयोग किए जाते हैं जब रंगों की संख्या कम होती है, और सामान्यतः यह समझा जाता है कि लेबल पूर्णांकों से खींचे गए हैं {1, 2, 3, …}. अधिक से अधिक उपयोग करने वाला रंग k रंग कहा जाता है (उचित)k-रंग। किसी ग्राफ़ को रंगने के लिए आवश्यक रंगों की न्यूनतम संख्या G इसकी रंगीन संख्या कहा जाता है, और इसे प्रायः निरूपित किया जाता है χ(G). कभी-कभी γ(G) उपयोग किया जाता है, क्योंकि χ(G) एक ग्राफ की यूलर विशेषता को निरूपित करने के लिए भी प्रयोग किया जाता है। एक ग्राफ जिसे असाइन किया जा सकता है (उचित) k-रंग है k-रंगीन, और यह हैk-क्रोमैटिक अगर इसकी क्रोमैटिक संख्या बिल्कुल है k. एक ही रंग को सौंपे गए शीर्षों के एक उपसमुच्चय को रंग वर्ग कहा जाता है, ऐसा प्रत्येक वर्ग एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) बनाता है। इस प्रकार, एक k-coloring एक शीर्ष सेट को k-स्वतंत्र सेटों में विभाजित करने के बराबर है, और k-match और k-colourable शब्दों का अर्थ समान है।

रंगीन बहुपद

File:Chromatic polynomial of all 3-vertex graphs.png

3 शीर्षों पर सभी गैर-समरूपी रेखांकन और उनके रंगीन बहुपद। खाली ग्राफ E₃ (लाल) 1-रंग स्वीकार करता है; पूरा ग्राफ K₃ (नीला) 3-रंगों को स्वीकार करता है; अन्य रेखांकन एक 2-रंग स्वीकार करते हैं।

Main article: रंगीन बहुपद

रंगीन बहुपद उन तरीकों की गणना करता है जिनमें कुछ दिए गए रंगों का उपयोग करके ग्राफ को रंगीन किया जा सकता है। उदाहरण के लिए, तीन रंगों का उपयोग करके, आसन्न छवि में ग्राफ़ को 12 तरीकों से रंगा जा सकता है। इसे केवल दो रंगों से नहीं रंगा जा सकता। चार रंगों से, इसे 24 + 4⋅12 = 72 तरीकों से रंगा जा सकता है: चारों रंगों का उपयोग करके, 4! = 24 वैध रंग (प्रत्येक चार रंगों का कोई भी 4-वर्टेक्स ग्राफ एक वैध रंग है); और चार में से तीन रंगों की हर पसंद के लिए, 12 मान्य 3-रंग हैं। इसलिए, उदाहरण में ग्राफ़ के लिए, मान्य रंगों की संख्या की तालिका इस तरह प्रारम्भ होगी:

उपलब्ध रंग	1	2	3	4	…
रंगों की संख्या	0	0	12	72	…

रंगीन बहुपद एक कार्य है P(G,t) जो की संख्या की गणना करता है t- का रंग G. जैसा कि नाम इंगित करता है, दिए गए के लिए G समारोह वास्तव में एक बहुपद है t. उदाहरण ग्राफ के लिए, P(G,t) = t(t – 1)²(t – 2), वास्तव में P(G,4) = 72.

रंगीन बहुपद में की रंगीनता के बारे में अधिक जानकारी सम्मिलित है G रंगीन संख्या की तुलना में। वास्तव में, χ सबसे छोटा सकारात्मक पूर्णांक है जो रंगीन बहुपद का शून्य नहीं है χ(G) = min{k : P(G,k) > 0}.

कुछ रेखांकन के लिए रंगीन बहुपद

त्रिकोण K3	t(t – 1)(t – 2)
पूरा ग्राफ Kn	t(t – 1)(t – 2) … (t – (n – 1))
n शीर्षों वाला ट्री	t(t – 1)n – 1
चक्र Cn	(t – 1)n + (-1)n(t – 1)
पीटरसन ग्राफ	t(t – 1)(t – 2)(t7 – 12t6 + 67t5 – 230t4 + 529t3 – 814t2 + 775t – 352)

किनारे का रंग

Main article: किनारे का रंग

एक ग्राफ़ का एक किनारा रंग किनारों का एक उचित रंग है, जिसका अर्थ है कि किनारों को रंगों का एक असाइनमेंट ताकि एक ही रंग के दो किनारों पर कोई शीर्ष घटना न हो। एक किनारे का रंग k रंगों को कहा जाता है k-एज-कलरिंग और एज सेट को विभाजित करने की समस्या के बराबर है k मिलान (ग्राफ सिद्धांत)। किसी ग्राफ़ के किनारों को रंगने के लिए आवश्यक रंगों की सबसे छोटी संख्या G क्रोमैटिक इंडेक्स या एज क्रोमैटिक नंबर है, χ′(G). टैट कलरिंग क्यूबिक ग्राफ का 3-किनारे वाला कलरिंग है। चार रंग प्रमेय इस दावे के बराबर है कि प्रत्येक प्लानर क्यूबिक पुल (ग्राफ सिद्धांत) ग्राफ एक टैट रंग को स्वीकार करता है।

कुल रंग

Main article: समग्र रंगाई

टोटल कलरिंग ग्राफ के कोने और किनारों पर कलरिंग का एक प्रकार है। जब किसी योग्यता के बिना उपयोग किया जाता है, तो कुल रंग हमेशा इस अर्थ में उचित माना जाता है कि कोई आसन्न कोने, कोई आसन्न किनारे नहीं, और कोई किनारा नहीं है और इसके अंत-कोने को एक ही रंग दिया जाता है। कुल रंगीन संख्या χ″(G) एक ग्राफ का G के कुल रंग में सबसे कम आवश्यक रंग G है।

बिना लेबल वाला रंग

किसी ग्राफ़ का लेबल रहित रंग ग्राफ़ के ग्राफ ऑटोमोर्फिज्म की क्रिया के अंतर्गत किसी रंग की समूह क्रिया (गणित) है। ध्यान दें कि रंग लेबल रहते हैं; यह वह ग्राफ है जिसे लेबल नहीं किया गया है। रंगीन बहुपद का एक एनालॉग है जो किसी दिए गए परिमित रंग सेट से ग्राफ के बिना लेबल वाले रंगों की संख्या की गणना करता है।

अगर हम एक ग्राफ के रंग की व्याख्या करते हैं d में एक वेक्टर के रूप में शिखर $\mathbb {Z} ^{d}$, ऑटोमोर्फिज्म की क्रिया रंगीन वेक्टर में गुणांकों का क्रम परिवर्तन है।

गुण

वर्णक्रमीय संख्या पर ऊपरी सीमा

अलग-अलग रंगों को अलग-अलग रंगों में निर्दिष्ट करने से हमेशा एक उचित रंग मिलता है, इसलिए

$1\leq \chi (G)\leq n.$

एकमात्र ग्राफ़ जो 1-रंग का हो सकता है, वे किनारा रहित ग्राफ हैं। एक पूरा ग्राफ $K_{n}$ n शीर्षों की आवश्यकता है $\chi (K_{n})=n$ रंग की। एक इष्टतम रंग में रंग वर्गों की प्रत्येक जोड़ी के बीच ग्राफ के एम किनारों में से कम से कम एक होना चाहिए, इसलिए

$\chi (G)(\chi (G)-1)\leq 2m.$

यदि G में आकार k का एक समूह (ग्राफ़ सिद्धांत) है, तो उस समूह को रंगने के लिए कम से कम k रंगों की आवश्यकता होती है; दूसरे शब्दों में, रंगीन संख्या कम से कम क्लिक संख्या है:

$\chi (G)\geq \omega (G).$

सही रेखांकन के लिए यह सीमा तंग है। क्लिक्स ढूँढना क्लिक्स समस्या के रूप में जाना जाता है।

अधिक सामान्यतः एक परिवार ${\mathcal {F}}$ रेखांकन का Χ-बाध्य है$\chi$-बाउंडेड अगर कोई फंक्शन है $c$ जैसे कि रेखांकन $G$ में ${\mathcal {F}}$ ज्यादा से ज्यादा रंगा जा सकता है $c(\omega (G))$ रंग, सही रेखांकन के परिवार के लिए यह कार्य है $c(\omega (G))=\omega (G)$.

2-रंगीन ग्राफ़ वास्तव में द्विदलीय ग्राफ़ हैं, जिनमें वृक्ष (ग्राफ़ सिद्धांत) और वन सम्मिलित हैं।

चार रंग प्रमेय के अनुसार, प्रत्येक प्लानर ग्राफ 4-रंगों का हो सकता है।

एक लालची रंग दिखाता है कि प्रत्येक ग्राफ को अधिकतम शीर्ष डिग्री (ग्राफ सिद्धांत) की तुलना में एक और रंग से रंगा जा सकता है।

$\chi (G)\leq \Delta (G)+1.$

पूरा रेखांकन है $\chi (G)=n$ और $\Delta (G)=n-1$, और विषम चक्र हैं $\chi (G)=3$ और $\mathrm{\Delta <!--\; \Delta \; -->}$