अंतर्निहित ग्राफ: Difference between revisions
No edit summary |
|||
| Line 33: | Line 33: | ||
| year = 2003| arxiv = quant-ph/0209131}}.</ref> | | year = 2003| arxiv = quant-ph/0209131}}.</ref> | ||
== | ==अडजैसेन्सी लेबलिंग स्कीम्स== | ||
ग्राफ़ के कुशल प्रतिनिधित्व के संदर्भ में, जे.एच. मुलर ने ग्राफ़ के लिए एक स्थानीय संरचना या आसन्न लेबलिंग योजना को परिभाषित किया {{mvar|G}} | ग्राफ़ के कुशल प्रतिनिधित्व के संदर्भ में, जे.एच. मुलर ने ग्राफ़ के किसी दिए गए समूह {{mvar|F}} में ग्राफ़ {{mvar|G}} के लिए एक स्थानीय संरचना या आसन्न लेबलिंग योजना को परिभाषित किया, जो कि {{mvar|G}} के प्रत्येक शीर्ष पर {{math|''O''(log ''n'')}}-बिट पहचानकर्ता का असाइनमेंट है, एक एल्गोरिथ्म के साथ (जो {{mvar|F}} पर निर्भर हो सकता है लेकिन व्यक्तिगत ग्राफ {{mvar|G}} से स्वतंत्र है) जो इनपुट के रूप में दो शीर्ष पहचानकर्ताओं को लेता है और निर्धारित करता है कि वे {{mvar|G}} में एक किनारे के अंतिम बिंदु हैं या नहीं। यानी, इस प्रकार का अंतर्निहित प्रतिनिधित्व है आसन्न मैट्रिक्स के अनुरूप: यह जांचना सीधा है कि क्या दो शीर्ष आसन्न हैं, लेकिन किसी शीर्ष के पड़ोसियों को खोजने में सभी शीर्षों के माध्यम से लूपिंग और परीक्षण करना शामिल हो सकता है कि कौन परिवेश हैं।<ref name="muller">{{citation | ||
| last = Muller | first = John Harold | | last = Muller | first = John Harold | ||
| publisher = Georgia Institute of Technology | | publisher = Georgia Institute of Technology | ||
| Line 40: | Line 40: | ||
| title = Local structure in graph classes | | title = Local structure in graph classes | ||
| year = 1988}}.</ref> | | year = 1988}}.</ref> | ||
निकटवर्ती लेबलिंग योजनाओं वाले ग्राफ़ | |||
;परिबद्ध डिग्री ग्राफ़: यदि | निकटवर्ती लेबलिंग योजनाओं वाले ग्राफ़ समूहों में शामिल हैं: | ||
;परिबद्ध डिग्री ग्राफ़: यदि {{mvar|G}} के प्रत्येक शीर्ष पर अधिकतम {{mvar|d}} पड़ोसी हैं, तो कोई व्यक्ति {{mvar|G}} के शीर्षों को 1 से {{mvar|n}} तक क्रमांकित कर सकता है और किसी शीर्ष के लिए पहचानकर्ता को उसकी अपनी संख्या और उसके पड़ोसियों की संख्या का {{math|(''d'' + 1)}}-टुपल मान सकता है। दो शीर्ष आसन्न होते हैं जब उनके पहचानकर्ताओं में पहले नंबर बाद में दूसरे शीर्ष के पहचानकर्ता में दिखाई देते हैं। अधिक आम तौर पर, समान दृष्टिकोण का उपयोग सीमाबद्ध आर्बोरिसिटी या सीमाबद्ध अध:पतन वाले ग्राफ़ के लिए एक अंतर्निहित प्रतिनिधित्व प्रदान करने के लिए किया जा सकता है, जिसमें समतल ग्राफ़ और किसी भी छोटे-बंद ग्राफ़ परिवार में ग्राफ़ शामिल हैं।<ref name="knr" /><ref>{{citation | |||
| last1 = Chrobak | first1 = Marek | | last1 = Chrobak | first1 = Marek | ||
| last2 = Eppstein | first2 = David | author2-link = David Eppstein | | last2 = Eppstein | first2 = David | author2-link = David Eppstein | ||
| Line 52: | Line 53: | ||
| volume = 86 | | volume = 86 | ||
| year = 1991| doi-access = free | | year = 1991| doi-access = free | ||
}}.</ref> | }}.</ref>: | ||
;इंटरसेक्शन ग्राफ: एक | ;इंटरसेक्शन ग्राफ: एक अंतराल ग्राफ वास्तविक रेखा में रेखा खंडों के एक सेट का प्रतिच्छेदन ग्राफ है। इसे एक आसन्न लेबलिंग योजना दी जा सकती है जिसमें रेखा खंडों के अंतिम बिंदुओं को 1 से 2n तक क्रमांकित किया जाता है और ग्राफ़ के प्रत्येक शीर्ष को उसके संबंधित अंतराल के दो समापन बिंदुओं की संख्या द्वारा दर्शाया जाता है। इस प्रतिनिधित्व के साथ, कोई यह जांच सकता है कि क्या दो शीर्ष उन संख्याओं की तुलना करके आसन्न हैं जो उनका प्रतिनिधित्व करते हैं और यह सत्यापित करते हैं कि ये संख्याएं ओवरलैपिंग अंतराल को परिभाषित करती हैं। यही दृष्टिकोण अन्य ज्यामितीय [[प्रतिच्छेदन ग्राफ]] के लिए भी काम करता है, जिसमें सीमाबद्ध [[बॉक्सिसिटी]] और [[वृत्त ग्राफ]] और इन समूहों के उपपरिवार जैसे दूरी-वंशानुगत ग्राफ़ और कोग्राफ़ शामिल हैं।<ref name="knr" /><ref name="spinrad" /> हालाँकि, एक ज्यामितीय प्रतिच्छेदन ग्राफ प्रतिनिधित्व हमेशा एक आसन्नता लेबलिंग योजना के अस्तित्व का संकेत नहीं देता है, क्योंकि प्रत्येक ज्यामितीय वस्तु को निर्दिष्ट करने के लिए बिट्स की लघुगणकीय संख्या से अधिक की आवश्यकता हो सकती है। उदाहरण के लिए, एक ग्राफ़ को एक इकाई डिस्क ग्राफ़ के रूप में प्रस्तुत करने के लिए डिस्क केंद्रों के निर्देशांक के लिए तेजी से कई बिट्स की आवश्यकता हो सकती है।<ref>{{citation|url=http://homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf|last1=Kang|first1=Ross J.|last2=Müller|first2=Tobias|title=Sphere and dot product representations of graphs|year=2011|access-date=2011-07-12|archive-url=https://web.archive.org/web/20120316103530/http://homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf|archive-date=2012-03-16|url-status=dead}}.</ref>: | ||
;निम्न-आयामी | ;निम्न-आयामी तुलनीयता ग्राफ़: आंशिक रूप से ऑर्डर किए गए सेट के लिए तुलनीयता ग्राफ़ में प्रत्येक सेट तत्व के लिए एक शीर्ष और आंशिक क्रम से संबंधित दो सेट तत्वों के बीच एक किनारा होता है। आंशिक ऑर्डर का ऑर्डर आयाम रैखिक ऑर्डरों की न्यूनतम संख्या है जिसका प्रतिच्छेदन दिया गया आंशिक ऑर्डर है। यदि किसी आंशिक क्रम में सीमित क्रम आयाम है, तो इसके तुलनीयता ग्राफ में शीर्षों के लिए एक आसन्नता लेबलिंग योजना को प्रत्येक परिभाषित रैखिक क्रम में अपनी स्थिति के साथ प्रत्येक शीर्ष को लेबल करके परिभाषित किया जा सकता है, और यह निर्धारित किया जा सकता है कि यदि प्रत्येक संगत जोड़ी है तो दो शीर्ष आसन्न हैं उनके लेबल में संख्याओं का एक-दूसरे जोड़े के समान क्रम संबंध है। विशेष रूप से, यह कॉर्डल तुलनीयता ग्राफ़ के लिए एक आसन्नता लेबलिंग योजना की अनुमति देता है, जो अधिकतम चार आयामों के आंशिक आदेशों से आते हैं।<ref>{{citation | ||
| last1 = Ma | first1 = Tze Heng | | last1 = Ma | first1 = Tze Heng | ||
| last2 = Spinrad | first2 = Jeremy P. | | last2 = Spinrad | first2 = Jeremy P. | ||
| Line 83: | Line 84: | ||
===अंतर्निहित ग्राफ़ अनुमान=== | ===अंतर्निहित ग्राफ़ अनुमान=== | ||
{{unsolved|mathematics|Does every slowly-growing [[Hereditary property#In graph theory|hereditary family of graphs]] have an implicit representation?}} | {{unsolved|mathematics|Does every slowly-growing [[Hereditary property#In graph theory|hereditary family of graphs]] have an implicit representation?}} | ||
सभी ग्राफ़ | सभी ग्राफ़ समूहों में स्थानीय संरचनाएँ नहीं होती हैं। कुछ समूहों के लिए, एक साधारण गिनती तर्क साबित करता है कि आसन्नता लेबलिंग योजनाएं मौजूद नहीं हैं: केवल {{math|''O''(''n'' log ''n'')}} बिट्स का उपयोग संपूर्ण ग्राफ़ का प्रतिनिधित्व करने के लिए किया जा सकता है, इसलिए इस प्रकार का प्रतिनिधित्व केवल तभी मौजूद हो सकता है जब संख्या {{mvar|n}}-दिए गए समूह में वर्टेक्स ग्राफ़ {{mvar|F}} अधिकतम है {{math|2<sup>''O''(''n'' log ''n'')</sup>}}. ग्राफ़ समूह जिनके पास इससे बड़ी संख्या में ग्राफ़ हैं, जैसे [[द्विदलीय ग्राफ]]़ या [[त्रिकोण-मुक्त ग्राफ़]], में आसन्नता लेबलिंग योजनाएँ नहीं हैं।<ref name="knr"/><ref name="spinrad">{{citation|first=Jeremy P.|last=Spinrad|title=Efficient Graph Representations|year=2003|isbn=0-8218-2815-0|chapter=2. Implicit graph representation|pages=17–30|url=https://books.google.com/books?id=RrtXSKMAmWgC&pg=PA17}}.</ref> हालाँकि, ग्राफ़ के ऐसे समूहों में भी, जिनमें समूह में ग्राफ़ की संख्या कम है, आसन्न लेबलिंग योजना नहीं हो सकती है; उदाहरण के लिए, शीर्षों की तुलना में कम किनारों वाले ग्राफ़ का समूह {{math|2<sup>''O''(''n'' log ''n'')</sup>}} {{mvar|n}}-वर्टेक्स ग्राफ़ लेकिन इसमें आसन्नता लेबलिंग योजना नहीं है, क्योंकि इस समूह में किसी भी दिए गए ग्राफ़ को प्रत्येक किनारे के लिए एक नया पृथक वर्टेक्स जोड़कर, इसकी लेबलेबिलिटी को बदले बिना, एक बड़े ग्राफ़ में बदला जा सकता है।<ref name="muller"/><ref name="spinrad"/>कन्नन एट अल. पूछा गया कि क्या निषिद्ध ग्राफ़ लक्षण वर्णन और अधिकतम होना चाहिए {{math|2<sup>''O''(''n'' log ''n'')</sup>}} {{mvar|n}}-वर्टेक्स ग्राफ एक निकटवर्ती लेबलिंग योजना के अस्तित्व की गारंटी देने के लिए पर्याप्त हैं; यह प्रश्न, जिसे स्पिनराड ने अनुमान के रूप में दोहराया, खुला रहता है।<ref name="knr"/><ref name="spinrad"/>ग्राफ़ के समूहों में से जो अनुमान की शर्तों को पूरा करते हैं और जिनके लिए कोई ज्ञात आसन्नता लेबलिंग योजना नहीं है, वे डिस्क ग्राफ़ और लाइन सेगमेंट चौराहे ग्राफ़ के समूह हैं। | ||
===लेबलिंग योजनाएं और प्रेरित सार्वभौमिक ग्राफ=== | ===लेबलिंग योजनाएं और प्रेरित सार्वभौमिक ग्राफ=== | ||
यदि एक ग्राफ | यदि एक ग्राफ समूह {{mvar|F}} में एक आसन्नता लेबलिंग योजना है, फिर {{mvar|n}}-वर्टेक्स ग्राफ़ में {{mvar|F}} को बहुपद आकार के एक सामान्य प्रेरित [[सार्वभौमिक ग्राफ]] के प्रेरित उपग्राफ के रूप में दर्शाया जा सकता है, ग्राफ में सभी संभावित शीर्ष पहचानकर्ता शामिल हैं। इसके विपरीत, यदि इस प्रकार का एक प्रेरित सार्वभौमिक ग्राफ बनाया जा सकता है, तो इसके शीर्षों की पहचान को आसन्न लेबलिंग योजना में लेबल के रूप में उपयोग किया जा सकता है।<ref name="knr">{{citation | ||
| last1 = Kannan | first1 = Sampath | | last1 = Kannan | first1 = Sampath | ||
| last2 = Naor | first2 = Moni | author2-link = Moni Naor | | last2 = Naor | first2 = Moni | author2-link = Moni Naor | ||
| Line 114: | Line 115: | ||
| url-status = dead | | url-status = dead | ||
}}.</ref> | }}.</ref> | ||
इस सीमा में गैवोइल और लाबोरेल द्वारा सुधार किया गया था, जिन्होंने दिखाया था कि समतलीय ग्राफ़ और लघु-बंद ग्राफ़ | इस सीमा में गैवोइल और लाबोरेल द्वारा सुधार किया गया था, जिन्होंने दिखाया था कि समतलीय ग्राफ़ और लघु-बंद ग्राफ़ समूहों के पास एक लेबलिंग योजना है {{math|2 log<sub>2</sub> ''n'' + ''O''(log log ''n'')}} प्रति लेबल बिट्स, और बंधे हुए [[ वृक्ष चौड़ाई ]] के ग्राफ़ में एक लेबलिंग योजना होती है {{math|log<sub>2</sub> ''n'' + ''O''(log log ''n'')}} प्रति लेबल बिट्स।<ref>{{citation | ||
| last1 = Arnaud | first1 = Labourel | | last1 = Arnaud | first1 = Labourel | ||
| last2 = Gavoille | first2 = Cyril | | last2 = Gavoille | first2 = Cyril | ||
| Line 152: | Line 153: | ||
== टालमटोल== | == टालमटोल== | ||
आंडेरा-कार्प-रोसेनबर्ग अनुमान यह निर्धारित करने के लिए ब्लैक-बॉक्स नियम के साथ लेबल किए गए शीर्षों के एक सेट के रूप में दिए गए अंतर्निहित ग्राफ़ से संबंधित है कि क्या कोई दो शीर्ष आसन्न हैं। यह परिभाषा एक आसन्नता लेबलिंग योजना से भिन्न है जिसमें नियम एक सामान्य नियम होने के बजाय एक विशेष ग्राफ़ के लिए विशिष्ट हो सकता है जो एक | आंडेरा-कार्प-रोसेनबर्ग अनुमान यह निर्धारित करने के लिए ब्लैक-बॉक्स नियम के साथ लेबल किए गए शीर्षों के एक सेट के रूप में दिए गए अंतर्निहित ग्राफ़ से संबंधित है कि क्या कोई दो शीर्ष आसन्न हैं। यह परिभाषा एक आसन्नता लेबलिंग योजना से भिन्न है जिसमें नियम एक सामान्य नियम होने के बजाय एक विशेष ग्राफ़ के लिए विशिष्ट हो सकता है जो एक समूह में सभी ग्राफ़ पर लागू होता है। इस अंतर के कारण, प्रत्येक ग्राफ़ का एक अंतर्निहित प्रतिनिधित्व होता है। उदाहरण के लिए, नियम एक अलग आसन्न मैट्रिक्स में शीर्षों की जोड़ी को देखने का हो सकता है। हालाँकि, एक एल्गोरिथ्म जो इनपुट के रूप में इस प्रकार का एक अंतर्निहित ग्राफ़ दिया जाता है, उसे केवल अंतर्निहित आसन्नता परीक्षण के माध्यम से संचालित करना चाहिए, बिना इस संदर्भ के कि परीक्षण कैसे कार्यान्वित किया जाता है। | ||
ग्राफ़ गुण यह प्रश्न है कि क्या ग्राफ़ ग्राफ़ के दिए गए | ग्राफ़ गुण यह प्रश्न है कि क्या ग्राफ़ ग्राफ़ के दिए गए समूह से संबंधित है; शीर्षों के किसी भी पुनः लेबलिंग के तहत उत्तर अपरिवर्तनीय रहना चाहिए। इस संदर्भ में, निर्धारित करने का प्रश्न यह है कि सबसे खराब स्थिति में, आसन्नता के लिए कितने जोड़े के जोड़े का परीक्षण किया जाना चाहिए, इससे पहले कि किसी दिए गए अंतर्निहित ग्राफ के लिए ब्याज की संपत्ति सही या गलत निर्धारित की जा सके। रिवेस्ट और वुइलमिन ने साबित किया कि किसी भी गैर-तुच्छ ग्राफ़ संपत्ति के लिए किसी भी नियतात्मक एल्गोरिदम को शीर्षों के जोड़े की द्विघात संख्या का परीक्षण करना चाहिए।<ref>{{Citation | ||
| doi = 10.1145/800116.803747 | | doi = 10.1145/800116.803747 | ||
| pages = 6–11 | | pages = 6–11 | ||
Revision as of 16:00, 2 August 2023
ग्राफ़ एल्गोरिदम के अध्ययन में, एक अंतर्निहित ग्राफ़ प्रतिनिधित्व (या अधिक सरल रूप से अंतर्निहित ग्राफ़) एक ऐसा ग्राफ़ होता है जिसके शीर्ष या किनारों को कंप्यूटर की मेमोरी में स्पष्ट ऑब्जेक्ट्स, बल्कि किसी अन्य इनपुट से एल्गोरिदमिक रूप से निर्धारित होते हैं, उदाहरण के लिए एक गणना योग्य फ़ंक्शन के रूप में दर्शाया नहीं जाता है।
परिवेश का प्रतिनिधित्व
अंतर्निहित ग्राफ़ की धारणा विभिन्न खोज एल्गोरिदम में आम है जिन्हें ग्राफ़ के संदर्भ में वर्णित किया गया है। इस संदर्भ में, एक अंतर्निहित ग्राफ़ को किसी निर्दिष्ट शीर्ष के सभी पड़ोसियों को परिभाषित करने के लिए नियमों के एक सेट के रूप में परिभाषित किया जा सकता है।[1] इस प्रकार का अंतर्निहित ग्राफ़ प्रतिनिधित्व एक आसन्नता सूची के अनुरूप है, जिसमें यह प्रत्येक शीर्ष के पड़ोसियों तक आसान पहुंच प्रदान करता है। उदाहरण के लिए, रूबिक क्यूब जैसी पहेली का समाधान खोजने में, कोई एक अंतर्निहित ग्राफ को परिभाषित कर सकता है जिसमें प्रत्येक शीर्ष घन की संभावित स्थितियों में से एक का प्रतिनिधित्व करता है, और प्रत्येक किनारा एक राज्य से दूसरे राज्य में जाने का प्रतिनिधित्व करता है। पहेली में सभी संभावित स्थान-परिवर्तन को प्रयास करके और इनमें से प्रत्येक स्थान-परिवर्तन द्वारा पहुँची गई स्थिति का निर्धारण करके किसी भी शीर्ष के परिवैश को उत्पन्न करना प्रत्यक्ष है।; हालाँकि, एक अंतर्निहित प्रतिनिधित्व आवश्यक है, क्योंकि रुबिक क्यूब का राज्य स्थान इतना बड़ा है कि एक एल्गोरिदम इसके सभी अवस्थाओं को सूचीबद्ध करने की अनुमति नहीं दे सकता है।[2]
कम्प्यूटेशनल जटिलता सिद्धांत में, अंतर्निहित ग्राफ़ के संबंध में कई जटिलता वर्गों को परिभाषित किया गया है, जैसा कि एक शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक नियम या एल्गोरिदम द्वारा ऊपर परिभाषित किया गया है। उदाहरण के लिए, पीपीए समस्याओं का वह वर्ग है जिसमें इनपुट के रूप में एक अप्रत्यक्ष अंतर्निहित ग्राफ दिया जाता है (जिसमें कोने n-बिट बाइनरी स्ट्रिंग होते हैं, किसी भी शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक बहुपद समय एल्गोरिदम के साथ) और विषम डिग्री का एक शीर्ष होता है ग्राफ़ में, और विषम डिग्री का दूसरा शीर्ष खोजना होगा। हाथ मिलाने की प्रमेयिका द्वारा, ऐसा शीर्ष मौजूद है; NP में किसी को ढूंढना एक समस्या है, लेकिन जिन समस्याओं को इस तरह से परिभाषित किया जा सकता है, जरूरी नहीं कि वे NP-पूर्ण हों, क्योंकि यह अज्ञात है कि PPA = NP है या नहीं। PPAD अंतर्निहित निर्देशित ग्राफ़ पर परिभाषित एक अनुरूप वर्ग है जिसने एल्गोरिथम गेम सिद्धांत में ध्यान आकर्षित किया है क्योंकि इसमें नैश संतुलन की गणना करने की समस्या शामिल है।[3] एक अंतर्निहित ग्राफ़ में एक शीर्ष से दूसरे शीर्ष तक पहुंच योग्यता का परीक्षण करने की समस्या का उपयोग NL सहित अंतरिक्ष-बद्ध गैर-नियतात्मक जटिलता वर्गों को चिह्नित करने के लिए भी किया जा सकता है (समस्याओं का वर्ग जिसे अंतर्निहित निर्देशित ग्राफ़ में पहुंच योग्यता द्वारा विशेषता दी जा सकती है जिनके शीर्ष O(log n)-bit बिटस्ट्रिंग्स), SL (अप्रत्यक्ष ग्राफ़ के लिए अनुरूप वर्ग), और पीएसपीएसीई (समस्याओं का वर्ग जिसे बहुपद-लंबाई बिटस्ट्रिंग्स के साथ अंतर्निहित ग्राफ़ में पहुंच द्वारा विशेषता दी जा सकती है)। इस जटिलता-सैद्धांतिक संदर्भ में, एक अंतर्निहित ग्राफ़ के शीर्ष एक गैर-नियतात्मक ट्यूरिंग मशीन की स्थितियों का प्रतिनिधित्व कर सकते हैं, और किनारे संभावित राज्य परिवर्तनों का प्रतिनिधित्व कर सकते हैं, लेकिन अंतर्निहित ग्राफ़ का उपयोग कई अन्य प्रकार की संयोजन संरचना का प्रतिनिधित्व करने के लिए भी किया जा सकता है।[4] PLS, एक अन्य जटिलता वर्ग, एक अंतर्निहित ग्राफ़ में स्थानीय ऑप्टिमा खोजने की जटिलता को पकड़ता है।[5]
जटिलता वर्गों के बीच अलगाव को सिद्ध करने के लिए निहित ग्राफ मॉडल का उपयोग सापेक्षता के एक रूप के रूप में भी किया गया है जो गैर-सापेक्ष मॉडल के लिए ज्ञात पृथक्करण से अधिक मजबूत हैं। उदाहरण के लिए, चाइल्ड्स एट अल. ग्राफ़ ट्रैवर्सल समस्या को परिभाषित करने के लिए अंतर्निहित ग्राफ़ के परिवेश निरूपण का उपयोग किया जाता है जिसे क्वांटम कंप्यूटर पर बहुपद समय में हल किया जा सकता है लेकिन किसी भी शास्त्रीय कंप्यूटर पर हल करने के लिए घातीय समय की आवश्यकता होती है।[6]
अडजैसेन्सी लेबलिंग स्कीम्स
ग्राफ़ के कुशल प्रतिनिधित्व के संदर्भ में, जे.एच. मुलर ने ग्राफ़ के किसी दिए गए समूह F में ग्राफ़ G के लिए एक स्थानीय संरचना या आसन्न लेबलिंग योजना को परिभाषित किया, जो कि G के प्रत्येक शीर्ष पर O(log n)-बिट पहचानकर्ता का असाइनमेंट है, एक एल्गोरिथ्म के साथ (जो F पर निर्भर हो सकता है लेकिन व्यक्तिगत ग्राफ G से स्वतंत्र है) जो इनपुट के रूप में दो शीर्ष पहचानकर्ताओं को लेता है और निर्धारित करता है कि वे G में एक किनारे के अंतिम बिंदु हैं या नहीं। यानी, इस प्रकार का अंतर्निहित प्रतिनिधित्व है आसन्न मैट्रिक्स के अनुरूप: यह जांचना सीधा है कि क्या दो शीर्ष आसन्न हैं, लेकिन किसी शीर्ष के पड़ोसियों को खोजने में सभी शीर्षों के माध्यम से लूपिंग और परीक्षण करना शामिल हो सकता है कि कौन परिवेश हैं।[7]
निकटवर्ती लेबलिंग योजनाओं वाले ग्राफ़ समूहों में शामिल हैं:
- परिबद्ध डिग्री ग्राफ़
- यदि G के प्रत्येक शीर्ष पर अधिकतम d पड़ोसी हैं, तो कोई व्यक्ति G के शीर्षों को 1 से n तक क्रमांकित कर सकता है और किसी शीर्ष के लिए पहचानकर्ता को उसकी अपनी संख्या और उसके पड़ोसियों की संख्या का (d + 1)-टुपल मान सकता है। दो शीर्ष आसन्न होते हैं जब उनके पहचानकर्ताओं में पहले नंबर बाद में दूसरे शीर्ष के पहचानकर्ता में दिखाई देते हैं। अधिक आम तौर पर, समान दृष्टिकोण का उपयोग सीमाबद्ध आर्बोरिसिटी या सीमाबद्ध अध:पतन वाले ग्राफ़ के लिए एक अंतर्निहित प्रतिनिधित्व प्रदान करने के लिए किया जा सकता है, जिसमें समतल ग्राफ़ और किसी भी छोटे-बंद ग्राफ़ परिवार में ग्राफ़ शामिल हैं।[8][9]:
- इंटरसेक्शन ग्राफ
- एक अंतराल ग्राफ वास्तविक रेखा में रेखा खंडों के एक सेट का प्रतिच्छेदन ग्राफ है। इसे एक आसन्न लेबलिंग योजना दी जा सकती है जिसमें रेखा खंडों के अंतिम बिंदुओं को 1 से 2n तक क्रमांकित किया जाता है और ग्राफ़ के प्रत्येक शीर्ष को उसके संबंधित अंतराल के दो समापन बिंदुओं की संख्या द्वारा दर्शाया जाता है। इस प्रतिनिधित्व के साथ, कोई यह जांच सकता है कि क्या दो शीर्ष उन संख्याओं की तुलना करके आसन्न हैं जो उनका प्रतिनिधित्व करते हैं और यह सत्यापित करते हैं कि ये संख्याएं ओवरलैपिंग अंतराल को परिभाषित करती हैं। यही दृष्टिकोण अन्य ज्यामितीय प्रतिच्छेदन ग्राफ के लिए भी काम करता है, जिसमें सीमाबद्ध बॉक्सिसिटी और वृत्त ग्राफ और इन समूहों के उपपरिवार जैसे दूरी-वंशानुगत ग्राफ़ और कोग्राफ़ शामिल हैं।[8][10] हालाँकि, एक ज्यामितीय प्रतिच्छेदन ग्राफ प्रतिनिधित्व हमेशा एक आसन्नता लेबलिंग योजना के अस्तित्व का संकेत नहीं देता है, क्योंकि प्रत्येक ज्यामितीय वस्तु को निर्दिष्ट करने के लिए बिट्स की लघुगणकीय संख्या से अधिक की आवश्यकता हो सकती है। उदाहरण के लिए, एक ग्राफ़ को एक इकाई डिस्क ग्राफ़ के रूप में प्रस्तुत करने के लिए डिस्क केंद्रों के निर्देशांक के लिए तेजी से कई बिट्स की आवश्यकता हो सकती है।[11]:
- निम्न-आयामी तुलनीयता ग्राफ़
- आंशिक रूप से ऑर्डर किए गए सेट के लिए तुलनीयता ग्राफ़ में प्रत्येक सेट तत्व के लिए एक शीर्ष और आंशिक क्रम से संबंधित दो सेट तत्वों के बीच एक किनारा होता है। आंशिक ऑर्डर का ऑर्डर आयाम रैखिक ऑर्डरों की न्यूनतम संख्या है जिसका प्रतिच्छेदन दिया गया आंशिक ऑर्डर है। यदि किसी आंशिक क्रम में सीमित क्रम आयाम है, तो इसके तुलनीयता ग्राफ में शीर्षों के लिए एक आसन्नता लेबलिंग योजना को प्रत्येक परिभाषित रैखिक क्रम में अपनी स्थिति के साथ प्रत्येक शीर्ष को लेबल करके परिभाषित किया जा सकता है, और यह निर्धारित किया जा सकता है कि यदि प्रत्येक संगत जोड़ी है तो दो शीर्ष आसन्न हैं उनके लेबल में संख्याओं का एक-दूसरे जोड़े के समान क्रम संबंध है। विशेष रूप से, यह कॉर्डल तुलनीयता ग्राफ़ के लिए एक आसन्नता लेबलिंग योजना की अनुमति देता है, जो अधिकतम चार आयामों के आंशिक आदेशों से आते हैं।[12][13]
अंतर्निहित ग्राफ़ अनुमान
Does every slowly-growing hereditary family of graphs have an implicit representation?
सभी ग्राफ़ समूहों में स्थानीय संरचनाएँ नहीं होती हैं। कुछ समूहों के लिए, एक साधारण गिनती तर्क साबित करता है कि आसन्नता लेबलिंग योजनाएं मौजूद नहीं हैं: केवल O(n log n) बिट्स का उपयोग संपूर्ण ग्राफ़ का प्रतिनिधित्व करने के लिए किया जा सकता है, इसलिए इस प्रकार का प्रतिनिधित्व केवल तभी मौजूद हो सकता है जब संख्या n-दिए गए समूह में वर्टेक्स ग्राफ़ F अधिकतम है 2O(n log n). ग्राफ़ समूह जिनके पास इससे बड़ी संख्या में ग्राफ़ हैं, जैसे द्विदलीय ग्राफ़ या त्रिकोण-मुक्त ग्राफ़, में आसन्नता लेबलिंग योजनाएँ नहीं हैं।[8][10] हालाँकि, ग्राफ़ के ऐसे समूहों में भी, जिनमें समूह में ग्राफ़ की संख्या कम है, आसन्न लेबलिंग योजना नहीं हो सकती है; उदाहरण के लिए, शीर्षों की तुलना में कम किनारों वाले ग्राफ़ का समूह 2O(n log n) n-वर्टेक्स ग्राफ़ लेकिन इसमें आसन्नता लेबलिंग योजना नहीं है, क्योंकि इस समूह में किसी भी दिए गए ग्राफ़ को प्रत्येक किनारे के लिए एक नया पृथक वर्टेक्स जोड़कर, इसकी लेबलेबिलिटी को बदले बिना, एक बड़े ग्राफ़ में बदला जा सकता है।[7][10]कन्नन एट अल. पूछा गया कि क्या निषिद्ध ग्राफ़ लक्षण वर्णन और अधिकतम होना चाहिए 2O(n log n) n-वर्टेक्स ग्राफ एक निकटवर्ती लेबलिंग योजना के अस्तित्व की गारंटी देने के लिए पर्याप्त हैं; यह प्रश्न, जिसे स्पिनराड ने अनुमान के रूप में दोहराया, खुला रहता है।[8][10]ग्राफ़ के समूहों में से जो अनुमान की शर्तों को पूरा करते हैं और जिनके लिए कोई ज्ञात आसन्नता लेबलिंग योजना नहीं है, वे डिस्क ग्राफ़ और लाइन सेगमेंट चौराहे ग्राफ़ के समूह हैं।
लेबलिंग योजनाएं और प्रेरित सार्वभौमिक ग्राफ
यदि एक ग्राफ समूह F में एक आसन्नता लेबलिंग योजना है, फिर n-वर्टेक्स ग्राफ़ में F को बहुपद आकार के एक सामान्य प्रेरित सार्वभौमिक ग्राफ के प्रेरित उपग्राफ के रूप में दर्शाया जा सकता है, ग्राफ में सभी संभावित शीर्ष पहचानकर्ता शामिल हैं। इसके विपरीत, यदि इस प्रकार का एक प्रेरित सार्वभौमिक ग्राफ बनाया जा सकता है, तो इसके शीर्षों की पहचान को आसन्न लेबलिंग योजना में लेबल के रूप में उपयोग किया जा सकता है।[8] अंतर्निहित ग्राफ़ अभ्यावेदन के इस अनुप्रयोग के लिए, यह महत्वपूर्ण है कि लेबल यथासंभव कम बिट्स का उपयोग करें, क्योंकि लेबल में बिट्स की संख्या सीधे प्रेरित सार्वभौमिक ग्राफ़ में शीर्षों की संख्या में तब्दील हो जाती है। अलस्ट्रुप और रौहे ने दिखाया कि किसी भी पेड़ के पास एक आसन्नता लेबलिंग योजना होती है log2 n + O(log* n) प्रति लेबल बिट्स, जिससे यह पता चलता है कि आर्बोरिसिटी k वाले किसी भी ग्राफ में एक योजना होती है k log2 n + O(log* n) प्रति लेबल बिट्स और एक सार्वभौमिक ग्राफ nk2O(log* n) शिखर. विशेष रूप से, समतलीय ग्राफ़ में अधिकतम तीन आर्बोरिसिटी होती है, इसलिए उनके पास लगभग-घन संख्या वाले शीर्षों के साथ सार्वभौमिक ग्राफ़ होते हैं।[14] इस सीमा में गैवोइल और लाबोरेल द्वारा सुधार किया गया था, जिन्होंने दिखाया था कि समतलीय ग्राफ़ और लघु-बंद ग्राफ़ समूहों के पास एक लेबलिंग योजना है 2 log2 n + O(log log n) प्रति लेबल बिट्स, और बंधे हुए वृक्ष चौड़ाई के ग्राफ़ में एक लेबलिंग योजना होती है log2 n + O(log log n) प्रति लेबल बिट्स।[15] बोनामी, गैवोइल और पिलिकज़ुक द्वारा समतलीय ग्राफ़ की सीमा में फिर से सुधार किया गया, जिन्होंने दिखाया कि समतलीय ग्राफ़ में एक लेबलिंग योजना होती है (4/3+o(1))log2 n प्रति लेबल बिट्स।[16] अंत में डुजमोविक और अन्य ने दिखाया कि समतलीय ग्राफ़ में एक लेबलिंग योजना होती है (1+o(1))log2 n बिट्स प्रति लेबल एक सार्वभौमिक ग्राफ देता है n1+o(1) शिखर.[17]
टालमटोल
आंडेरा-कार्प-रोसेनबर्ग अनुमान यह निर्धारित करने के लिए ब्लैक-बॉक्स नियम के साथ लेबल किए गए शीर्षों के एक सेट के रूप में दिए गए अंतर्निहित ग्राफ़ से संबंधित है कि क्या कोई दो शीर्ष आसन्न हैं। यह परिभाषा एक आसन्नता लेबलिंग योजना से भिन्न है जिसमें नियम एक सामान्य नियम होने के बजाय एक विशेष ग्राफ़ के लिए विशिष्ट हो सकता है जो एक समूह में सभी ग्राफ़ पर लागू होता है। इस अंतर के कारण, प्रत्येक ग्राफ़ का एक अंतर्निहित प्रतिनिधित्व होता है। उदाहरण के लिए, नियम एक अलग आसन्न मैट्रिक्स में शीर्षों की जोड़ी को देखने का हो सकता है। हालाँकि, एक एल्गोरिथ्म जो इनपुट के रूप में इस प्रकार का एक अंतर्निहित ग्राफ़ दिया जाता है, उसे केवल अंतर्निहित आसन्नता परीक्षण के माध्यम से संचालित करना चाहिए, बिना इस संदर्भ के कि परीक्षण कैसे कार्यान्वित किया जाता है।
ग्राफ़ गुण यह प्रश्न है कि क्या ग्राफ़ ग्राफ़ के दिए गए समूह से संबंधित है; शीर्षों के किसी भी पुनः लेबलिंग के तहत उत्तर अपरिवर्तनीय रहना चाहिए। इस संदर्भ में, निर्धारित करने का प्रश्न यह है कि सबसे खराब स्थिति में, आसन्नता के लिए कितने जोड़े के जोड़े का परीक्षण किया जाना चाहिए, इससे पहले कि किसी दिए गए अंतर्निहित ग्राफ के लिए ब्याज की संपत्ति सही या गलत निर्धारित की जा सके। रिवेस्ट और वुइलमिन ने साबित किया कि किसी भी गैर-तुच्छ ग्राफ़ संपत्ति के लिए किसी भी नियतात्मक एल्गोरिदम को शीर्षों के जोड़े की द्विघात संख्या का परीक्षण करना चाहिए।[18] पूर्ण आंडेरा-कार्प-रोसेनबर्ग अनुमान यह है कि एक मोनोटोनिक ग्राफ़ संपत्ति के लिए कोई भी नियतात्मक एल्गोरिदम (जो संपत्ति के साथ ग्राफ़ में अधिक किनारों को जोड़ने पर सत्य रहता है) को कुछ मामलों में शीर्षों की हर संभव जोड़ी का परीक्षण करना होगा। अनुमान के कई मामले सत्य साबित हुए हैं - उदाहरण के लिए, यह शीर्षों की अभाज्य संख्या वाले ग्राफ़ के लिए सत्य माना जाता है[19]-लेकिन पूरा अनुमान खुला रहता है। यादृच्छिक एल्गोरिदम और क्वांटम एल्गोरिदम के लिए समस्या के वेरिएंट का भी अध्ययन किया गया है।
बेंडर और रॉन ने दिखाया है कि, टालमटोल अनुमान के लिए उपयोग किए जाने वाले एक ही मॉडल में, केवल निरंतर समय में निर्देशित एसाइक्लिक ग्राफ़ को उन ग्राफ़ से अलग करना संभव है जो एसाइक्लिक होने से बहुत दूर हैं। इसके विपरीत, प्रतिवेशी-आधारित अंतर्निहित ग्राफ़ मॉडल में इतना तेज़ समय संभव नहीं है,[20]
यह भी देखें
- ब्लैक बॉक्स समूह, समूह सिद्धांत के लिए एक अंतर्निहित मॉडल|समूह-सैद्धांतिक एल्गोरिदम
- [[matroid दैवज्ञ]], मैट्रोइड एल्गोरिदम के लिए एक अंतर्निहित मॉडल
संदर्भ
- ↑ Korf, Richard E. (2008), "Linear-time disk-based implicit graph search", Journal of the ACM, 55 (6), Article 26, 40pp, doi:10.1145/1455248.1455250, MR 2477486.
- ↑ Korf, Richard E. (2008), "Minimizing disk I/O in two-bit breadth-first search" (PDF), Proc. 23rd AAAI Conf. on Artificial Intelligence, pp. 317–324,
The standard 3×3×3 Rubik's Cube contains 4.3252 × 1019 states, and is too large to search exhaustively.
- ↑ Papadimitriou, Christos (1994), "On the complexity of the parity argument and other inefficient proofs of existence" (PDF), Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7, archived from the original (PDF) on 2016-03-04, retrieved 2011-07-12
- ↑ Immerman, Neil (1999), "Exercise 3.7 (Everything is a Graph)", Descriptive Complexity, Graduate Texts in Computer Science, Springer-Verlag, p. 48, ISBN 978-0-387-98600-5.
- ↑ Yannakakis, Mihalis (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2): 71–85, arXiv:0802.2831, doi:10.1016/j.cosrev.2009.03.004.
- ↑ Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), "Exponential algorithmic speedup by a quantum walk", Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 59–68, arXiv:quant-ph/0209131, doi:10.1145/780542.780552, MR 2121062.
- ↑ 7.0 7.1 Muller, John Harold (1988), Local structure in graph classes, Ph.D. thesis, Georgia Institute of Technology.
- ↑ 8.0 8.1 8.2 8.3 8.4 Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics, 5 (4): 596–603, doi:10.1137/0405049, MR 1186827.
- ↑ Chrobak, Marek; Eppstein, David (1991), "Planar orientations with low out-degree and compaction of adjacency matrices" (PDF), Theoretical Computer Science, 86 (2): 243–266, doi:10.1016/0304-3975(91)90020-3.
- ↑ 10.0 10.1 10.2 10.3 Spinrad, Jeremy P. (2003), "2. Implicit graph representation", Efficient Graph Representations, pp. 17–30, ISBN 0-8218-2815-0.
- ↑ Kang, Ross J.; Müller, Tobias (2011), Sphere and dot product representations of graphs (PDF), archived from the original (PDF) on 2012-03-16, retrieved 2011-07-12.
- ↑ Ma, Tze Heng; Spinrad, Jeremy P. (1991), "Cycle-free partial orders and chordal comparability graphs", Order, 8 (1): 49–61, doi:10.1007/BF00385814, MR 1129614.
- ↑ Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), "An implicit representation of chordal comparability graphs in linear time", Discrete Applied Mathematics, 158 (8): 869–875, doi:10.1016/j.dam.2010.01.005, MR 2602811.
- ↑ Alstrup, Stephen; Rauhe, Theis (2002), "Small induced-universal graphs and compact implicit graph representations" (PDF), Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 53–62, doi:10.1109/SFCS.2002.1181882, archived from the original (PDF) on 2011-09-27, retrieved 2011-07-13.
- ↑ Arnaud, Labourel; Gavoille, Cyril (2007), "Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs" (PDF), Proceedings of the 15th annual European Symposium on Algorithms, pp. 582–593, doi:10.1007/978-3-540-75520-3_52.
- ↑ Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał (2020), "Shorter Labeling Schemes for Planar Graphs", Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp. 446–462, arXiv:1908.03341, doi:10.1007/978-3-540-75520-3_52.
- ↑ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2020), "Adjacency Labelling for Planar Graphs (and Beyond)", 61st IEEE Annual Symposium on Foundations of Computer Science]], pp. 577–588, arXiv:2003.04280, doi:10.1007/978-3-540-75520-3_52.
- ↑ Rivest, Ronald L.; Vuillemin, Jean (1975), "A generalization and proof of the Aanderaa-Rosenberg conjecture", Proc. 7th ACM Symposium on Theory of Computing, Albuquerque, New Mexico, United States, pp. 6–11, doi:10.1145/800116.803747
{{citation}}: CS1 maint: location missing publisher (link). - ↑ Kahn, Jeff; Saks, Michael; Sturtevant, Dean (1983), "A topological approach to evasiveness", Symposium on Foundations of Computer Science, Los Alamitos, CA, USA: IEEE Computer Society, pp. 31–33, doi:10.1109/SFCS.1983.4.
- ↑ Bender, Michael A.; Ron, Dana (2000), "Testing acyclicity of directed graphs in sublinear time", Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci., vol. 1853, Berlin: Springer, pp. 809–820, doi:10.1007/3-540-45022-X_68, MR 1795937.
