आंशिक रंग

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}}$ |

रैखिक प्रोग्रामन (LP) सूत्रण

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

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

जो प्रत्येक शीर्ष x के लिए

$\sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1$ अगर है।

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

अनुप्रयोग

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

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

अधिक वास्तविक शब्दों में, G का प्रत्येक बिंदु तार रहित संचार नेटवर्क में एक रेडियो प्रसारण को निरूपित कर सकता है; 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.

यह भी देखें

• आंशिक मिलान

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