आंशिक रंग

5:2-द्वादशफलकी ग्राफ का रंग। A 4:2-इस ग्राफ का रंग उपस्थित नहीं है।

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

भिन्नात्मक ग्राफ रंग को पारंपरिक ग्राफ रंग के रैखिक प्रोग्रामिंग विश्रांति (रीलैक्सेशन) के रूप में देखा जा सकता है। निश्चित रूप से, आंशिक रंग की समस्याएं पारंपरिक रंग की समस्याओं की तुलना में रैखिक प्रोग्रामिंग दृष्टिकोण के लिए अधिक उत्तरदायी हैं।

परिभाषाएँ

ऊपर: 3:1-चक्र के 5 शीर्षों पर रंग, और संगत 6:2-रंग।
नीचे: एक 5:2 एक ही ग्राफ का रंग।

ग्राफ G का एक b-गुना रंग एक ग्राफ के शीर्षों के आकार b के समुच्चयों का एक नियतन (असाइनमेंट) है जैसे कि आसन्न शीर्ष अलग-अलग समुच्चय प्राप्त करते हैं। a:b-रंग उपलब्ध रंगों में से एक b-गुना रंग है। तुल्यतः, इसे केनेसर ग्राफ KG_a,b के समरूपता के रूप में परिभाषित किया जा सकता है। b-गुना रंगीन संख्या $\chi _{b}(G)$ कम से कम ऐसा है कि a:b-रंग उपस्थित है।

आंशिक रंगीन संख्या $\chi _{f}(G)$ को परिभाषित किया गया है

$\chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}$

ध्यान दें कि सीमा उपस्थित है क्योंकि $\chi _{b}(G)$ सबएडिटिव है, जिसका अर्थ है $\chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G)$ है | आंशिक रंगीन संख्या को तुल्यतः प्रायिकतात्मक पदों में परिभाषित किया जा सकता है। $\chi _{f}(G)$ सामान्य k है जिसके लिए G के स्वतंत्र समुच्चयों पर एक प्रायिकता वितरण उपस्थित है जैसे कि प्रत्येक शीर्ष v के लिए, वितरण से लिया गया एक स्वतंत्र समुच्चय S दिया गया है,

$\Pr(v\in S)\geq {\frac {1}{k}}.$

गुण

अपने पास

$\chi _{f}(G)\geq {\frac {n(G)}{\alpha (G)}},$

शीर्ष-सकर्मक रेखांकन के लिए समानता के साथ, जहाँ n(G) ग्राफ सिद्धांत की शब्दावली है #G की मूल बातें, α(G) स्वतंत्रता संख्या है। इसके अतिरिक्त,

$\omega (G)\leq \chi _{f}(G)\leq \chi (G),$

जहां ω(G) क्लिक संख्या है, और $\chi (G)$ वर्णक्रमीय संख्या है।

इसके अलावा, भिन्नात्मक रंगीन संख्या एक लघुगणक कारक के भीतर रंगीन संख्या का अनुमान लगाती है, वास्तव में:

${\frac {\chi (G)}{1+\ln \alpha (G)}}\leq \chi _{f}(G)\leq {\frac {\chi _{b}(G)}{b}}\leq \chi (G).$

केनेसर रेखांकन उदाहरण देते हैं जहां $\chi (G)/\chi _{f}(G)$ मनमाने ढंग से बड़ा है, क्योंकि $\chi (KG_{m,n})=m-2n+2,$ जबकि $\chi _{f}(KG_{m,n})={\tfrac {m}{n}}.$

रैखिक प्रोग्रामिंग (एलपी) सूत्रीकरण

आंशिक रंगीन संख्या $\chi _{f}(G)$ एक ग्राफ जी का एक रैखिक प्रोग्रामिंग के समाधान के रूप में प्राप्त किया जा सकता है। होने देना ${\mathcal {I}}(G)$ जी के सभी स्वतंत्र सेटों का सेट बनें, और दें ${\mathcal {I}}(G,x)$ उन सभी स्वतंत्र समुच्चयों का समुच्चय हो जिनमें शीर्ष x शामिल हो। प्रत्येक स्वतंत्र सेट I के लिए, एक गैर-ऋणात्मक वास्तविक चर x परिभाषित करें_I. तब $\chi _{f}(G)$ का न्यूनतम मान है

$\sum _{I\in {\mathcal {I}}(G)}x_{I},$

का विषय है

$\sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1$ प्रत्येक शीर्ष के लिए $x$.

इस रेखीय कार्यक्रम की दोहरी समस्या भिन्नात्मक क्लिक संख्या की गणना करती है, जो कि क्लिक संख्या की पूर्णांक अवधारणा के परिमेय के लिए एक छूट है। अर्थात्, G के शीर्षों का भार इस प्रकार है कि किसी भी स्वतंत्र सेट को सौंपा गया कुल भार अधिक से अधिक 1 है। रैखिक प्रोग्रामिंग का प्रबल द्वैत प्रमेय यह गारंटी देता है कि दोनों रैखिक कार्यक्रमों के इष्टतम समाधानों का मान समान है। हालांकि ध्यान दें कि प्रत्येक रेखीय कार्यक्रम का आकार हो सकता है जो जी के कोने की संख्या में घातीय है, और यह कि ग्राफ के भिन्नात्मक रंगीन संख्या की गणना एनपी कठिन है। यह एक ग्राफ के किनारों को आंशिक रूप से रंगने की समस्या के विपरीत है, जिसे बहुपद समय में हल किया जा सकता है। यह एडमंड्स के मैचिंग पॉलीटॉप प्रमेय का सीधा परिणाम है।

अनुप्रयोग

भिन्नात्मक ग्राफ कलरिंग के अनुप्रयोगों में गतिविधि शेड्यूलिंग शामिल है। इस मामले में, ग्राफ जी एक संघर्ष ग्राफ है: नोड्स यू और वी के बीच जी में एक किनारा दर्शाता है कि यू और वी एक साथ सक्रिय नहीं हो सकते हैं। अन्यथा रखो, नोड्स का सेट जो एक साथ सक्रिय हैं, ग्राफ जी में एक स्वतंत्र सेट होना चाहिए।

जी में रंग भरने वाला एक इष्टतम भिन्नात्मक ग्राफ एक कम से कम संभव शेड्यूल प्रदान करता है, जैसे कि प्रत्येक नोड कुल मिलाकर (कम से कम) 1 समय इकाई के लिए सक्रिय है, और किसी भी समय सक्रिय नोड्स का सेट एक स्वतंत्र सेट है। यदि हमारे पास उपरोक्त रेखीय कार्यक्रम के लिए एक समाधान x है, तो हम सभी स्वतंत्र सेट I को मनमाने क्रम में पार करते हैं। प्रत्येक I के लिए, हम I में नोड्स को सक्रिय होने देते हैं $x_{I}$ समय इकाइयाँ; इस बीच, I में नहीं प्रत्येक नोड निष्क्रिय है।

अधिक ठोस शब्दों में, G का प्रत्येक नोड वायरलेस संचार नेटवर्क में एक रेडियो प्रसारण का प्रतिनिधित्व कर सकता है; जी के किनारे रेडियो प्रसारण के बीच हस्तक्षेप का प्रतिनिधित्व करते हैं। कुल 1 समय इकाई के लिए प्रत्येक रेडियो प्रसारण को सक्रिय होने की आवश्यकता है; एक इष्टतम आंशिक ग्राफ रंग एक न्यूनतम-लंबाई शेड्यूल (या, समकक्ष, एक अधिकतम-बैंडविड्थ शेड्यूल) प्रदान करता है जो संघर्ष-मुक्त है।

पारंपरिक ग्राफ रंग के साथ तुलना

यदि एक और आवश्यकता है कि प्रत्येक नोड को 1 समय इकाई के लिए लगातार सक्रिय होना चाहिए (इसे बंद किए बिना और हर बार चालू किए बिना), तो पारंपरिक ग्राफ़ शीर्ष रंग एक इष्टतम शेड्यूल प्रदान करेगा: पहले रंग 1 के नोड 1 समय के लिए सक्रिय हैं इकाई, तो रंग 2 के नोड 1 समय इकाई के लिए सक्रिय हैं, और इसी तरह। दोबारा, किसी भी समय, सक्रिय नोड्स का सेट एक स्वतंत्र सेट है।

सामान्य तौर पर, आंशिक ग्राफ रंग गैर-आंशिक ग्राफ रंग की तुलना में एक छोटा शेड्यूल प्रदान करता है; एक अभिन्नता अंतर है। उपकरणों (जैसे रेडियो ट्रांसमीटर) को एक से अधिक बार चालू और बंद करने की कीमत पर एक छोटा शेड्यूल खोजना संभव हो सकता है।

संदर्भ

• 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.

यह भी देखें

• आंशिक मिलान

श्रेणी:ग्राफ़ रंग