बॉक्सिसिटी: Difference between revisions

From Vigyanwiki
m (Abhishek moved page बॉक्सिंग to बॉक्सिसिटी without leaving a redirect)
No edit summary
Line 1: Line 1:
{{Short description|Smallest dimension where a graph can be represented as an intersection graph of boxes}}
{{Short description|Smallest dimension where a graph can be represented as an intersection graph of boxes}}
[[File:Boxicity.svg|thumb|300px|आयतों का प्रतिच्छेदन ग्राफ, बॉक्सिकता दो के साथ]]ग्राफ थ्योरी में, बॉक्सिकिटी एक [[ ग्राफ अपरिवर्तनीय ]] है, जिसे 1969 में फ्रेड एस रॉबर्ट्स द्वारा पेश किया गया था।
[[File:Boxicity.svg|thumb|300px|आयतों का प्रतिच्छेदन ग्राफ, बॉक्सिकता दो के साथ]]ग्राफ थ्योरी में, बॉक्सिसिटी एक [[ ग्राफ अपरिवर्तनीय |ग्राफ अपरिवर्तनीय]] है, जिसे 1969 में फ्रेड एस रॉबर्ट्स द्वारा प्रवेशित किया गया था।


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


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


{{harvtxt|Roberts|1969}} ने दिखाया कि 2n सिरों पर एक पूर्ण ग्राफ़ से एक पूर्ण मिलान को हटाकर 2n कोने वाले ग्राफ़ में बॉक्सिकता बिल्कुल n है: डिस्कनेक्ट किए गए कोने के प्रत्येक जोड़े को उन बॉक्सों द्वारा दर्शाया जाना चाहिए जो एक दूसरे जोड़े की तुलना में एक अलग आयाम में अलग होते हैं। आयाम के साथ इस ग्राफ का एक बॉक्स प्रतिनिधित्व एन-डायमेंशनल [[ अतिविम ]] के प्रत्येक 2n पहलुओं को एक बॉक्स में मोटा करके पाया जा सकता है। इन परिणामों के कारण, इस ग्राफ को रॉबर्ट्स ग्राफ कहा गया है,<ref>E.g., see {{harvtxt|Chandran|Francis|Sivadasan|2010}} and  {{harvtxt|Chandran|Sivadasan|2007}}.</ref> हालाँकि इसे कॉकटेल पार्टी ग्राफ के रूप में जाना जाता है और इसे तूरान ग्राफ ''T''(2''n'',''n'') के रूप में भी समझा जा सकता है।
{{harvtxt|रॉबर्ट्स|1969}} ने दिखाया कि 2n सिरों पर एक पूर्ण ग्राफ़ से परिपूर्ण मिलान को हटाकर 2n कोने वाले ग्राफ़ में बॉक्सिकता यथार्थत: n है: असंबद्ध किए गए कोने के प्रत्येक जोड़े को उन बक्सों द्वारा दिखाया जाना चाहिए जो एक दूसरे जोड़े की तुलना में एक अलग आयाम में अलग होते हैं। आयाम के साथ इस ग्राफ का एक बक्से प्रतिनिधित्व एन-डायमेंशनल [[ अतिविम |अतिविम]] के प्रत्येक 2n पहलुओं को एक बक्से में मोटा करके पाया जा सकता है। इन परिणामों के कारण, इस ग्राफ को रॉबर्ट्स ग्राफ कहा गया है,<ref>E.g., see {{harvtxt|Chandran|Francis|Sivadasan|2010}} and  {{harvtxt|Chandran|Sivadasan|2007}}.</ref> हालाँकि इसे कॉकटेल पार्टी ग्राफ के रूप में जाना जाता है और इसे तूरान ग्राफ ''T''(2''n'',''n'') के रूप में भी समझा जा सकता है।


== अन्य ग्राफ वर्गों से संबंध ==
== अन्य ग्राफ वर्गों से संबंध ==
एक ग्राफ़ में बॉक्सिकिटी अधिक से अधिक एक होती है यदि और केवल यदि यह एक [[अंतराल ग्राफ]]़ है; मनमाना ग्राफ़ G की बॉक्सिकता अंतराल के समान सेट पर अंतराल ग्राफ़ की न्यूनतम संख्या है, जैसे कि अंतराल ग्राफ़ के किनारों के सेट का प्रतिच्छेदन G है। प्रत्येक बाहरी ग्राफ़ में अधिकतम दो पर बॉक्सिकिटी होती है,<ref>{{harvtxt|Scheinerman|1984}}.</ref> और प्रत्येक [[ प्लेनर ग्राफ ]] में अधिक से अधिक तीन में बॉक्सिकिटी होती है।<ref>{{harvtxt|Thomassen|1986}}.</ref>
एक ग्राफ़ में बॉक्सिसिटी अधिक से अधिक एक होती है यदि और केवल यदि यह एक [[अंतराल ग्राफ]]़ है; मनमाना ग्राफ़ G की बॉक्सिकता अंतराल के समान समुच्चय पर अंतराल ग्राफ़ की न्यूनतम संख्या है, जैसे कि अंतराल ग्राफ़ के किनारों के समुच्चय का प्रतिच्छेदन G है। प्रत्येक बाहरी ग्राफ़ में अधिकतम दो पर बॉक्सिसिटी होती है,<ref>{{harvtxt|Scheinerman|1984}}.</ref> और प्रत्येक [[ प्लेनर ग्राफ |प्लेनर ग्राफ]] में अधिक से अधिक तीन में बॉक्सिसिटी होती है।<ref>{{harvtxt|Thomassen|1986}}.</ref>
यदि एक द्विदलीय ग्राफ में बॉक्सिकिटी दो है, तो इसे विमान में अक्ष-समानांतर रेखा खंडों के प्रतिच्छेदन ग्राफ के रूप में दर्शाया जा सकता है।<ref>{{harvtxt|Bellantoni|Ben-Arroyo Hartman|Przytycka|Whitesides|1993}}.</ref>
यदि एक द्विदलीय ग्राफ में बॉक्सिसिटी दो है, तो इसे विमान में अक्ष-समानांतर रेखा खंडों के प्रतिच्छेदन ग्राफ के रूप में दिखाया जा सकता है।<ref>{{harvtxt|Bellantoni|Ben-Arroyo Hartman|Przytycka|Whitesides|1993}}.</ref>


{{harvtxt|Adiga|Bhowmick|Chandran|2011}} ने साबित किया कि द्विदलीय ग्राफ G की बॉक्सिकता ऊंचाई के [[आदेश आयाम]] के एक कारक 2 के भीतर है- दो आंशिक रूप से G से जुड़े सेट का आदेश इस प्रकार है: न्यूनतम तत्वों का सेट G के एक आंशिक सेट से मेल खाता है, का सेट अधिकतम तत्व G के दूसरे पक्षीय सेट से मेल खाते हैं, और दो तत्व तुलनीय हैं यदि संबंधित कोने G में आसन्न हैं। समान रूप से, ऊंचाई-दो [[आंशिक रूप से आदेशित सेट]] P का ऑर्डर आयाम तुलनात्मकता के बॉक्सिकता के कारक 2 के भीतर है P का ग्राफ (जो द्विदलीय है, चूँकि P की ऊँचाई दो है)।
{{harvtxt|Adiga|Bhowmick|Chandran|2011}} ने साबित किया कि द्विदलीय ग्राफ G की बॉक्सिकता ऊंचाई के [[आदेश आयाम]] के एक कारक 2 के भीतर है- दो आंशिक रूप से G से जुड़े समुच्चय का आदेश इस प्रकार है: न्यूनतम तत्वों का समुच्चय G के एक आंशिक समुच्चय से मेल खाता है, का समुच्चय अधिकतम तत्व G के दूसरे पक्षीय समुच्चय से मेल खाते हैं, और दो तत्व तुलनीय हैं यदि संबंधित कोने G में आसन्न हैं। समान रूप से, ऊंचाई-दो [[आंशिक रूप से आदेशित सेट|आंशिक रूप से आदेशित समुच्चय]] P का ऑर्डर आयाम तुलनात्मकता के बॉक्सिकता के कारक 2 के भीतर है P का ग्राफ (जो द्विदलीय है, चूँकि P की ऊँचाई दो है)।


== एल्गोरिथम परिणाम ==
== एल्गोरिथम परिणाम ==
कई ग्राफ़ समस्याओं को हल किया जा सकता है या बाउंड बॉक्सिकिटी वाले ग्राफ़ के लिए अन्य ग्राफ़ की तुलना में अधिक कुशलता से हल किया जा सकता है; उदाहरण के लिए, बाउंड बॉक्सिकिटी वाले ग्राफ़ के लिए बहुपद समय में अधिकतम क्लिक समस्या को हल किया जा सकता है।<ref>{{harvtxt|Chandran|Francis|Sivadasan|2010}} observe that this follows from the fact that these graphs have a polynomial number of [[maximal clique]]s. An explicit box representation is not needed to list all maximal cliques efficiently.</ref> कुछ अन्य ग्राफ़ समस्याओं के लिए, एक कम-आयामी बॉक्स प्रतिनिधित्व ज्ञात होने पर एक कुशल समाधान या सन्निकटन पाया जा सकता है।<ref>See, e.g., {{harvtxt|Agarwal|van Kreveld|Suri|1998}} and {{harvtxt|Berman|DasGupta|Muthukrishnan|Ramaswami|2001}} for approximations to the [[maximum independent set]] for intersection graphs of rectangles, and {{harvtxt|Chlebík|Chlebíková|2005}} for results on hardness of approximation of these problems in higher dimensions.</ref> हालाँकि, ऐसा प्रतिनिधित्व खोजना मुश्किल हो सकता है:
कई ग्राफ़ समस्याओं को हल किया जा सकता है या बाउंड बॉक्सिसिटी वाले ग्राफ़ के लिए अन्य ग्राफ़ की तुलना में अधिक कुशलता से हल किया जा सकता है; उदाहरण के लिए, बाउंड बॉक्सिसिटी वाले ग्राफ़ के लिए बहुपद समय में अधिकतम क्लिक समस्या को हल किया जा सकता है।<ref>{{harvtxt|Chandran|Francis|Sivadasan|2010}} observe that this follows from the fact that these graphs have a polynomial number of [[maximal clique]]s. An explicit box representation is not needed to list all maximal cliques efficiently.</ref> कुछ अन्य ग्राफ़ समस्याओं के लिए, एक कम-आयामी बक्से प्रतिनिधित्व ज्ञात होने पर एक कुशल समाधान या सन्निकटन पाया जा सकता है।<ref>See, e.g., {{harvtxt|Agarwal|van Kreveld|Suri|1998}} and {{harvtxt|Berman|DasGupta|Muthukrishnan|Ramaswami|2001}} for approximations to the [[maximum independent set]] for intersection graphs of rectangles, and {{harvtxt|Chlebík|Chlebíková|2005}} for results on hardness of approximation of these problems in higher dimensions.</ref> हालाँकि, ऐसा प्रतिनिधित्व खोजना मुश्किल हो सकता है:
यह परीक्षण करने के लिए एनपी-पूर्ण है कि क्या किसी दिए गए ग्राफ की बॉक्सिकता कुछ दिए गए मान K पर है, यहां तक ​​​​कि K = 2 के लिए भी।<ref>{{harvtxt|Cozzens|1981}} shows that computing the boxicity is NP-complete; {{harvtxt|Yannakakis|1982}} shows that even checking whether the boxicity is at most 3 is NP-hard; finally {{harvtxt|Kratochvil|1994}} showed that recognising boxicity 2 is NP-hard.</ref>
यह परीक्षण करने के लिए एनपी-पूर्ण है कि क्या किसी दिए गए ग्राफ की बॉक्सिकता कुछ दिए गए मान K पर है, यहां तक ​​​​कि K = 2 के लिए भी।<ref>{{harvtxt|Cozzens|1981}} shows that computing the boxicity is NP-complete; {{harvtxt|Yannakakis|1982}} shows that even checking whether the boxicity is at most 3 is NP-hard; finally {{harvtxt|Kratochvil|1994}} showed that recognising boxicity 2 is NP-hard.</ref>
{{harvtxt|Chandran|Francis|Sivadasan|2010}} ग्राफ के [[डिग्री (ग्राफ सिद्धांत)]] के लॉगरिदमिक कारक के भीतर एक आयाम के साथ, बक्से के चौराहे ग्राफ के रूप में मनमाना ग्राफ के प्रतिनिधित्व को खोजने के लिए एल्गोरिदम का वर्णन करें; यह परिणाम ग्राफ़ की बॉक्सिकिटी पर एक ऊपरी सीमा प्रदान करता है।
{{harvtxt|Chandran|Francis|Sivadasan|2010}} ग्राफ के [[डिग्री (ग्राफ सिद्धांत)]] के लॉगरिदमिक कारक के भीतर एक आयाम के साथ, बक्से के चौराहे ग्राफ के रूप में मनमाना ग्राफ के प्रतिनिधित्व को खोजने के लिए एल्गोरिदम का वर्णन करें; यह परिणाम ग्राफ़ की बॉक्सिसिटी पर एक ऊपरी सीमा प्रदान करता है।


अपने प्राकृतिक पैरामीटर के लिए कठोर होने के बावजूद, बॉक्सिकिटी [[पैरामीटरयुक्त जटिलता]] है। इनपुट ग्राफ के [[वर्टेक्स कवर]] नंबर द्वारा पैरामीटर किए जाने पर फिक्स्ड-पैरामीटर ट्रैक्टेबल।<ref>{{harvtxt|Adiga|Chitnis|Saurabh|2010}}.</ref>
अपने प्राकृतिक पैरामीटर के लिए कठोर होने के बावजूद, बॉक्सिसिटी [[पैरामीटरयुक्त जटिलता]] है। इनपुट ग्राफ के [[वर्टेक्स कवर]] नंबर द्वारा पैरामीटर किए जाने पर फिक्स्ड-पैरामीटर ट्रैक्टेबल।<ref>{{harvtxt|Adiga|Chitnis|Saurabh|2010}}.</ref>




== सीमा ==
== सीमा ==
यदि किसी ग्राफ़ G ग्राफ़ में m किनारे हैं, तो:
यदि किसी ग्राफ़ G में m किनारे हैं, तो: <math>box(G) = O(\sqrt{m \cdot \log(m)})</math>.<ref>{{harvtxt|Chandran|Francis|Sivadasan|2010}}</ref><ref>{{harvtxt|Esperet|2016}}</ref>
<math>box(G) = O(\sqrt{m \cdot \log(m)})</math>.<ref>{{harvtxt|Chandran|Francis|Sivadasan|2010}}</ref><ref>{{harvtxt|Esperet|2016}}</ref>
यदि एक ग्राफ G k-Degeneracy (ग्राफ़ सिद्धांत) है (के साथ <math>k\ge 2</math>) और n शीर्ष हैं, तो G में बॉक्सिकता है <math>box(G) \le (k+2) \lceil 2e \log n \rceil</math>.<ref>{{harvtxt|Adiga|Chandran|Mathew|2014}}</ref>
यदि ग्राफ़ G का [[ग्राफ माइनर]] के रूप में शीर्षों पर कोई पूर्ण ग्राफ़ नहीं है, तो <math>box(G) = O(t^2 \log t)</math><ref>{{harvtxt|Esperet|Wiechert|2018}}</ref> जबकि ग्राफ़ माइनर के रूप में और बॉक्सिकिटी के साथ टी कोने पर कोई पूर्ण ग्राफ़ नहीं है <math>\Omega(t \sqrt{\log t})</math>.<ref>{{harvtxt|Esperet|2016}}</ref> विशेष रूप से, किसी भी ग्राफ G में बॉक्सीसिटी होती है <math>box(G) = O(\mu(G)^2 \log \mu(G))</math>, कहाँ <math>\mu(G)</math> कॉलिन डी वेर्डिएर ग्राफ इनवेरिएंट को दर्शाता है | जी का कॉलिन डी वेर्डिएर इनवेरिएंट।


== संबंधित ग्राफ़ इनवेरिएंट्स ==
यदि ग्राफ G k-डीजेनेरसी (ग्राफ़ सिद्धांत) है (<math>k\ge 2</math> के साथ) और n शीर्ष हैं, तो G में <math>box(G) \le (k+2) \lceil 2e \log n \rceil</math> बॉक्सिकता है।<ref>{{harvtxt|Adiga|Chandran|Mathew|2014}}</ref>
* [[ घनापन ]] को उसी तरह से परिभाषित किया जाता है जैसे कि बॉक्सिकिटी लेकिन हाइपररेक्टैंगल्स के बजाय एक्सिस-पैरेलल हाइपरक्यूब्स के साथ।<!--For a graph G, its cubicity cub(G) is the minimum dimension k such that G is representable as the intersection graph of (axis-parallel) cubes in k-dimensional space.--> बॉक्सिकिटी क्यूबिकिटी का एक सामान्यीकरण है।
 
* गोलाकारता (ग्राफ़ सिद्धांत) को उसी तरह से परिभाषित किया जाता है जैसे कि बॉक्सिकता लेकिन इकाई-व्यास वाले क्षेत्रों के साथ।<!-- The sphericity of a graph G is the smallest n such that the vertices in G can be mapped into unit-diameter spheres in n-space in such a way that two vertices are adjacent in G if and only if their assigned spheres intersect.-->
यदि ग्राफ़ G का [[ग्राफ माइनर|ग्राफ अवयस्क]] के रूप में शीर्षों पर कोई पूर्ण ग्राफ़ नहीं है, तो <math>box(G) = O(t^2 \log t)</math><ref>{{harvtxt|Esperet|Wiechert|2018}}</ref> जबकि ग्राफ़ अवयस्क के रूप में और बॉक्सिसिटी के साथ t कोने पर कोई पूर्ण ग्राफ़ नहीं है और बॉक्सिकिटी के साथ ग्राफ़ <math>\Omega(t \sqrt{\log t})</math> हैं। <ref>{{harvtxt|Esperet|2016}}</ref> विशेष रूप से, किसी भी ग्राफ G में <math>box(G) = O(\mu(G)^2 \log \mu(G))</math> बॉक्सीसिटी होती है , जहां  <math>\mu(G)</math> कॉलिन डी वेर्डिएर ग्राफ अपरिवर्तनीय को दर्शाता है |
 
== संबंधित ग्राफ़ अपरिवर्तनशीलता ==
* [[ घनापन |घनापन]] को उसी तरह से परिभाषित किया जाता है जैसे कि बॉक्सिसिटी लेकिन हाइपररेक्टैंगल्स के बजाय अक्ष-समानांतर हाइपरक्यूब्स के साथ। बॉक्सिसिटी घनता का एक सामान्यीकरण है।
* गोलाकारता (ग्राफ़ सिद्धांत) को उसी तरह से परिभाषित किया जाता है जैसे कि बॉक्सिकता लेकिन इकाई-व्यास वाले क्षेत्रों के साथ।




Revision as of 15:18, 12 March 2023

आयतों का प्रतिच्छेदन ग्राफ, बॉक्सिकता दो के साथ

ग्राफ थ्योरी में, बॉक्सिसिटी एक ग्राफ अपरिवर्तनीय है, जिसे 1969 में फ्रेड एस रॉबर्ट्स द्वारा प्रवेशित किया गया था।

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

उदाहरण

यह चित्र छह कोने के साथ एक ग्राफ दिखाता है, और आयतों (दो-आयामी बक्से) के प्रतिच्छेदन ग्राफ के रूप में इस ग्राफ का प्रतिनिधित्व करता है। इस ग्राफ को किसी भी निचले आयाम में बक्से के प्रतिच्छेदन ग्राफ के रूप में प्रदर्शित नहीं किया जा सकता है, इसलिए इसकी बॉक्सिकता दो है।

रॉबर्ट्स (1969) ने दिखाया कि 2n सिरों पर एक पूर्ण ग्राफ़ से परिपूर्ण मिलान को हटाकर 2n कोने वाले ग्राफ़ में बॉक्सिकता यथार्थत: n है: असंबद्ध किए गए कोने के प्रत्येक जोड़े को उन बक्सों द्वारा दिखाया जाना चाहिए जो एक दूसरे जोड़े की तुलना में एक अलग आयाम में अलग होते हैं। आयाम के साथ इस ग्राफ का एक बक्से प्रतिनिधित्व एन-डायमेंशनल अतिविम के प्रत्येक 2n पहलुओं को एक बक्से में मोटा करके पाया जा सकता है। इन परिणामों के कारण, इस ग्राफ को रॉबर्ट्स ग्राफ कहा गया है,[1] हालाँकि इसे कॉकटेल पार्टी ग्राफ के रूप में जाना जाता है और इसे तूरान ग्राफ T(2n,n) के रूप में भी समझा जा सकता है।

अन्य ग्राफ वर्गों से संबंध

एक ग्राफ़ में बॉक्सिसिटी अधिक से अधिक एक होती है यदि और केवल यदि यह एक अंतराल ग्राफ़ है; मनमाना ग्राफ़ G की बॉक्सिकता अंतराल के समान समुच्चय पर अंतराल ग्राफ़ की न्यूनतम संख्या है, जैसे कि अंतराल ग्राफ़ के किनारों के समुच्चय का प्रतिच्छेदन G है। प्रत्येक बाहरी ग्राफ़ में अधिकतम दो पर बॉक्सिसिटी होती है,[2] और प्रत्येक प्लेनर ग्राफ में अधिक से अधिक तीन में बॉक्सिसिटी होती है।[3] यदि एक द्विदलीय ग्राफ में बॉक्सिसिटी दो है, तो इसे विमान में अक्ष-समानांतर रेखा खंडों के प्रतिच्छेदन ग्राफ के रूप में दिखाया जा सकता है।[4]

Adiga, Bhowmick & Chandran (2011) ने साबित किया कि द्विदलीय ग्राफ G की बॉक्सिकता ऊंचाई के आदेश आयाम के एक कारक 2 के भीतर है- दो आंशिक रूप से G से जुड़े समुच्चय का आदेश इस प्रकार है: न्यूनतम तत्वों का समुच्चय G के एक आंशिक समुच्चय से मेल खाता है, का समुच्चय अधिकतम तत्व G के दूसरे पक्षीय समुच्चय से मेल खाते हैं, और दो तत्व तुलनीय हैं यदि संबंधित कोने G में आसन्न हैं। समान रूप से, ऊंचाई-दो आंशिक रूप से आदेशित समुच्चय P का ऑर्डर आयाम तुलनात्मकता के बॉक्सिकता के कारक 2 के भीतर है P का ग्राफ (जो द्विदलीय है, चूँकि P की ऊँचाई दो है)।

एल्गोरिथम परिणाम

कई ग्राफ़ समस्याओं को हल किया जा सकता है या बाउंड बॉक्सिसिटी वाले ग्राफ़ के लिए अन्य ग्राफ़ की तुलना में अधिक कुशलता से हल किया जा सकता है; उदाहरण के लिए, बाउंड बॉक्सिसिटी वाले ग्राफ़ के लिए बहुपद समय में अधिकतम क्लिक समस्या को हल किया जा सकता है।[5] कुछ अन्य ग्राफ़ समस्याओं के लिए, एक कम-आयामी बक्से प्रतिनिधित्व ज्ञात होने पर एक कुशल समाधान या सन्निकटन पाया जा सकता है।[6] हालाँकि, ऐसा प्रतिनिधित्व खोजना मुश्किल हो सकता है: यह परीक्षण करने के लिए एनपी-पूर्ण है कि क्या किसी दिए गए ग्राफ की बॉक्सिकता कुछ दिए गए मान K पर है, यहां तक ​​​​कि K = 2 के लिए भी।[7] Chandran, Francis & Sivadasan (2010) ग्राफ के डिग्री (ग्राफ सिद्धांत) के लॉगरिदमिक कारक के भीतर एक आयाम के साथ, बक्से के चौराहे ग्राफ के रूप में मनमाना ग्राफ के प्रतिनिधित्व को खोजने के लिए एल्गोरिदम का वर्णन करें; यह परिणाम ग्राफ़ की बॉक्सिसिटी पर एक ऊपरी सीमा प्रदान करता है।

अपने प्राकृतिक पैरामीटर के लिए कठोर होने के बावजूद, बॉक्सिसिटी पैरामीटरयुक्त जटिलता है। इनपुट ग्राफ के वर्टेक्स कवर नंबर द्वारा पैरामीटर किए जाने पर फिक्स्ड-पैरामीटर ट्रैक्टेबल।[8]


सीमा

यदि किसी ग्राफ़ G में m किनारे हैं, तो: .[9][10]

यदि ग्राफ G k-डीजेनेरसी (ग्राफ़ सिद्धांत) है ( के साथ) और n शीर्ष हैं, तो G में बॉक्सिकता है।[11]

यदि ग्राफ़ G का ग्राफ अवयस्क के रूप में शीर्षों पर कोई पूर्ण ग्राफ़ नहीं है, तो [12] जबकि ग्राफ़ अवयस्क के रूप में और बॉक्सिसिटी के साथ t कोने पर कोई पूर्ण ग्राफ़ नहीं है और बॉक्सिकिटी के साथ ग्राफ़ हैं। [13] विशेष रूप से, किसी भी ग्राफ G में बॉक्सीसिटी होती है , जहां कॉलिन डी वेर्डिएर ग्राफ अपरिवर्तनीय को दर्शाता है |

संबंधित ग्राफ़ अपरिवर्तनशीलता

  • घनापन को उसी तरह से परिभाषित किया जाता है जैसे कि बॉक्सिसिटी लेकिन हाइपररेक्टैंगल्स के बजाय अक्ष-समानांतर हाइपरक्यूब्स के साथ। बॉक्सिसिटी घनता का एक सामान्यीकरण है।
  • गोलाकारता (ग्राफ़ सिद्धांत) को उसी तरह से परिभाषित किया जाता है जैसे कि बॉक्सिकता लेकिन इकाई-व्यास वाले क्षेत्रों के साथ।


टिप्पणियाँ

  1. ↑ E.g., see Chandran, Francis & Sivadasan (2010) and Chandran & Sivadasan (2007).
  2. ↑ Scheinerman (1984).
  3. ↑ Thomassen (1986).
  4. ↑ Bellantoni et al. (1993).
  5. ↑ Chandran, Francis & Sivadasan (2010) observe that this follows from the fact that these graphs have a polynomial number of maximal cliques. An explicit box representation is not needed to list all maximal cliques efficiently.
  6. ↑ See, e.g., Agarwal, van Kreveld & Suri (1998) and Berman et al. (2001) for approximations to the maximum independent set for intersection graphs of rectangles, and Chlebík & Chlebíková (2005) for results on hardness of approximation of these problems in higher dimensions.
  7. ↑ Cozzens (1981) shows that computing the boxicity is NP-complete; Yannakakis (1982) shows that even checking whether the boxicity is at most 3 is NP-hard; finally Kratochvil (1994) showed that recognising boxicity 2 is NP-hard.
  8. ↑ Adiga, Chitnis & Saurabh (2010).
  9. ↑ Chandran, Francis & Sivadasan (2010)
  10. ↑ Esperet (2016)
  11. ↑ Adiga, Chandran & Mathew (2014)
  12. ↑ Esperet & Wiechert (2018)
  13. ↑ Esperet (2016)


संदर्भ

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बॉक्सिसिटी&oldid=107891’