ग्राफ कलरिंग: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (5 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Methodic assignment of colors to elements of a graph}} | {{Short description|Methodic assignment of colors to elements of a graph}} | ||
[[File:Petersen graph 3-coloring.svg|thumb|right|3 रंगों के साथ [[पीटरसन ग्राफ]] का उचित शीर्ष रंग, न्यूनतम संभव संख्या।]]ग्राफ़ सिद्धांत में, ग्राफ़ कलरिंग [[ग्राफ लेबलिंग]] का एक विशेष स्थिति है; यह कुछ बाधाओं के अधीन एक ग्राफ के तत्वों के लिए पारंपरिक रूप से "रंग" कहे जाने वाले लेबल का एक असाइनमेंट है। अपने सरलतम रूप में, यह ग्राफ के शीर्षों को इस प्रकार रंगने का एक तरीका है कि कोई भी दो आसन्न शीर्ष एक ही रंग के न हों; इसे वर्टेक्स कलरिंग कहा जाता है। इसी तरह, किनारे का रंग प्रत्येक किनारे को एक रंग प्रदान करता है ताकि कोई भी दो आसन्न किनारे एक ही रंग के न हों, और समतल ग्राफ का एक चेहरा रंग प्रत्येक चेहरे या क्षेत्र को एक रंग प्रदान करता है ताकि कोई भी दो आसन्न किनारे एक ही रंग के चेहरे न हों एक ही रंग का न हो। | [[File:Petersen graph 3-coloring.svg|thumb|right|3 रंगों के साथ [[पीटरसन ग्राफ]] का उचित शीर्ष रंग, न्यूनतम संभव संख्या।]]ग्राफ़ सिद्धांत में, '''ग्राफ़ कलरिंग''' [[ग्राफ लेबलिंग]] का एक विशेष स्थिति है; यह कुछ बाधाओं के अधीन एक ग्राफ के तत्वों के लिए पारंपरिक रूप से "रंग" कहे जाने वाले लेबल का एक असाइनमेंट है। अपने सरलतम रूप में, यह ग्राफ के शीर्षों को इस प्रकार रंगने का एक तरीका है कि कोई भी दो आसन्न शीर्ष एक ही रंग के न हों; इसे वर्टेक्स कलरिंग कहा जाता है। इसी तरह, किनारे का रंग प्रत्येक किनारे को एक रंग प्रदान करता है ताकि कोई भी दो आसन्न किनारे एक ही रंग के न हों, और समतल ग्राफ का एक चेहरा रंग प्रत्येक चेहरे या क्षेत्र को एक रंग प्रदान करता है ताकि कोई भी दो आसन्न किनारे एक ही रंग के चेहरे न हों एक ही रंग का न हो। | ||
वर्टेक्स कलरिंग का उपयोग प्रायः ग्राफ कलरिंग की समस्याओं को पेश करने के लिए किया जाता है, क्योंकि अन्य कलरिंग समस्याओं को वर्टेक्स कलरिंग इंस्टेंस में बदला जा सकता है। उदाहरण के लिए, एक ग्राफ़ का एक किनारा रंग उसके लाइन ग्राफ़ का सिर्फ एक शीर्ष रंग है, और एक समतल ग्राफ़ का एक चेहरा रंग उसके दोहरे का सिर्फ एक शीर्ष रंग है। हालांकि, गैर-शीर्ष रंग की समस्याओं को प्रायः कहा जाता है और उनका अध्ययन किया जाता है। यह आंशिक रूप से शैक्षणिक है, और आंशिक रूप से क्योंकि कुछ समस्याओं का उनके गैर-शीर्ष रूप में सबसे अच्छा अध्ययन किया जाता है, जैसा कि किनारे के रंग के स्थिति में है। | वर्टेक्स कलरिंग का उपयोग प्रायः ग्राफ कलरिंग की समस्याओं को पेश करने के लिए किया जाता है, क्योंकि अन्य कलरिंग समस्याओं को वर्टेक्स कलरिंग इंस्टेंस में बदला जा सकता है। उदाहरण के लिए, एक ग्राफ़ का एक किनारा रंग उसके लाइन ग्राफ़ का सिर्फ एक शीर्ष रंग है, और एक समतल ग्राफ़ का एक चेहरा रंग उसके दोहरे का सिर्फ एक शीर्ष रंग है। हालांकि, गैर-शीर्ष रंग की समस्याओं को प्रायः कहा जाता है और उनका अध्ययन किया जाता है। यह आंशिक रूप से शैक्षणिक है, और आंशिक रूप से क्योंकि कुछ समस्याओं का उनके गैर-शीर्ष रूप में सबसे अच्छा अध्ययन किया जाता है, जैसा कि किनारे के रंग के स्थिति में है। | ||
रंगों का उपयोग करने की परिपाटी एक मानचित्र के देशों को रंगने से उत्पन्न होती है, जहाँ प्रत्येक चेहरा सचमुच रंगीन होता है। यह सतह में | रंगों का उपयोग करने की परिपाटी एक मानचित्र के देशों को रंगने से उत्पन्न होती है, जहाँ प्रत्येक चेहरा सचमुच रंगीन होता है। यह सतह में अंतर्निहितग्राफ के चेहरों को रंगने के लिए सामान्यीकृत किया गया था। प्लेनर द्वैत द्वारा यह कोने को रंगने लगा, और इस रूप में यह सभी रेखांकन के लिए सामान्य हो गया। गणितीय और कंप्यूटर अभ्यावेदन में, पहले कुछ धनात्मक या गैर-ऋणात्मक पूर्णांकों को "रंग" के रूप में उपयोग करना विशिष्ट है। सामान्य तौर पर, कोई भी परिमित सेट को "रंग सेट" के रूप में उपयोग कर सकता है। रंजक समस्या की प्रकृति रंगों की संख्या पर निर्भर करती है न कि वे क्या हैं। | ||
ग्राफ़ कलरिंग कई व्यावहारिक अनुप्रयोगों के साथ-साथ सैद्धांतिक चुनौतियों का भी आनंद लेती है। शास्त्रीय प्रकार की समस्याओं के अलावा, ग्राफ़ पर, या जिस तरह से एक रंग सौंपा गया है, या यहाँ तक कि स्वयं रंग पर भी विभिन्न सीमाएँ निर्धारित की जा सकती हैं। यहां तक कि यह लोकप्रिय संख्या पहेली सुडोकू के रूप में साधारण जनता के बीच लोकप्रियता तक पहुंच गया है। ग्राफ कलरिंग अभी भी अनुसंधान का एक बहुत ही सक्रिय क्षेत्र है। | ग्राफ़ कलरिंग कई व्यावहारिक अनुप्रयोगों के साथ-साथ सैद्धांतिक चुनौतियों का भी आनंद लेती है। शास्त्रीय प्रकार की समस्याओं के अलावा, ग्राफ़ पर, या जिस तरह से एक रंग सौंपा गया है, या यहाँ तक कि स्वयं रंग पर भी विभिन्न सीमाएँ निर्धारित की जा सकती हैं। यहां तक कि यह लोकप्रिय संख्या पहेली सुडोकू के रूप में साधारण जनता के बीच लोकप्रियता तक पहुंच गया है। ग्राफ कलरिंग अभी भी अनुसंधान का एक बहुत ही सक्रिय क्षेत्र है। | ||
| Line 13: | Line 13: | ||
{{See also |चार रंग प्रमेय का इतिहास|ग्राफ सिद्धांत का इतिहास}} | {{See also |चार रंग प्रमेय का इतिहास|ग्राफ सिद्धांत का इतिहास}} | ||
ग्राफ़ कलरिंग के बारे में पहला परिणाम नक्शों के रंग के रूप में लगभग अनन्य रूप से प्लानर ग्राफ़ से संबंधित है। इंग्लैंड की काउंटियों के मानचित्र को रंगने की | ग्राफ़ कलरिंग के बारे में पहला परिणाम नक्शों के रंग के रूप में लगभग अनन्य रूप से प्लानर ग्राफ़ से संबंधित है। इंग्लैंड की काउंटियों के मानचित्र को रंगने की प्रयास करते समय, [[फ्रांसिस गुथरी]] ने चार रंगों के अनुमान को स्वीकार किया, यह देखते हुए कि चार रंग नक्शे को रंगने के लिए पर्याप्त थे ताकि किसी भी क्षेत्र में एक समान सीमा साझा करने पर एक ही रंग न हो। गुथरी के भाई ने [[यूनिवर्सिटी कॉलेज लंदन|यूनिवर्सिटी कॉलेज]] में उनके गणित के शिक्षक [[ऑगस्टस डी मॉर्गन]] को प्रश्न दिया, जिन्होंने 1852 में [[विलियम रोवन हैमिल्टन]] को लिखे एक पत्र में इसका उल्लेख किया। [[आर्थर केली]] ने 1879 में लंदन मैथमेटिकल सोसाइटी की बैठक में समस्या को उठाया। उसी वर्ष, [[अल्फ्रेड केम्पे]] ने एक पेपर प्रकाशित किया जिसमें परिणाम स्थापित करने का दावा किया गया था, और एक दशक तक चार-रंग की समस्या हल हो गई थी। उनकी उपलब्धि के लिए केम्पे को रॉयल सोसाइटी का फेलो और बाद में लंदन मैथमेटिकल सोसाइटी का अध्यक्ष चुना गया था।<ref>M. Kubale, ''History of graph coloring'', in {{harvtxt|Kubale|2004}}</ref> | ||
1890 में हेवुड ने बताया कि केम्पे का तर्क गलत था। हालांकि, उस पेपर में उन्होंने यह कहते हुए पांच रंग प्रमेय को साबित कर दिया कि केम्पे के विचारों का उपयोग करके प्रत्येक प्लानर मानचित्र को पांच से अधिक रंगों से रंगा जा सकता है। अगली शताब्दी में, रंगों की संख्या को चार तक कम करने के लिए बड़ी मात्रा में काम और सिद्धांत विकसित किया गया था, जब तक कि केनेथ एपेल और वोल्फगैंग हेइकेन द्वारा 1976 में चार रंग प्रमेय को अंततः सिद्ध नहीं किया गया था। साक्ष्य हेवुड और केम्पे के विचारों पर वापस चले गए और बड़े पैमाने पर हस्तक्षेपों के विकास की अवहेलना की। | 1890 में हेवुड ने बताया कि केम्पे का तर्क गलत था। हालांकि, उस पेपर में उन्होंने यह कहते हुए पांच रंग प्रमेय को साबित कर दिया कि केम्पे के विचारों का उपयोग करके प्रत्येक प्लानर मानचित्र को पांच से अधिक रंगों से रंगा जा सकता है। अगली शताब्दी में, रंगों की संख्या को चार तक कम करने के लिए बड़ी मात्रा में काम और सिद्धांत विकसित किया गया था, जब तक कि केनेथ एपेल और वोल्फगैंग हेइकेन द्वारा 1976 में चार रंग प्रमेय को अंततः सिद्ध नहीं किया गया था। साक्ष्य हेवुड और केम्पे के विचारों पर वापस चले गए और बड़े पैमाने पर हस्तक्षेपों के विकास की अवहेलना की।<ref>{{harvtxt|van Lint|Wilson|2001|loc=Chap. 33}}</ref> चार रंग प्रमेय का प्रमाण पहला प्रमुख कंप्यूटर-एडेड प्रमाण होने के लिए भी उल्लेखनीय है। | ||
1912 में, [[जॉर्ज डेविड बिरखॉफ]] ने रंगीन समस्याओं का अध्ययन करने के लिए रंगीन बहुपदों की प्रारम्भ की, जिन्हें टुट्टे से टुट्टे बहुपदों तक सामान्यीकृत किया गया था, [[बीजगणितीय ग्राफ सिद्धांत]] में महत्वपूर्ण संरचनाएं। केम्पे ने पहले ही 1879 में सामान्य, गैर-प्लानर स्थिति पर ध्यान आकर्षित किया था, | 1912 में, [[जॉर्ज डेविड बिरखॉफ]] ने रंगीन समस्याओं का अध्ययन करने के लिए रंगीन बहुपदों की प्रारम्भ की, जिन्हें टुट्टे से टुट्टे बहुपदों तक सामान्यीकृत किया गया था, [[बीजगणितीय ग्राफ सिद्धांत]] में महत्वपूर्ण संरचनाएं। केम्पे ने पहले ही 1879 में सामान्य, गैर-प्लानर स्थिति पर ध्यान आकर्षित किया था, <ref>{{harvtxt|Jensen|Toft|1995}}, p. 2</ref> और 20 वीं शताब्दी की प्रारम्भ में उच्च क्रम सतहों के लिए प्लानर ग्राफ रंग के सामान्यीकरण पर कई परिणाम दिखाई दिए। | ||
1960 में, क्लॉड बर्ज ने ग्राफ कलरिंग के बारे में एक और अनुमान तैयार किया, मजबूत सही ग्राफ अनुमान, जो मूल रूप से एक सूचना-सैद्धांतिक अवधारणा से प्रेरित था जिसे शैनन द्वारा प्रस्तुत ग्राफ की शून्य-त्रुटि क्षमता कहा जाता है। यह अनुमान 40 वर्षों तक अनसुलझा रहा, जब तक कि इसे 2002 में [[मारिया चुडनोव्स्की|चुडनोव्स्की]], [[नील रॉबर्टसन (गणितज्ञ)|नील रॉबर्टसन]], सीमोर और थॉमस द्वारा एक प्रसिद्ध मजबूत पूर्ण ग्राफ प्रमेय के रूप में स्थापित नहीं किया | 1960 में, क्लॉड बर्ज ने ग्राफ कलरिंग के बारे में एक और अनुमान तैयार किया, मजबूत सही ग्राफ अनुमान, जो मूल रूप से एक सूचना-सैद्धांतिक अवधारणा से प्रेरित था जिसे शैनन द्वारा प्रस्तुत ग्राफ की शून्य-त्रुटि क्षमता कहा जाता है। यह अनुमान 40 वर्षों तक अनसुलझा रहा, जब तक कि इसे 2002 में [[मारिया चुडनोव्स्की|चुडनोव्स्की]], [[नील रॉबर्टसन (गणितज्ञ)|नील रॉबर्टसन]], सीमोर और थॉमस द्वारा एक प्रसिद्ध मजबूत पूर्ण ग्राफ प्रमेय के रूप में स्थापित नहीं किया गया था। | ||
1970 के दशक की प्रारम्भ से ग्राफ कलरिंग का एक एल्गोरिथम समस्या के रूप में अध्ययन किया गया है: क्रोमैटिक नंबर प्रॉब्लम (नीचे देखें) 1972 से कार्प की 21 एनपी-सम्पूर्ण समस्याओं में से एक है, और लगभग उसी समय बैकट्रैकिंग | 1970 के दशक की प्रारम्भ से ग्राफ कलरिंग का एक एल्गोरिथम समस्या के रूप में अध्ययन किया गया है: क्रोमैटिक नंबर प्रॉब्लम (नीचे देखें) 1972 से कार्प की 21 एनपी-सम्पूर्ण समस्याओं में से एक है, और लगभग उसी समय बैकट्रैकिंग घातीय-समय एल्गोरिथम पर आधारित विभिन्न तरीके थे और ज़ीकोव (1949) के विलोपन-संकुचन पुनरावृत्ति पर। ग्राफ कलरिंग के प्रमुख अनुप्रयोगों में से एक, कंपाइलर्स में रजिस्टर आवंटन, 1981 में पेश किया गया था। | ||
== परिभाषा और शब्दावली == | == परिभाषा और शब्दावली == | ||
| Line 30: | Line 30: | ||
जब बिना किसी योग्यता के उपयोग किया जाता है, तो ग्राफ़ का रंग लगभग हमेशा एक ''उचित शीर्ष रंग'' होता है, अर्थात् ग्राफ़ के शीर्षों को रंगों के साथ लेबल करना, जैसे कि एक ही किनारे (ग्राफ़ सिद्धांत) को साझा करने वाले दो शीर्षों का रंग समान नहीं होता है। चूंकि एक [[पाश (ग्राफ सिद्धांत)]] (अर्थात् सीधे अपने आप में एक कनेक्शन) के साथ एक शीर्ष कभी भी ठीक से रंगीन नहीं हो सकता है, यह समझा जाता है कि इस संदर्भ में ग्राफ लूपलेस हैं। | जब बिना किसी योग्यता के उपयोग किया जाता है, तो ग्राफ़ का रंग लगभग हमेशा एक ''उचित शीर्ष रंग'' होता है, अर्थात् ग्राफ़ के शीर्षों को रंगों के साथ लेबल करना, जैसे कि एक ही किनारे (ग्राफ़ सिद्धांत) को साझा करने वाले दो शीर्षों का रंग समान नहीं होता है। चूंकि एक [[पाश (ग्राफ सिद्धांत)]] (अर्थात् सीधे अपने आप में एक कनेक्शन) के साथ एक शीर्ष कभी भी ठीक से रंगीन नहीं हो सकता है, यह समझा जाता है कि इस संदर्भ में ग्राफ लूपलेस हैं। | ||
वर्टेक्स लेबल्स के लिए ''रंगों'' का उपयोग करने की शब्दावली मैप कलरिंग पर वापस जाती है। ''लाल'' और ''नीला'' जैसे लेबल केवल तभी उपयोग किए जाते हैं जब रंगों की संख्या कम होती है, और सामान्यतः यह समझा जाता है कि लेबल [[पूर्णांक]] | वर्टेक्स लेबल्स के लिए ''रंगों'' का उपयोग करने की शब्दावली मैप कलरिंग पर वापस जाती है। ''लाल'' और ''नीला'' जैसे लेबल केवल तभी उपयोग किए जाते हैं जब रंगों की संख्या कम होती है, और सामान्यतः यह समझा जाता है कि लेबल [[पूर्णांक]] से खींचे गए हैं {{math|{1, 2, 3, …}.}} अधिक से अधिक उपयोग करने वाला रंग {{mvar|k}} रंग कहा जाता है (उचित) {{mvar|k}}-रंग। किसी ग्राफ़ को रंगने के लिए आवश्यक रंगों की न्यूनतम संख्या {{mvar|G}} इसकी रंगीन संख्या कहा जाता है, और इसे प्रायः निरूपित किया जाता है {{math|χ(''G'')}}. कभी-कभी {{math|γ(''G'')}} उपयोग किया जाता है, क्योंकि {{math|χ(''G'')}} ग्राफ की [[यूलर विशेषता]] को निरूपित करने के लिए भी प्रयोग किया जाता है। एक ग्राफ जिसे असाइन किया जा सकता है (उचित) {{mvar|k}}-रंग है {{mvar|k}}-रंगीन, और यह है{{mvar|k}}-क्रोमैटिक अगर इसकी क्रोमैटिक संख्या बिल्कुल है {{mvar|k}}. एक ही रंग को सौंपे गए शीर्षों के एक उपसमुच्चय को रंग वर्ग कहा जाता है, ऐसा प्रत्येक वर्ग एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) बनाता है। इस प्रकार, एक {{mvar|k}}-coloring एक शीर्ष सेट को {{mvar|k}}-स्वतंत्र सेटों में विभाजित करने के बराबर है, और {{mvar|k}}-match और {{mvar|k}}-colourable शब्दों का अर्थ समान है। | ||
=== रंगीन बहुपद === | === रंगीन बहुपद === | ||
| Line 45: | Line 45: | ||
| 0 || 0 || 12 || 72 || … | | 0 || 0 || 12 || 72 || … | ||
|} | |} | ||
रंगीन बहुपद एक कार्य है {{math|''P''(''G'',''t'')}} जो की संख्या की गणना करता है {{mvar|t}}- का रंग {{mvar|G}}. जैसा कि नाम इंगित करता है, दिए गए के लिए {{mvar|G}} | रंगीन बहुपद एक कार्य है {{math|''P''(''G'',''t'')}} जो की संख्या की गणना करता है {{mvar|t}}- का रंग {{mvar|G}}. जैसा कि नाम इंगित करता है, दिए गए के लिए {{mvar|G}} फंक्शन वास्तव में एक [[बहुपद]] है {{mvar|t}}. उदाहरण ग्राफ के लिए, {{math|1=''P''(''G'',''t'') = ''t''(''t'' – 1){{sup|2}}(''t'' – 2)}}, वास्तव में {{math|1=''P''(''G'',4) = 72}}. | ||
रंगीन बहुपद में की रंगीनता के बारे में अधिक जानकारी सम्मिलित है {{mvar|G}} रंगीन संख्या की तुलना में। वास्तव में, {{mvar|χ}} सबसे छोटा | रंगीन बहुपद में की रंगीनता के बारे में अधिक जानकारी सम्मिलित है {{mvar|G}} रंगीन संख्या की तुलना में। वास्तव में, {{mvar|χ}} सबसे छोटा धनात्मक पूर्णांक है जो {{math|1=χ(''G'') = min{''k'' : ''P''(''G'',''k'') > 0}.}}रंगीन बहुपद का शून्य नहीं है | ||
{| class="wikitable" style="background:white;" | {| class="wikitable" style="background:white;" | ||
| Line 70: | Line 70: | ||
===किनारे का रंग === | ===किनारे का रंग === | ||
{{Main|किनारे का रंग}} | {{Main|किनारे का रंग}} | ||
एक ग्राफ़ का एक किनारा रंग ''किनारों'' का एक उचित रंग है, जिसका अर्थ है कि किनारों को रंगों का एक असाइनमेंट ताकि एक ही रंग के दो किनारों पर कोई शीर्ष घटना न हो। एक किनारे का रंग {{mvar|k}} रंगों को कहा जाता है {{mvar|k}}-एज-कलरिंग और एज सेट को विभाजित करने की समस्या के बराबर है {{mvar|k}} [[मिलान (ग्राफ सिद्धांत)]]। किसी ग्राफ़ के किनारों को रंगने के लिए आवश्यक रंगों की सबसे छोटी संख्या {{mvar|G}} क्रोमैटिक | एक ग्राफ़ का एक किनारा रंग ''किनारों'' का एक उचित रंग है, जिसका अर्थ है कि किनारों को रंगों का एक असाइनमेंट ताकि एक ही रंग के दो किनारों पर कोई शीर्ष घटना न हो। एक किनारे का रंग {{mvar|k}} रंगों को कहा जाता है {{mvar|k}}-एज-कलरिंग और एज सेट को विभाजित करने की समस्या के बराबर है {{mvar|k}} [[मिलान (ग्राफ सिद्धांत)]]। किसी ग्राफ़ के किनारों को रंगने के लिए आवश्यक रंगों की सबसे छोटी संख्या {{mvar|G}} क्रोमैटिक सूचकांक या एज क्रोमैटिक नंबर है, {{math|χ′(''G'')}}. टैट कलरिंग [[क्यूबिक ग्राफ]] का 3-किनारे वाला कलरिंग है। [[चार रंग प्रमेय]] इस दावे के बराबर है कि प्रत्येक प्लानर क्यूबिक [[पुल (ग्राफ सिद्धांत)]] ग्राफ एक टैट रंग को स्वीकार करता है। | ||
=== कुल रंग === | === कुल रंग === | ||
| Line 77: | Line 77: | ||
=== बिना लेबल वाला रंग === | === बिना लेबल वाला रंग === | ||
किसी ग्राफ़ का लेबल रहित रंग ग्राफ़ के [[ग्राफ ऑटोमोर्फिज्म]] की क्रिया के अंतर्गत किसी रंग की [[समूह क्रिया (गणित)]] है। ध्यान दें कि रंग लेबल रहते हैं; यह वह ग्राफ है जिसे लेबल नहीं किया गया है। | किसी ग्राफ़ का लेबल रहित रंग ग्राफ़ के [[ग्राफ ऑटोमोर्फिज्म]] की क्रिया के अंतर्गत किसी रंग की [[समूह क्रिया (गणित)]] है। ध्यान दें कि रंग लेबल रहते हैं; यह वह ग्राफ है जिसे लेबल नहीं किया गया है। रंगीन बहुपद का एक एनालॉग है जो किसी दिए गए परिमित रंग सेट से ग्राफ के बिना लेबल वाले रंगों की संख्या की गणना करता है। अगर हम एक ग्राफ के रंग की व्याख्या करते हैं {{mvar|d}} में एक वेक्टर के रूप में शिखर {{tmath|\mathbb{Z}^d}}, ऑटोमोर्फिज्म की क्रिया रंगीन वेक्टर में गुणांकों का क्रम [[परिवर्तन]] है। | ||
रंगीन बहुपद का एक एनालॉग है जो किसी दिए गए परिमित रंग सेट से ग्राफ के बिना लेबल वाले रंगों की संख्या की गणना करता है। | |||
अगर हम एक ग्राफ के रंग की व्याख्या करते हैं {{mvar|d}} में एक वेक्टर के रूप में शिखर {{tmath|\mathbb{Z}^d}}, ऑटोमोर्फिज्म की क्रिया रंगीन वेक्टर में गुणांकों का क्रम [[परिवर्तन]] है। | |||
== गुण == | == गुण == | ||
| Line 89: | Line 86: | ||
: <math>1 \le \chi(G) \le n.</math> | : <math>1 \le \chi(G) \le n.</math> | ||
एकमात्र ग्राफ़ जो 1-रंग का हो सकता है, वे [[किनारा रहित ग्राफ]] हैं। एक [[पूरा ग्राफ]] <math>K_n</math> n शीर्षों की आवश्यकता है <math>\chi(K_n)=n</math> रंग की। एक इष्टतम रंग में रंग वर्गों की प्रत्येक जोड़ी के बीच ग्राफ के | एकमात्र ग्राफ़ जो 1-रंग का हो सकता है, वे [[किनारा रहित ग्राफ]] हैं। एक [[पूरा ग्राफ]] <math>K_n</math> n शीर्षों की आवश्यकता है <math>\chi(K_n)=n</math> रंग की। एक इष्टतम रंग में रंग वर्गों की प्रत्येक जोड़ी के बीच ग्राफ के m किनारों में से कम से कम एक होना चाहिए, इसलिए | ||
: <math>\chi(G)(\chi(G)-1) \le 2m.</math> | : <math>\chi(G)(\chi(G)-1) \le 2m.</math> | ||
| Line 97: | Line 94: | ||
सही रेखांकन के लिए यह सीमा तंग है। क्लिक्स ढूँढना क्लिक्स समस्या के रूप में जाना जाता है। | सही रेखांकन के लिए यह सीमा तंग है। क्लिक्स ढूँढना क्लिक्स समस्या के रूप में जाना जाता है। | ||
अधिक सामान्यतः एक परिवार <math>\mathcal{F}</math> रेखांकन का Χ-बाध्य है<math>\chi</math>-बाउंडेड अगर कोई फंक्शन है <math>c</math> जैसे कि रेखांकन <math>G</math> में <math>\mathcal{F}</math> ज्यादा से ज्यादा रंगा जा सकता है <math>c(\omega(G))</math> रंग, सही रेखांकन | अधिक सामान्यतः एक परिवार <math>\mathcal{F}</math> रेखांकन का Χ-बाध्य है<math>\chi</math>-बाउंडेड अगर कोई फंक्शन है <math>c</math> जैसे कि रेखांकन <math>G</math> में <math>\mathcal{F}</math> ज्यादा से ज्यादा रंगा जा सकता है <math>c(\omega(G))</math> रंग, सही रेखांकन <math>c(\omega(G))=\omega(G)</math>के परिवार के लिए यह कार्य है . | ||
2-रंगीन ग्राफ़ वास्तव में द्विदलीय ग्राफ़ हैं, जिनमें वृक्ष (ग्राफ़ सिद्धांत) और वन सम्मिलित हैं। | 2-रंगीन ग्राफ़ वास्तव में द्विदलीय ग्राफ़ हैं, जिनमें वृक्ष (ग्राफ़ सिद्धांत) और वन सम्मिलित हैं। | ||
| Line 103: | Line 100: | ||
चार रंग प्रमेय के अनुसार, प्रत्येक प्लानर ग्राफ 4-रंगों का हो सकता है। | चार रंग प्रमेय के अनुसार, प्रत्येक प्लानर ग्राफ 4-रंगों का हो सकता है। | ||
एक [[लालची रंग]] दिखाता है कि प्रत्येक ग्राफ को अधिकतम शीर्ष [[डिग्री (ग्राफ सिद्धांत)]] की तुलना में एक और रंग से रंगा जा सकता है। | एक [[लालची रंग|लोभी रंग]] दिखाता है कि प्रत्येक ग्राफ को अधिकतम शीर्ष [[डिग्री (ग्राफ सिद्धांत)]] की तुलना में एक और रंग से रंगा जा सकता है। | ||
: <math>\chi(G) \le \Delta(G) + 1. </math> | : <math>\chi(G) \le \Delta(G) + 1. </math> | ||
पूरा रेखांकन है <math>\chi(G)=n</math> और <math>\Delta(G)=n-1</math>, और [[विषम चक्र]] हैं <math>\chi(G)=3</math> और <math>\Delta(G)=2</math>, इसलिए इन ग्राफ़ के लिए यह बाउंड सर्वोत्तम संभव है। अन्य सभी मामलों में, सीमा में थोड़ा सुधार किया जा सकता है; ब्रूक्स प्रमेय<ref>{{harvtxt|Brooks|1941}}</ref> बताता है | पूरा रेखांकन है <math>\chi(G)=n</math> और <math>\Delta(G)=n-1</math>, और [[विषम चक्र]] हैं <math>\chi(G)=3</math> और <math>\Delta(G)=2</math>, इसलिए इन ग्राफ़ के लिए यह बाउंड सर्वोत्तम संभव है। अन्य सभी मामलों में, सीमा में थोड़ा सुधार किया जा सकता है; ब्रूक्स प्रमेय<ref>{{harvtxt|Brooks|1941}}</ref> बताता है | ||
: ब्रूक्स प्रमेय:<math>\chi (G) \le \Delta (G) </math> एक जुड़े हुए, सरल ग्राफ़ G के लिए, जब तक कि G एक पूर्ण ग्राफ़ या विषम चक्र न हो। | : ब्रूक्स प्रमेय:<math>\chi (G) \le \Delta (G) </math> एक जुड़े हुए, सरल ग्राफ़ G के लिए, जब तक कि G एक पूर्ण ग्राफ़ या विषम चक्र न हो। | ||
| Line 117: | Line 115: | ||
: <math> \chi_H(G)\leq \chi(G).</math> | : <math> \chi_H(G)\leq \chi(G).</math> | ||
{{vanchor|वेक्टर रंगीन संख्या}}: होने देना <math>W</math> एक | {{vanchor|वेक्टर रंगीन संख्या}}: होने देना <math>W</math> एक धनात्मक अर्ध-निश्चित मैट्रिक्स हो जैसे कि <math> W_{i,j} \le -\tfrac{1}{k-1} </math> जब कभी भी <math>(i,j) </math> में बढ़त है <math>G</math> परिभाषित करना <math>\chi_V(G)</math> कम से कम k जिसके लिए <math>W</math> ऐसा मैट्रिक्स उपस्थित हो तब: | ||
: <math> \chi_V(G)\leq \chi(G).</math> | : <math> \chi_V(G)\leq \chi(G).</math> | ||
लोवाज़ संख्या: एक पूरक ग्राफ की लोवाज़ संख्या भी रंगीन संख्या पर एक निचली सीमा है: | लोवाज़ संख्या: एक पूरक ग्राफ की लोवाज़ संख्या भी रंगीन संख्या पर एक निचली सीमा है: | ||
| Line 134: | Line 132: | ||
: प्रमेय (पॉल एर्डोस | एर्डोस): मनमाने ढंग से उच्च परिधि और रंगीन संख्या के ग्राफ उपस्थित हैं।<ref>{{citation | last = Erdős | first = Paul | author-link = Paul Erdős | journal = Canadian Journal of Mathematics | pages = 34–38 | title = Graph theory and probability | volume = 11 | year = 1959 | doi = 10.4153/CJM-1959-003-9| s2cid = 122784453 }}.</ref> | : प्रमेय (पॉल एर्डोस | एर्डोस): मनमाने ढंग से उच्च परिधि और रंगीन संख्या के ग्राफ उपस्थित हैं।<ref>{{citation | last = Erdős | first = Paul | author-link = Paul Erdős | journal = Canadian Journal of Mathematics | pages = 34–38 | title = Graph theory and probability | volume = 11 | year = 1959 | doi = 10.4153/CJM-1959-003-9| s2cid = 122784453 }}.</ref> | ||
=== रंगीन सूचकांक पर सीमा === | === रंगीन सूचकांक पर सीमा === | ||
जी का किनारा रंग इसके लाइन ग्राफ का शीर्ष रंग है <math>L(G)</math>, और इसके | जी का किनारा रंग इसके लाइन ग्राफ का शीर्ष रंग है <math>L(G)</math>, और इसके विपरीत, इस प्रकार | ||
:<math>\chi'(G)=\chi(L(G)). </math> | :<math>\chi'(G)=\chi(L(G)). </math> | ||
| Line 158: | Line 156: | ||
*यदि कोई ग्राफ़ प्रत्येक ''n'' ≥ ''n''<sub>0</sub> के लिए पूर्ण n-रंग स्वीकार करता है, यह एक अनंत पूर्ण रंग को स्वीकार करता है {{harv|Fawcett|1978}}. | *यदि कोई ग्राफ़ प्रत्येक ''n'' ≥ ''n''<sub>0</sub> के लिए पूर्ण n-रंग स्वीकार करता है, यह एक अनंत पूर्ण रंग को स्वीकार करता है {{harv|Fawcett|1978}}. | ||
=== | === प्रारंभिक समस्याएं === | ||
जैसा कि ऊपर कहा, <math> \omega(G) \le \chi(G) \le \Delta(G) + 1. </math> 1998 से रीड का एक अनुमान यह है कि मूल्य अनिवार्य रूप से निचली सीमा के करीब है, | जैसा कि ऊपर कहा, <math> \omega(G) \le \chi(G) \le \Delta(G) + 1. </math> 1998 से रीड का एक अनुमान यह है कि मूल्य अनिवार्य रूप से निचली सीमा के करीब है, | ||
<math> \chi(G) \le \left\lceil \frac{\omega(G) + \Delta(G) + 1}{2} \right\rceil. </math> | <math> \chi(G) \le \left\lceil \frac{\omega(G) + \Delta(G) + 1}{2} \right\rceil. </math> | ||
| Line 220: | Line 218: | ||
}} | }} | ||
=== बहुपद समय === | === बहुपद समय === | ||
यह निर्धारित करना कि क्या एक ग्राफ को 2 रंगों से रंगा जा सकता है, यह निर्धारित करने के बराबर है कि क्या ग्राफ एक द्विदलीय ग्राफ है, और इस प्रकार रैखिक समय में या तो चौड़ाई-प्रथम खोज या गहराई-प्रथम खोज का उपयोग करता है। गणना की जा सकती है। जा सकता है। जा सकता है। अधिक | यह निर्धारित करना कि क्या एक ग्राफ को 2 रंगों से रंगा जा सकता है, यह निर्धारित करने के बराबर है कि क्या ग्राफ एक द्विदलीय ग्राफ है, और इस प्रकार रैखिक समय में या तो चौड़ाई-प्रथम खोज या गहराई-प्रथम खोज का उपयोग करता है। गणना की जा सकती है। जा सकता है। जा सकता है। अधिक सामान्यतः, रंग संख्या की गणना और सही ग्राफ़ के संबंधित रंग बहुपद समय में अर्द्ध-निश्चित प्रोग्रामिंग का उपयोग करके किया जा सकता है। रंगीन बहुपदों के लिए बंद-रूप अभिव्यक्तियां कई वर्गों के रेखांकन के लिए जानी जाती हैं, जैसे कि वनों, राग रेखांकन, वृत्त, पहिए और सीढ़ी, इसलिए इनका मूल्यांकन बहुपद समय में किया जा सकता है। | ||
यदि ग्राफ़ प्लानर है और कम शाखा-चौड़ाई है (या गैर-प्लानर है लेकिन ज्ञात शाखा अपघटन के साथ), तो इसे गतिशील प्रोग्रामिंग का उपयोग करके बहुपद समय में हल किया जा सकता है। सामान्य तौर पर, आवश्यक समय ग्राफ़ आकार में बहुपद होता है, लेकिन शाखा-चौड़ाई में घातीय होता है। | यदि ग्राफ़ प्लानर है और कम शाखा-चौड़ाई है (या गैर-प्लानर है लेकिन ज्ञात शाखा अपघटन के साथ), तो इसे गतिशील प्रोग्रामिंग का उपयोग करके बहुपद समय में हल किया जा सकता है। सामान्य तौर पर, आवश्यक समय ग्राफ़ आकार में बहुपद होता है, लेकिन शाखा-चौड़ाई में घातीय होता है। | ||
| Line 239: | Line 237: | ||
जहाँ u और v आसन्न शीर्ष हैं, और <math>G-uv</math> किनारे के साथ ग्राफ है {{mvar|uv}} निकाला गया। <math>P(G - uv, k)</math> ग्राफ़ के संभावित उचित रंगों की संख्या का प्रतिनिधित्व करता है, जहाँ शीर्षों में समान या भिन्न रंग हो सकते हैं। फिर दो अलग-अलग ग्राफों से उचित रंग उत्पन्न होते हैं। व्याख्या करने के लिए, यदि शीर्षों u और v के अलग-अलग रंग हैं, तो हम एक ग्राफ़ पर भी विचार कर सकते हैं जहाँ u और v आसन्न हैं। यदि यू और वी के समान रंग हैं, तो हम एक ग्राफ पर भी विचार कर सकते हैं जहां यू और वी अनुबंधित हैं। टुट्टे की जिज्ञासा जिसके बारे में अन्य ग्राफ गुण इस पुनरावृत्ति को संतुष्ट करते हैं, ने उन्हें रंगीन बहुपद, टुट्टे बहुपद के द्विभाजित सामान्यीकरण की खोज करने के लिए प्रेरित किया। | जहाँ u और v आसन्न शीर्ष हैं, और <math>G-uv</math> किनारे के साथ ग्राफ है {{mvar|uv}} निकाला गया। <math>P(G - uv, k)</math> ग्राफ़ के संभावित उचित रंगों की संख्या का प्रतिनिधित्व करता है, जहाँ शीर्षों में समान या भिन्न रंग हो सकते हैं। फिर दो अलग-अलग ग्राफों से उचित रंग उत्पन्न होते हैं। व्याख्या करने के लिए, यदि शीर्षों u और v के अलग-अलग रंग हैं, तो हम एक ग्राफ़ पर भी विचार कर सकते हैं जहाँ u और v आसन्न हैं। यदि यू और वी के समान रंग हैं, तो हम एक ग्राफ पर भी विचार कर सकते हैं जहां यू और वी अनुबंधित हैं। टुट्टे की जिज्ञासा जिसके बारे में अन्य ग्राफ गुण इस पुनरावृत्ति को संतुष्ट करते हैं, ने उन्हें रंगीन बहुपद, टुट्टे बहुपद के द्विभाजित सामान्यीकरण की खोज करने के लिए प्रेरित किया। | ||
ये भाव विलोपन-संकुचन एल्गोरिथम नामक एक पुनरावर्ती प्रक्रिया को जन्म देते हैं, जो ग्राफ़ रंग के लिए कई एल्गोरिदम का आधार बनाती है। चलने का समय [[फाइबोनैचि संख्या]] | ये भाव विलोपन-संकुचन एल्गोरिथम नामक एक पुनरावर्ती प्रक्रिया को जन्म देते हैं, जो ग्राफ़ रंग के लिए कई एल्गोरिदम का आधार बनाती है। चलने का समय [[फाइबोनैचि संख्या|फाइबोनैचि संख्यााओं]] के समान पुनरावृत्ति संबंध को संतुष्ट करता है, इसलिए सबसे खराब स्थिति में एल्गोरिदम बहुपद कारक के भीतर समय पर चलता है <math>\left(\tfrac{1+\sqrt{5}}2\right)^{n+m}=O(1.6180^{n+m})</math> n शीर्षों और m किनारों के लिए।<ref>{{harvtxt|Wilf|1986}}</ref> संख्या के एक बहुपद कारक के भीतर विश्लेषण <math>t(G)</math> इनपुट ग्राफ के फैले हुए (गणित) में सुधार किया जा सकता है।<ref>{{harvtxt|Sekine|Imai|Tani|1995}}</ref> अभ्यास में, कुछ पुनरावर्ती कॉलों से बचने के लिए शाखा और बाध्य रणनीतियों और समरूपता अस्वीकृति को नियोजित किया जाता है। रनिंग टाइम वर्टेक्स पेयर को चुनने के लिए उपयोग किए गए ह्यूरिस्टिक पर निर्भर करता है। | ||
=== लोभी रंग === | === लोभी रंग === | ||
{{Main|लोभी रंग}} | {{Main|लोभी रंग}} | ||
[[File:Greedy colourings.svg|thumb|right|अलग-अलग वर्टेक्स ऑर्डर का उपयोग करते हुए एक ही ग्राफ के दो | [[File:Greedy colourings.svg|thumb|right|अलग-अलग वर्टेक्स ऑर्डर का उपयोग करते हुए एक ही ग्राफ के दो लोभी रंग। सही उदाहरण एन कोने के साथ 2-रंगीन ग्राफों को सामान्यीकृत करता है, जहां लालची एल्गोरिदम खर्च करता है <math>n/2</math> रंग की।]]लालची एल्गोरिथ्म एक विशिष्ट क्रम में कोने पर विचार करता है <math>v_1</math>,…,<math> v_n</math> और असाइन करता है <math>v_i</math> सबसे छोटा उपलब्ध रंग जिसका उपयोग नहीं किया गया <math>v_i</math>के पड़ोसियों में <math>v_1</math>,…,<math> v_{i-1}</math>, यदि आवश्यक हो तो एक नया रंग जोड़ना। परिणामी रंग की गुणवत्ता चुने हुए क्रम पर निर्भर करती है। एक आदेश उपस्थित है जो इष्टतम संख्या के साथ एक लोभी रंग की ओर जाता है <math>\chi(G)</math> रंग की। दूसरी ओर, लोभी रंग मनमाने ढंग से खराब हो सकते हैं; उदाहरण के लिए, n शीर्षों पर [[क्राउन ग्राफ]] 2-रंग का हो सकता है, लेकिन इसमें एक क्रम है जो एक लोभी रंग की ओर जाता है <math>n/2</math> रंग की। | ||
[[कॉर्डल ग्राफ]] के लिए, और कॉर्डल ग्राफ़ के विशेष मामलों जैसे कि [[अंतराल ग्राफ]] और [[उदासीनता ग्राफ]] के लिए, | [[कॉर्डल ग्राफ]] के लिए, और कॉर्डल ग्राफ़ के विशेष मामलों जैसे कि [[अंतराल ग्राफ]] और [[उदासीनता ग्राफ]] के लिए, लोभी रंग एल्गोरिथ्म का उपयोग बहुपद समय में इष्टतम रंग खोजने के लिए किया जा सकता है, वर्टेक्स ऑर्डरिंग को [[पूर्ण उन्मूलन आदेश]] के रिवर्स होने के लिए चुनकर। ग्राफ। पूरी तरह से ऑर्डर करने योग्य ग्राफ इस संपत्ति को सामान्यीकृत करते हैं, लेकिन इन ग्राफों का सही क्रम खोजना एनपी-हार्ड है। | ||
यदि शीर्षों को उनकी डिग्री (ग्राफ़ सिद्धांत) के अनुसार क्रमबद्ध किया जाता है, तो परिणामी | |||