आंशिक रंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Graph coloring where graph elements are assigned sets of colors}} | {{Short description|Graph coloring where graph elements are assigned sets of colors}} | ||
[[Image:Graph fractional coloring.svg|right|thumb| 5:2-द्वादशफलकी ग्राफ का रंग। A 4:2-इस ग्राफ का रंग उपस्थित नहीं है।]]'''आंशिक रंग''' [[ग्राफ सिद्धांत]] की एक नयी (यंग) शाखा में एक विषय है जिसे [[भिन्नात्मक ग्राफ सिद्धांत]] के रूप में जाना जाता है। यह साधारण [[ग्राफ रंग]] का एक सामान्यीकरण है। एक पारंपरिक ग्राफ़ रंग में, ग्राफ़ में प्रत्येक शीर्ष को कुछ रंग निर्दिष्ट किया जाता है, और आसन्न शीर्ष- जो किनारों से जुड़े होते हैं - को अलग-अलग रंग निर्दिष्ट किए जाने चाहिए। एक | [[Image:Graph fractional coloring.svg|right|thumb| 5:2-द्वादशफलकी ग्राफ का रंग। A 4:2-इस ग्राफ का रंग उपस्थित नहीं है।]]'''आंशिक रंग''' [[ग्राफ सिद्धांत]] की एक नयी (यंग) शाखा में एक विषय है जिसे [[भिन्नात्मक ग्राफ सिद्धांत|आंशिक ग्राफ सिद्धांत]] के रूप में जाना जाता है। यह साधारण [[ग्राफ रंग]] का एक सामान्यीकरण है। एक पारंपरिक ग्राफ़ रंग में, ग्राफ़ में प्रत्येक शीर्ष को कुछ रंग निर्दिष्ट किया जाता है, और आसन्न शीर्ष- जो किनारों से जुड़े होते हैं - को अलग-अलग रंग निर्दिष्ट किए जाने चाहिए। एक आंशिक रंग में हालांकि, रंगों के एक समुच्चय ग्राफ़ के प्रत्येक शीर्ष पर निर्दिष्ट किया जाता है। आसन्न शीर्षों की आवश्यकता अभी भी बनी हुई है, इसलिए यदि दो शीर्षों को एक किनारे से जोड़ा जाता है, तो उनमें कोई रंग उभयनिष्ठ नहीं होना चाहिए। | ||
[[आंशिक]] [[ग्राफ रंग]] को पारंपरिक ग्राफ रंग के [[रैखिक प्रोग्रामिंग विश्रांति|रैखिक प्रोग्रामन विश्रांति]] (रीलैक्सेशन) के रूप में देखा जा सकता है। निश्चित रूप से, आंशिक रंग की समस्याएं पारंपरिक रंग की समस्याओं की तुलना में रैखिक प्रोग्रामन दृष्टिकोण के लिए अधिक उत्तरदायी हैं। | |||
== परिभाषाएँ == | == परिभाषाएँ == | ||
[[File:Fractional coloring of C5.png|thumb|ऊपर: 3:1-चक्र के 5 शीर्षों पर रंग, और संगत 6:2-रंग।<br />नीचे: एक 5:2 एक ही ग्राफ का रंग।]]ग्राफ ''G'' का एक '''''b''-गुना रंग''' एक ग्राफ के शीर्षों के आकार ''b'' के समुच्चयों का एक नियतन (असाइनमेंट) है जैसे कि आसन्न शीर्ष अलग-अलग समुच्चय प्राप्त करते हैं। '''a:b-रंग''' उपलब्ध रंगों में से एक b-गुना रंग है। तुल्यतः, इसे [[केनेसर ग्राफ]] {{math|''KG''<sub>''a'',''b''</sub>}} | [[File:Fractional coloring of C5.png|thumb|ऊपर: 3:1-चक्र के 5 शीर्षों पर रंग, और संगत 6:2-रंग।<br />नीचे: एक 5:2 एक ही ग्राफ का रंग।]]ग्राफ ''G'' का एक '''''b''-गुना रंग''' एक ग्राफ के शीर्षों के आकार ''b'' के समुच्चयों का एक नियतन (असाइनमेंट) है जैसे कि आसन्न शीर्ष अलग-अलग समुच्चय प्राप्त करते हैं। '''a:b-रंग''' उपलब्ध रंगों में से एक b-गुना रंग है। तुल्यतः, इसे [[केनेसर ग्राफ]] {{math|''KG''<sub>''a'',''b''</sub>}} की समरूपता के रूप में परिभाषित किया जा सकता है। '''''b''-गुना रंगीन संख्या''' <math>\chi_b(G)</math> कम से कम ऐसा है कि a:b-रंग उपस्थित है। | ||
'''आंशिक रंगीन संख्या''' <math>\chi_f(G)</math> को परिभाषित किया गया है | '''आंशिक रंगीन संख्या''' <math>\chi_f(G)</math> को परिभाषित किया गया है | ||
:<math>\chi_{f}(G) = \lim_{b \to \infty}\frac{\chi_{b}(G)}{b} = \inf_{b}\frac{\chi_{b}(G)}{b}</math> | :<math>\chi_{f}(G) = \lim_{b \to \infty}\frac{\chi_{b}(G)}{b} = \inf_{b}\frac{\chi_{b}(G)}{b}</math> | ||
ध्यान दें कि सीमा उपस्थित है क्योंकि <math>\chi_b(G)</math> सबएडिटिव है, जिसका अर्थ है <math>\chi_{a+b}(G) \le \chi_a(G) + \chi_b(G) </math> है | आंशिक रंगीन संख्या को तुल्यतः प्रायिकतात्मक पदों में परिभाषित किया जा सकता है। <math>\chi_f(G)</math> सामान्य k है जिसके लिए G के [[स्वतंत्र सेट (ग्राफ सिद्धांत)|स्वतंत्र समुच्चयों]] पर एक प्रायिकता वितरण उपस्थित है जैसे कि प्रत्येक शीर्ष v के लिए, वितरण से लिया गया एक स्वतंत्र समुच्चय S दिया गया है, | ध्यान दें कि सीमा उपस्थित है क्योंकि <math>\chi_b(G)</math> सहायक (''सबएडिटिव'' ) है, जिसका अर्थ है <math>\chi_{a+b}(G) \le \chi_a(G) + \chi_b(G) </math> है | आंशिक रंगीन संख्या को तुल्यतः प्रायिकतात्मक पदों में परिभाषित किया जा सकता है। <math>\chi_f(G)</math> सामान्य ''k'' है जिसके लिए G के [[स्वतंत्र सेट (ग्राफ सिद्धांत)|स्वतंत्र समुच्चयों]] पर एक प्रायिकता वितरण उपस्थित है जैसे कि प्रत्येक शीर्ष v के लिए, वितरण से लिया गया एक स्वतंत्र समुच्चय S दिया गया है, | ||
:<math>\Pr(v\in S) \geq \frac{1}{k}.</math> | :<math>\Pr(v\in S) \geq \frac{1}{k}.</math> | ||
| Line 19: | Line 19: | ||
:<math>\chi_f(G)\ge \frac{n(G)}{\alpha(G)},</math> | :<math>\chi_f(G)\ge \frac{n(G)}{\alpha(G)},</math> | ||
[[शीर्ष-संक्रामक ग्राफों]] के लिए समिका के साथ, जहाँ n(G) G की कोटि है, α(G) [[स्वतंत्रता संख्या]] है।<ref>{{Cite book |title=आंशिक ग्राफ सिद्धांत, रेखांकन के सिद्धांत के लिए एक तर्कसंगत दृष्टिकोण|publisher=Dover Publication |year=2013 |isbn=978-0486485935 |page=42 |first1=Edward R. |last1=Scheinerman |first2=Daniel H. |last2=Ullman}}, Proposition 3.1.1.</ref> | [[शीर्ष-संक्रामक ग्राफों]] के लिए समिका के साथ, जहाँ ''n(G) G'' की कोटि है, ''α(G)'' [[स्वतंत्रता संख्या|स्वतंत्रत संख्या]] है।<ref>{{Cite book |title=आंशिक ग्राफ सिद्धांत, रेखांकन के सिद्धांत के लिए एक तर्कसंगत दृष्टिकोण|publisher=Dover Publication |year=2013 |isbn=978-0486485935 |page=42 |first1=Edward R. |last1=Scheinerman |first2=Daniel H. |last2=Ullman}}, Proposition 3.1.1.</ref> | ||
इसके अतिरिक्त, | इसके अतिरिक्त, | ||
| Line 25: | Line 25: | ||
जहां ω(G) [[क्लिक संख्या]] है, और <math>\chi(G)</math> [[रंगीन संख्या]] है। | जहां ω(G) [[क्लिक संख्या]] है, और <math>\chi(G)</math> [[रंगीन संख्या]] है। | ||
इसके अलावा, | इसके अलावा, [[आंशिक]] [[रंगीन संख्या]] एक लघुगणकीय गुणक के अंदर रंगीन संख्या का सन्निकट है,<ref>[[László Lovász]]: "[https://dx.doi.org/10.1016/0012-365X(75)90058-8 On the ratio of optimal integral and fractional covers]", Discrete Math. 13:4(1975), p. 383-390.</ref> वास्तव में: | ||
:<math>\frac{\chi(G)}{1+\ln \alpha(G)} \le \chi_f(G) \le \frac{\chi_b(G)}{b} \le \chi(G).</math> | :<math>\frac{\chi(G)}{1+\ln \alpha(G)} \le \chi_f(G) \le \frac{\chi_b(G)}{b} \le \chi(G).</math> | ||
| Line 32: | Line 32: | ||
== रैखिक | == रैखिक प्रोग्रामन (LP) सूत्रण == | ||
एक ग्राफ ''G की'' भिन्नात्मक रंगीन संख्या <math>\chi_f(G)</math> को एक रैखिक प्रोग्रामन के समाधान के रूप में प्राप्त किया जा सकता है। <math>\mathcal{I}(G)</math> को G के सभी स्वतंत्र समुच्चयों का समुच्चय होने दें, और <math>\mathcal{I}(G,x)</math> को उन सभी स्वतंत्र समुच्चयों का समुच्चय होने दें जिनमें शीर्ष ''x'' सम्मिलित है। प्रत्येक स्वतंत्र समुच्चय ''I'' के लिए, एक अऋणात्मक वास्तविक चर ''xI'' परिभाषित करें | तब <math>\chi_f(G)</math> का न्यूनतम मान | |||
: <math>\sum_{I\in\mathcal{I}(G)} x_I | : <math>\sum_{I\in\mathcal{I}(G)} x_I</math> है, | ||
जो प्रत्येक शीर्ष ''x'' के लिए | |||
:<math>\sum_{I\in\mathcal{I}(G,x)} x_I \ge 1</math> | :<math>\sum_{I\in\mathcal{I}(G,x)} x_I \ge 1</math> अगर है। | ||
इस रेखीय | इस रेखीय प्रोग्रामन का [[दोहरी समस्या|द्वैती]] <nowiki>''आंशिक क्लिक संख्या''</nowiki> की गणना करता है, [[क्लिक संख्या]] के पूर्णांक सिद्धान्त के परिमेय के लिए एक विश्रांति है। अर्थात्, G के शीर्षों का भार इस प्रकार है कि किसी भी स्वतंत्र समुच्चय को नियत किया गया कुल भार अधिक से अधिक 1 है। रैखिक प्रोग्रामन का [[प्रबल द्वैत]] प्रमेय यह गारंटी देता है कि दोनों रैखिक प्रोग्रामन के इष्टतम समाधान का मान समान है। हालांकि ध्यान दें कि प्रत्येक रेखीय प्रोग्रामन का आकार हो सकता है जो ''G'' के शीर्षों की संख्या में घातांकी है, और यह कि ग्राफ के आंशिक रंगीन संख्या की गणना [[एनपी-हार्ड]] है।<ref>[[Carsten Lund]] and [[Mihalis Yannakakis]]: "[https://dx.doi.org/10.1145/185675.306789 On the hardness of approximating minimization problems]", J. ACM 41:5(1994), p. 960-981.</ref> यह एक ग्राफ के किनारों को आंशिक रूप से रंगने की समस्या के विपरीत है, जिसे बहुपद समय में हल किया जा सकता है। यह एडमंड्स के सुमेलन पॉलीटॉप प्रमेय का स्पष्ट परिणाम है।<ref>{{Cite journal |doi = 10.1109/18.21215|title = बहुपद समय में लिंक शेड्यूलिंग|journal = IEEE Transactions on Information Theory|volume = 34|issue = 5|pages = 910–917|year = 1988|last1 = Hajek|first1 = B.|last2 = Sasaki|first2 = G.}}</ref><ref name=schrijver>{{cite book|last=Schrijver|first=Alexander|title=Combinatorial Optimization: Polyhedra and Efficiency|url=https://archive.org/details/combinatorialopt00asch|url-access=limited|year=2003|publisher=Springer-Verlag|location=Berlin ; Heidelberg ; New York, N.Y.|isbn=978-3540443896|pages=[https://archive.org/details/combinatorialopt00asch/page/n511 474]}}</ref> | ||
Revision as of 11:14, 16 May 2023
आंशिक रंग ग्राफ सिद्धांत की एक नयी (यंग) शाखा में एक विषय है जिसे आंशिक ग्राफ सिद्धांत के रूप में जाना जाता है। यह साधारण ग्राफ रंग का एक सामान्यीकरण है। एक पारंपरिक ग्राफ़ रंग में, ग्राफ़ में प्रत्येक शीर्ष को कुछ रंग निर्दिष्ट किया जाता है, और आसन्न शीर्ष- जो किनारों से जुड़े होते हैं - को अलग-अलग रंग निर्दिष्ट किए जाने चाहिए। एक आंशिक रंग में हालांकि, रंगों के एक समुच्चय ग्राफ़ के प्रत्येक शीर्ष पर निर्दिष्ट किया जाता है। आसन्न शीर्षों की आवश्यकता अभी भी बनी हुई है, इसलिए यदि दो शीर्षों को एक किनारे से जोड़ा जाता है, तो उनमें कोई रंग उभयनिष्ठ नहीं होना चाहिए।
आंशिक ग्राफ रंग को पारंपरिक ग्राफ रंग के रैखिक प्रोग्रामन विश्रांति (रीलैक्सेशन) के रूप में देखा जा सकता है। निश्चित रूप से, आंशिक रंग की समस्याएं पारंपरिक रंग की समस्याओं की तुलना में रैखिक प्रोग्रामन दृष्टिकोण के लिए अधिक उत्तरदायी हैं।
परिभाषाएँ
ग्राफ G का एक b-गुना रंग एक ग्राफ के शीर्षों के आकार b के समुच्चयों का एक नियतन (असाइनमेंट) है जैसे कि आसन्न शीर्ष अलग-अलग समुच्चय प्राप्त करते हैं। a:b-रंग उपलब्ध रंगों में से एक b-गुना रंग है। तुल्यतः, इसे केनेसर ग्राफ KGa,b की समरूपता के रूप में परिभाषित किया जा सकता है। b-गुना रंगीन संख्या कम से कम ऐसा है कि a:b-रंग उपस्थित है।
आंशिक रंगीन संख्या को परिभाषित किया गया है
ध्यान दें कि सीमा उपस्थित है क्योंकि सहायक (सबएडिटिव ) है, जिसका अर्थ है है | आंशिक रंगीन संख्या को तुल्यतः प्रायिकतात्मक पदों में परिभाषित किया जा सकता है। सामान्य k है जिसके लिए G के स्वतंत्र समुच्चयों पर एक प्रायिकता वितरण उपस्थित है जैसे कि प्रत्येक शीर्ष v के लिए, वितरण से लिया गया एक स्वतंत्र समुच्चय S दिया गया है,
गुण
अपने पास
शीर्ष-संक्रामक ग्राफों के लिए समिका के साथ, जहाँ n(G) G की कोटि है, α(G) स्वतंत्रत संख्या है।[1]
इसके अतिरिक्त,
जहां ω(G) क्लिक संख्या है, और रंगीन संख्या है।
इसके अलावा, आंशिक रंगीन संख्या एक लघुगणकीय गुणक के अंदर रंगीन संख्या का सन्निकट है,[2] वास्तव में:
केनेसर ग्राफ ऐसे उदाहरण देते हैं जहां स्वेच्छत रूप से बड़ा है, क्योंकि जबकि |
रैखिक प्रोग्रामन (LP) सूत्रण
एक ग्राफ G की भिन्नात्मक रंगीन संख्या को एक रैखिक प्रोग्रामन के समाधान के रूप में प्राप्त किया जा सकता है। को G के सभी स्वतंत्र समुच्चयों का समुच्चय होने दें, और को उन सभी स्वतंत्र समुच्चयों का समुच्चय होने दें जिनमें शीर्ष x सम्मिलित है। प्रत्येक स्वतंत्र समुच्चय I के लिए, एक अऋणात्मक वास्तविक चर xI परिभाषित करें | तब का न्यूनतम मान
- है,
जो प्रत्येक शीर्ष x के लिए
- अगर है।
इस रेखीय प्रोग्रामन का द्वैती ''आंशिक क्लिक संख्या'' की गणना करता है, क्लिक संख्या के पूर्णांक सिद्धान्त के परिमेय के लिए एक विश्रांति है। अर्थात्, G के शीर्षों का भार इस प्रकार है कि किसी भी स्वतंत्र समुच्चय को नियत किया गया कुल भार अधिक से अधिक 1 है। रैखिक प्रोग्रामन का प्रबल द्वैत प्रमेय यह गारंटी देता है कि दोनों रैखिक प्रोग्रामन के इष्टतम समाधान का मान समान है। हालांकि ध्यान दें कि प्रत्येक रेखीय प्रोग्रामन का आकार हो सकता है जो G के शीर्षों की संख्या में घातांकी है, और यह कि ग्राफ के आंशिक रंगीन संख्या की गणना एनपी-हार्ड है।[3] यह एक ग्राफ के किनारों को आंशिक रूप से रंगने की समस्या के विपरीत है, जिसे बहुपद समय में हल किया जा सकता है। यह एडमंड्स के सुमेलन पॉलीटॉप प्रमेय का स्पष्ट परिणाम है।[4][5]
अनुप्रयोग
भिन्नात्मक ग्राफ कलरिंग के अनुप्रयोगों में गतिविधि शेड्यूलिंग शामिल है। इस मामले में, ग्राफ जी एक संघर्ष ग्राफ है: नोड्स यू और वी के बीच जी में एक किनारा दर्शाता है कि यू और वी एक साथ सक्रिय नहीं हो सकते हैं। अन्यथा रखो, नोड्स का सेट जो एक साथ सक्रिय हैं, ग्राफ जी में एक स्वतंत्र सेट होना चाहिए।
जी में रंग भरने वाला एक इष्टतम भिन्नात्मक ग्राफ एक कम से कम संभव शेड्यूल प्रदान करता है, जैसे कि प्रत्येक नोड कुल मिलाकर (कम से कम) 1 समय इकाई के लिए सक्रिय है, और किसी भी समय सक्रिय नोड्स का सेट एक स्वतंत्र सेट है। यदि हमारे पास उपरोक्त रेखीय कार्यक्रम के लिए एक समाधान x है, तो हम सभी स्वतंत्र सेट I को मनमाने क्रम में पार करते हैं। प्रत्येक I के लिए, हम I में नोड्स को सक्रिय होने देते हैं समय इकाइयाँ; इस बीच, I में नहीं प्रत्येक नोड निष्क्रिय है।
अधिक ठोस शब्दों में, G का प्रत्येक नोड वायरलेस संचार नेटवर्क में एक रेडियो प्रसारण का प्रतिनिधित्व कर सकता है; जी के किनारे रेडियो प्रसारण के बीच हस्तक्षेप का प्रतिनिधित्व करते हैं। कुल 1 समय इकाई के लिए प्रत्येक रेडियो प्रसारण को सक्रिय होने की आवश्यकता है; एक इष्टतम आंशिक ग्राफ रंग एक न्यूनतम-लंबाई शेड्यूल (या, समकक्ष, एक अधिकतम-बैंडविड्थ शेड्यूल) प्रदान करता है जो संघर्ष-मुक्त है।
पारंपरिक ग्राफ रंग के साथ तुलना
यदि एक और आवश्यकता है कि प्रत्येक नोड को 1 समय इकाई के लिए लगातार सक्रिय होना चाहिए (इसे बंद किए बिना और हर बार चालू किए बिना), तो पारंपरिक ग्राफ़ शीर्ष रंग एक इष्टतम शेड्यूल प्रदान करेगा: पहले रंग 1 के नोड 1 समय के लिए सक्रिय हैं इकाई, तो रंग 2 के नोड 1 समय इकाई के लिए सक्रिय हैं, और इसी तरह। दोबारा, किसी भी समय, सक्रिय नोड्स का सेट एक स्वतंत्र सेट है।
सामान्य तौर पर, आंशिक ग्राफ रंग गैर-आंशिक ग्राफ रंग की तुलना में एक छोटा शेड्यूल प्रदान करता है; एक अभिन्नता अंतर है। उपकरणों (जैसे रेडियो ट्रांसमीटर) को एक से अधिक बार चालू और बंद करने की कीमत पर एक छोटा शेड्यूल खोजना संभव हो सकता है।
टिप्पणियाँ
- ↑ Scheinerman, Edward R.; Ullman, Daniel H. (2013). आंशिक ग्राफ सिद्धांत, रेखांकन के सिद्धांत के लिए एक तर्कसंगत दृष्टिकोण. Dover Publication. p. 42. ISBN 978-0486485935., Proposition 3.1.1.
- ↑ László Lovász: "On the ratio of optimal integral and fractional covers", Discrete Math. 13:4(1975), p. 383-390.
- ↑ Carsten Lund and Mihalis Yannakakis: "On the hardness of approximating minimization problems", J. ACM 41:5(1994), p. 960-981.
- ↑ Hajek, B.; Sasaki, G. (1988). "बहुपद समय में लिंक शेड्यूलिंग". IEEE Transactions on Information Theory. 34 (5): 910–917. doi:10.1109/18.21215.
- ↑ Schrijver, Alexander (2003). Combinatorial Optimization: Polyhedra and Efficiency. Berlin ; Heidelberg ; New York, N.Y.: Springer-Verlag. pp. 474. ISBN 978-3540443896.
संदर्भ
- Scheinerman, Edward R.; Ullman, Daniel H. (1997), Fractional graph theory, New York: Wiley-Interscience, ISBN 978-0-471-17864-4.
- Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, New York: Springer-Verlag, ISBN 978-0-387-95241-3.
यह भी देखें
श्रेणी:ग्राफ़ रंग
