अंतर्निहित ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
Line 2: Line 2:
ग्राफ़ एल्गोरिदम के अध्ययन में, एक '''अंतर्निहित ग्राफ़ प्रतिनिधित्व''' (या अधिक सरल रूप से '''अंतर्निहित ग्राफ़''') एक ऐसा ग्राफ़ होता है जिसके शीर्ष या किनारों को कंप्यूटर की मेमोरी में स्पष्ट ऑब्जेक्ट्स, बल्कि किसी अन्य इनपुट से एल्गोरिदमिक रूप से निर्धारित होते हैं, उदाहरण के लिए एक गणना योग्य फ़ंक्शन के रूप में दर्शाया नहीं जाता है।
ग्राफ़ एल्गोरिदम के अध्ययन में, एक '''अंतर्निहित ग्राफ़ प्रतिनिधित्व''' (या अधिक सरल रूप से '''अंतर्निहित ग्राफ़''') एक ऐसा ग्राफ़ होता है जिसके शीर्ष या किनारों को कंप्यूटर की मेमोरी में स्पष्ट ऑब्जेक्ट्स, बल्कि किसी अन्य इनपुट से एल्गोरिदमिक रूप से निर्धारित होते हैं, उदाहरण के लिए एक गणना योग्य फ़ंक्शन के रूप में दर्शाया नहीं जाता है।


==पड़ोस का प्रतिनिधित्व==
==परिवेश का प्रतिनिधित्व==
अंतर्निहित ग्राफ़ की धारणा विभिन्न खोज एल्गोरिदम में आम है जिन्हें ग्राफ़ के संदर्भ में वर्णित किया गया है। इस संदर्भ में, किसी निर्दिष्ट शीर्ष के लिए सभी पड़ोस (ग्राफ़ सिद्धांत) को परिभाषित करने के लिए एक अंतर्निहित ग्राफ़ को नियमों के एक सेट के रूप में परिभाषित किया जा सकता है।<ref>{{citation
अंतर्निहित ग्राफ़ की धारणा विभिन्न खोज एल्गोरिदम में आम है जिन्हें ग्राफ़ के संदर्भ में वर्णित किया गया है। इस संदर्भ में, एक अंतर्निहित ग्राफ़ को किसी निर्दिष्ट शीर्ष के सभी पड़ोसियों को परिभाषित करने के लिए नियमों के एक सेट के रूप में परिभाषित किया जा सकता है।<ref>{{citation
  | last = Korf | first = Richard E.
  | last = Korf | first = Richard E.
  | at = Article 26, 40pp
  | at = Article 26, 40pp
Line 12: Line 12:
  | title = Linear-time disk-based implicit graph search
  | title = Linear-time disk-based implicit graph search
  | volume = 55
  | volume = 55
  | year = 2008}}.</ref> इस प्रकार का अंतर्निहित ग्राफ प्रतिनिधित्व एक आसन्न सूची के अनुरूप है, जिसमें यह प्रत्येक शीर्ष के पड़ोसियों तक आसान पहुंच प्रदान करता है। उदाहरण के लिए, रूबिक क्यूब जैसी पहेली का समाधान खोजने में, कोई एक अंतर्निहित ग्राफ़ को परिभाषित कर सकता है जिसमें प्रत्येक शीर्ष घन के संभावित राज्यों में से एक का प्रतिनिधित्व करता है, और प्रत्येक किनारा एक राज्य से दूसरे राज्य में जाने का प्रतिनिधित्व करता है। पहेली में सभी संभावित चालों को आज़माकर और इनमें से प्रत्येक चाल द्वारा पहुँचे गए राज्यों का निर्धारण करके किसी भी शीर्ष के पड़ोसियों को उत्पन्न करना सीधा है; हालाँकि, एक अंतर्निहित प्रतिनिधित्व आवश्यक है, क्योंकि रूबिक क्यूब का राज्य स्थान इतना बड़ा है कि एक एल्गोरिदम इसके सभी राज्यों को सूचीबद्ध करने की अनुमति नहीं दे सकता है।<ref>{{citation|last=Korf|first=Richard E.|contribution=Minimizing disk I/O in two-bit breadth-first search|title=Proc. 23rd AAAI Conf. on Artificial Intelligence|year=2008|contribution-url=http://www.aaai.org/Papers/AAAI/2008/AAAI08-050.pdf|pages=317–324|quotation=The standard 3×3×3 Rubik's Cube contains 4.3252&nbsp;×&nbsp;10<sup>19</sup> states, and is too large to search exhaustively.}}</ref>
  | year = 2008}}.</ref> इस प्रकार का अंतर्निहित ग्राफ़ प्रतिनिधित्व एक आसन्नता सूची के अनुरूप है, जिसमें यह प्रत्येक शीर्ष के पड़ोसियों तक आसान पहुंच प्रदान करता है। उदाहरण के लिए, रूबिक क्यूब जैसी पहेली का समाधान खोजने में, कोई एक अंतर्निहित ग्राफ को परिभाषित कर सकता है जिसमें प्रत्येक शीर्ष घन की संभावित स्थितियों में से एक का प्रतिनिधित्व करता है, और प्रत्येक किनारा एक राज्य से दूसरे राज्य में जाने का प्रतिनिधित्व करता है। पहेली में सभी संभावित चालों को आज़माकर और इनमें से प्रत्येक चाल द्वारा पहुँची गई अवस्थाओं को निर्धारित करके किसी भी शीर्ष के पड़ोसियों को उत्पन्न करना सीधा है; हालाँकि, एक अंतर्निहित प्रतिनिधित्व आवश्यक है, क्योंकि रुबिक क्यूब का राज्य स्थान इतना बड़ा है कि एक एल्गोरिदम इसके सभी राज्यों को सूचीबद्ध करने की अनुमति नहीं दे सकता है।<ref>{{citation|last=Korf|first=Richard E.|contribution=Minimizing disk I/O in two-bit breadth-first search|title=Proc. 23rd AAAI Conf. on Artificial Intelligence|year=2008|contribution-url=http://www.aaai.org/Papers/AAAI/2008/AAAI08-050.pdf|pages=317–324|quotation=The standard 3×3×3 Rubik's Cube contains 4.3252&nbsp;×&nbsp;10<sup>19</sup> states, and is too large to search exhaustively.}}</ref>
 
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, अंतर्निहित ग्राफ़ के संबंध में कई जटिलता वर्गों को परिभाषित किया गया है, जैसा कि एक शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक नियम या एल्गोरिदम द्वारा ऊपर परिभाषित किया गया है। उदाहरण के लिए, [[पीपीए (जटिलता)|पीपीए]] समस्याओं का वह वर्ग है जिसमें इनपुट के रूप में एक अप्रत्यक्ष अंतर्निहित ग्राफ दिया जाता है (जिसमें कोने ''n''-बिट बाइनरी स्ट्रिंग होते हैं, किसी भी शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक बहुपद समय एल्गोरिदम के साथ) और विषम डिग्री का एक शीर्ष होता है ग्राफ़ में, और विषम डिग्री का दूसरा शीर्ष खोजना होगा। हाथ मिलाने की प्रमेयिका द्वारा, ऐसा शीर्ष मौजूद है; एनपी में किसी को ढूंढना एक समस्या है, लेकिन जिन समस्याओं को इस तरह से परिभाषित किया जा सकता है, जरूरी नहीं कि वे एनपी-पूर्ण हों, क्योंकि यह अज्ञात है कि पीपीए = एनपी है या नहीं। [[पीपीएडी (जटिलता)|पीपीएडी]] अंतर्निहित निर्देशित ग्राफ़ पर परिभाषित एक अनुरूप वर्ग है जिसने एल्गोरिथम गेम सिद्धांत में ध्यान आकर्षित किया है क्योंकि इसमें नैश संतुलन की गणना करने की समस्या शामिल है।[3] एक अंतर्निहित ग्राफ़ में एक शीर्ष से दूसरे शीर्ष तक पहुंच योग्यता का परीक्षण करने की समस्या का उपयोग एनएल सहित अंतरिक्ष-बद्ध गैर-नियतात्मक जटिलता वर्गों को चिह्नित करने के लिए भी किया जा सकता है (समस्याओं का वर्ग जिसे अंतर्निहित निर्देशित ग्राफ़ में पहुंच योग्यता द्वारा विशेषता दी जा सकती है जिनके शीर्ष ओ (लॉग n) हैं )-बिट बिटस्ट्रिंग्स), एसएल (अप्रत्यक्ष ग्राफ़ के लिए अनुरूप वर्ग), और पीएसपीएसीई (समस्याओं का वर्ग जिसे बहुपद-लंबाई बिटस्ट्रिंग्स के साथ अंतर्निहित ग्राफ़ में पहुंच द्वारा विशेषता दी जा सकती है)। इस जटिलता-सैद्धांतिक संदर्भ में, एक अंतर्निहित ग्राफ़ के शीर्ष एक गैर-नियतात्मक ट्यूरिंग मशीन की स्थितियों का प्रतिनिधित्व कर सकते हैं, और किनारे संभावित राज्य परिवर्तनों का प्रतिनिधित्व कर सकते हैं, लेकिन अंतर्निहित ग्राफ़ का उपयोग कई अन्य प्रकार की संयोजन संरचना का प्रतिनिधित्व करने के लिए भी किया जा सकता है। ] पीएलएस, एक अन्य जटिलता वर्ग, एक अंतर्निहित ग्राफ़ में स्थानीय ऑप्टिमा खोजने की जटिलता को पकड़ता है। [5]
 
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, अंतर्निहित ग्राफ़ के संबंध में कई [[जटिलता वर्ग]]ों को परिभाषित किया गया है, जैसा कि एक शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक नियम या एल्गोरिदम द्वारा ऊपर परिभाषित किया गया है। उदाहरण के लिए, [[पीपीए (जटिलता)]] समस्याओं का वह वर्ग है जिसमें इनपुट के रूप में एक अप्रत्यक्ष अंतर्निहित ग्राफ दिया जाता है (जिसमें कोने होते हैं) {{mvar|n}}-बिट बाइनरी स्ट्रिंग्स, किसी भी शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक बहुपद समय एल्गोरिथ्म के साथ) और ग्राफ़ में विषम डिग्री का एक शीर्ष, और विषम डिग्री का दूसरा शीर्ष खोजना होगा। हाथ मिलाने की प्रमेयिका द्वारा, ऐसा शीर्ष मौजूद है; किसी को ढूंढना [[एनपी (जटिलता)]] में एक समस्या है, लेकिन जिन समस्याओं को इस तरह से परिभाषित किया जा सकता है, जरूरी नहीं कि वे एनपी-पूर्ण हों, क्योंकि यह अज्ञात है कि पीपीए = एनपी है या नहीं। [[पीपीएडी (जटिलता)]] अंतर्निहित [[निर्देशित ग्राफ]]़ पर परिभाषित एक अनुरूप वर्ग है जिसने [[एल्गोरिथम गेम सिद्धांत]] में ध्यान आकर्षित किया है क्योंकि इसमें [[नैश संतुलन]] की गणना करने की समस्या शामिल है।<ref>{{citation | first = Christos | last = Papadimitriou | authorlink = Christos Papadimitriou | year = 1994 | title = On the complexity of the parity argument and other inefficient proofs of existence | journal = [[Journal of Computer and System Sciences]] | volume = 48 | issue = 3 | pages = 498–532 | url = http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf | doi = 10.1016/S0022-0000(05)80063-7 | access-date = 2011-07-12 | archive-url = https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf | archive-date = 2016-03-04 | url-status = dead }}</ref> एक अंतर्निहित ग्राफ़ में एक शीर्ष से दूसरे तक पहुंचने की क्षमता का परीक्षण करने की समस्या का उपयोग [[एनएल (जटिलता)]] सहित अंतरिक्ष-बद्ध गैर-नियतात्मक जटिलता वर्गों को चिह्नित करने के लिए भी किया जा सकता है (समस्याओं का वर्ग जो अंतर्निहित निर्देशित ग्राफ़ में पहुंच योग्यता द्वारा विशेषता हो सकती है जिनके कोने हैं) {{math|O(log ''n'')}}-बिट बिटस्ट्रिंग्स), [[एसएल (जटिलता)]] (अप्रत्यक्ष ग्राफ़ के लिए अनुरूप वर्ग), और पीएसपीएसीई (समस्याओं का वर्ग जिसे बहुपद-लंबाई बिटस्ट्रिंग्स के साथ अंतर्निहित ग्राफ़ में पहुंच द्वारा विशेषता दी जा सकती है)। इस जटिलता-सैद्धांतिक संदर्भ में, एक अंतर्निहित ग्राफ़ के शीर्ष एक [[गैर-नियतात्मक ट्यूरिंग मशीन]] की स्थितियों का प्रतिनिधित्व कर सकते हैं, और किनारे संभावित राज्य परिवर्तनों का प्रतिनिधित्व कर सकते हैं, लेकिन अंतर्निहित ग्राफ़ का उपयोग कई अन्य प्रकार की संयोजन संरचना का प्रतिनिधित्व करने के लिए भी किया जा सकता है।<ref>{{citation|title=Descriptive Complexity|title-link= Descriptive Complexity |contribution=Exercise 3.7 (Everything is a Graph)|first=Neil|last=Immerman|authorlink=Neil Immerman|page=48|contribution-url=https://books.google.com/books?id=kWSZ0OWnupkC&pg=PA48|series=Graduate Texts in Computer Science|year=1999|publisher=Springer-Verlag|isbn= 978-0-387-98600-5}}.</ref> [[पीएलएस (जटिलता)]], एक अन्य जटिलता वर्ग, एक अंतर्निहित ग्राफ़ में स्थानीय ऑप्टिमा खोजने की जटिलता को पकड़ता है।<ref>{{Citation | last1=Yannakakis | first1=Mihalis | author1-link=Mihalis Yannakakis | title=Equilibria, fixed points, and complexity classes | year=2009 | journal=Computer Science Review | volume=3 | issue=2 | pages=71–85 | doi=10.1016/j.cosrev.2009.03.004| arxiv=0802.2831 }}.</ref>
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, अंतर्निहित ग्राफ़ के संबंध में कई [[जटिलता वर्ग]]ों को परिभाषित किया गया है, जैसा कि एक शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक नियम या एल्गोरिदम द्वारा ऊपर परिभाषित किया गया है। उदाहरण के लिए, [[पीपीए (जटिलता)]] समस्याओं का वह वर्ग है जिसमें इनपुट के रूप में एक अप्रत्यक्ष अंतर्निहित ग्राफ दिया जाता है (जिसमें कोने होते हैं) {{mvar|n}}-बिट बाइनरी स्ट्रिंग्स, किसी भी शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक बहुपद समय एल्गोरिथ्म के साथ) और ग्राफ़ में विषम डिग्री का एक शीर्ष, और विषम डिग्री का दूसरा शीर्ष खोजना होगा। हाथ मिलाने की प्रमेयिका द्वारा, ऐसा शीर्ष मौजूद है; किसी को ढूंढना [[एनपी (जटिलता)]] में एक समस्या है, लेकिन जिन समस्याओं को इस तरह से परिभाषित किया जा सकता है, जरूरी नहीं कि वे एनपी-पूर्ण हों, क्योंकि यह अज्ञात है कि पीपीए = एनपी है या नहीं। [[पीपीएडी (जटिलता)]] अंतर्निहित [[निर्देशित ग्राफ]]़ पर परिभाषित एक अनुरूप वर्ग है जिसने [[एल्गोरिथम गेम सिद्धांत]] में ध्यान आकर्षित किया है क्योंकि इसमें [[नैश संतुलन]] की गणना करने की समस्या शामिल है।<ref>{{citation | first = Christos | last = Papadimitriou | authorlink = Christos Papadimitriou | year = 1994 | title = On the complexity of the parity argument and other inefficient proofs of existence | journal = [[Journal of Computer and System Sciences]] | volume = 48 | issue = 3 | pages = 498–532 | url = http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf | doi = 10.1016/S0022-0000(05)80063-7 | access-date = 2011-07-12 | archive-url = https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf | archive-date = 2016-03-04 | url-status = dead }}</ref> एक अंतर्निहित ग्राफ़ में एक शीर्ष से दूसरे तक पहुंचने की क्षमता का परीक्षण करने की समस्या का उपयोग [[एनएल (जटिलता)]] सहित अंतरिक्ष-बद्ध गैर-नियतात्मक जटिलता वर्गों को चिह्नित करने के लिए भी किया जा सकता है (समस्याओं का वर्ग जो अंतर्निहित निर्देशित ग्राफ़ में पहुंच योग्यता द्वारा विशेषता हो सकती है जिनके कोने हैं) {{math|O(log ''n'')}}-बिट बिटस्ट्रिंग्स), [[एसएल (जटिलता)]] (अप्रत्यक्ष ग्राफ़ के लिए अनुरूप वर्ग), और पीएसपीएसीई (समस्याओं का वर्ग जिसे बहुपद-लंबाई बिटस्ट्रिंग्स के साथ अंतर्निहित ग्राफ़ में पहुंच द्वारा विशेषता दी जा सकती है)। इस जटिलता-सैद्धांतिक संदर्भ में, एक अंतर्निहित ग्राफ़ के शीर्ष एक [[गैर-नियतात्मक ट्यूरिंग मशीन]] की स्थितियों का प्रतिनिधित्व कर सकते हैं, और किनारे संभावित राज्य परिवर्तनों का प्रतिनिधित्व कर सकते हैं, लेकिन अंतर्निहित ग्राफ़ का उपयोग कई अन्य प्रकार की संयोजन संरचना का प्रतिनिधित्व करने के लिए भी किया जा सकता है।<ref>{{citation|title=Descriptive Complexity|title-link= Descriptive Complexity |contribution=Exercise 3.7 (Everything is a Graph)|first=Neil|last=Immerman|authorlink=Neil Immerman|page=48|contribution-url=https://books.google.com/books?id=kWSZ0OWnupkC&pg=PA48|series=Graduate Texts in Computer Science|year=1999|publisher=Springer-Verlag|isbn= 978-0-387-98600-5}}.</ref> [[पीएलएस (जटिलता)]], एक अन्य जटिलता वर्ग, एक अंतर्निहित ग्राफ़ में स्थानीय ऑप्टिमा खोजने की जटिलता को पकड़ता है।<ref>{{Citation | last1=Yannakakis | first1=Mihalis | author1-link=Mihalis Yannakakis | title=Equilibria, fixed points, and complexity classes | year=2009 | journal=Computer Science Review | volume=3 | issue=2 | pages=71–85 | doi=10.1016/j.cosrev.2009.03.004| arxiv=0802.2831 }}.</ref>
जटिलता वर्गों के बीच अलगाव को साबित करने के लिए अंतर्निहित ग्राफ़ मॉडल का उपयोग सापेक्षता के एक रूप के रूप में भी किया गया है जो गैर-सापेक्ष मॉडल के लिए ज्ञात अलगाव से अधिक मजबूत हैं। उदाहरण के लिए, चिल्ड्स एट अल। ग्राफ़ ट्रैवर्सल समस्या को परिभाषित करने के लिए अंतर्निहित ग्राफ़ के पड़ोस प्रतिनिधित्व का उपयोग किया जाता है जिसे [[ एक कंप्यूटर जितना ]] पर बहुपद समय में हल किया जा सकता है लेकिन किसी भी शास्त्रीय कंप्यूटर पर हल करने के लिए घातीय समय की आवश्यकता होती है।<ref>{{citation
 
जटिलता वर्गों के बीच अलगाव को साबित करने के लिए अंतर्निहित ग्राफ़ मॉडल का उपयोग सापेक्षता के एक रूप के रूप में भी किया गया है जो गैर-सापेक्ष मॉडल के लिए ज्ञात अलगाव से अधिक मजबूत हैं। उदाहरण के लिए, चिल्ड्स एट अल। ग्राफ़ ट्रैवर्सल समस्या को परिभाषित करने के लिए अंतर्निहित ग्राफ़ के प्रतिवेशी प्रतिनिधित्व का उपयोग किया जाता है जिसे [[ एक कंप्यूटर जितना | एक कंप्यूटर जितना]] पर बहुपद समय में हल किया जा सकता है लेकिन किसी भी शास्त्रीय कंप्यूटर पर हल करने के लिए घातीय समय की आवश्यकता होती है।<ref>{{citation
  | last1 = Childs | first1 = Andrew M.
  | last1 = Childs | first1 = Andrew M.
  | last2 = Cleve | first2 = Richard
  | last2 = Cleve | first2 = Richard
Line 30: Line 34:
  | title = Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing
  | title = Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing
  | year = 2003| arxiv = quant-ph/0209131}}.</ref>
  | year = 2003| arxiv = quant-ph/0209131}}.</ref>




Line 178: Line 183:
}}.</ref>-लेकिन पूरा अनुमान खुला रहता है। यादृच्छिक एल्गोरिदम और क्वांटम एल्गोरिदम के लिए समस्या के वेरिएंट का भी अध्ययन किया गया है।
}}.</ref>-लेकिन पूरा अनुमान खुला रहता है। यादृच्छिक एल्गोरिदम और क्वांटम एल्गोरिदम के लिए समस्या के वेरिएंट का भी अध्ययन किया गया है।


बेंडर और रॉन ने दिखाया है कि, टालमटोल अनुमान के लिए उपयोग किए जाने वाले एक ही मॉडल में, केवल निरंतर समय में निर्देशित एसाइक्लिक ग्राफ़ को उन ग्राफ़ से अलग करना संभव है जो एसाइक्लिक होने से बहुत दूर हैं। इसके विपरीत, पड़ोस-आधारित अंतर्निहित ग्राफ़ मॉडल में इतना तेज़ समय संभव नहीं है,<ref>{{citation
बेंडर और रॉन ने दिखाया है कि, टालमटोल अनुमान के लिए उपयोग किए जाने वाले एक ही मॉडल में, केवल निरंतर समय में निर्देशित एसाइक्लिक ग्राफ़ को उन ग्राफ़ से अलग करना संभव है जो एसाइक्लिक होने से बहुत दूर हैं। इसके विपरीत, प्रतिवेशी-आधारित अंतर्निहित ग्राफ़ मॉडल में इतना तेज़ समय संभव नहीं है,<ref>{{citation
  | last1 = Bender | first1 = Michael A.
  | last1 = Bender | first1 = Michael A.
  | last2 = Ron | first2 = Dana | author2-link = Dana Ron
  | last2 = Ron | first2 = Dana | author2-link = Dana Ron

Revision as of 10:24, 2 August 2023

ग्राफ़ एल्गोरिदम के अध्ययन में, एक अंतर्निहित ग्राफ़ प्रतिनिधित्व (या अधिक सरल रूप से अंतर्निहित ग्राफ़) एक ऐसा ग्राफ़ होता है जिसके शीर्ष या किनारों को कंप्यूटर की मेमोरी में स्पष्ट ऑब्जेक्ट्स, बल्कि किसी अन्य इनपुट से एल्गोरिदमिक रूप से निर्धारित होते हैं, उदाहरण के लिए एक गणना योग्य फ़ंक्शन के रूप में दर्शाया नहीं जाता है।

परिवेश का प्रतिनिधित्व

अंतर्निहित ग्राफ़ की धारणा विभिन्न खोज एल्गोरिदम में आम है जिन्हें ग्राफ़ के संदर्भ में वर्णित किया गया है। इस संदर्भ में, एक अंतर्निहित ग्राफ़ को किसी निर्दिष्ट शीर्ष के सभी पड़ोसियों को परिभाषित करने के लिए नियमों के एक सेट के रूप में परिभाषित किया जा सकता है।[1] इस प्रकार का अंतर्निहित ग्राफ़ प्रतिनिधित्व एक आसन्नता सूची के अनुरूप है, जिसमें यह प्रत्येक शीर्ष के पड़ोसियों तक आसान पहुंच प्रदान करता है। उदाहरण के लिए, रूबिक क्यूब जैसी पहेली का समाधान खोजने में, कोई एक अंतर्निहित ग्राफ को परिभाषित कर सकता है जिसमें प्रत्येक शीर्ष घन की संभावित स्थितियों में से एक का प्रतिनिधित्व करता है, और प्रत्येक किनारा एक राज्य से दूसरे राज्य में जाने का प्रतिनिधित्व करता है। पहेली में सभी संभावित चालों को आज़माकर और इनमें से प्रत्येक चाल द्वारा पहुँची गई अवस्थाओं को निर्धारित करके किसी भी शीर्ष के पड़ोसियों को उत्पन्न करना सीधा है; हालाँकि, एक अंतर्निहित प्रतिनिधित्व आवश्यक है, क्योंकि रुबिक क्यूब का राज्य स्थान इतना बड़ा है कि एक एल्गोरिदम इसके सभी राज्यों को सूचीबद्ध करने की अनुमति नहीं दे सकता है।[2]

कम्प्यूटेशनल जटिलता सिद्धांत में, अंतर्निहित ग्राफ़ के संबंध में कई जटिलता वर्गों को परिभाषित किया गया है, जैसा कि एक शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक नियम या एल्गोरिदम द्वारा ऊपर परिभाषित किया गया है। उदाहरण के लिए, पीपीए समस्याओं का वह वर्ग है जिसमें इनपुट के रूप में एक अप्रत्यक्ष अंतर्निहित ग्राफ दिया जाता है (जिसमें कोने n-बिट बाइनरी स्ट्रिंग होते हैं, किसी भी शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक बहुपद समय एल्गोरिदम के साथ) और विषम डिग्री का एक शीर्ष होता है ग्राफ़ में, और विषम डिग्री का दूसरा शीर्ष खोजना होगा। हाथ मिलाने की प्रमेयिका द्वारा, ऐसा शीर्ष मौजूद है; एनपी में किसी को ढूंढना एक समस्या है, लेकिन जिन समस्याओं को इस तरह से परिभाषित किया जा सकता है, जरूरी नहीं कि वे एनपी-पूर्ण हों, क्योंकि यह अज्ञात है कि पीपीए = एनपी है या नहीं। पीपीएडी अंतर्निहित निर्देशित ग्राफ़ पर परिभाषित एक अनुरूप वर्ग है जिसने एल्गोरिथम गेम सिद्धांत में ध्यान आकर्षित किया है क्योंकि इसमें नैश संतुलन की गणना करने की समस्या शामिल है।[3] एक अंतर्निहित ग्राफ़ में एक शीर्ष से दूसरे शीर्ष तक पहुंच योग्यता का परीक्षण करने की समस्या का उपयोग एनएल सहित अंतरिक्ष-बद्ध गैर-नियतात्मक जटिलता वर्गों को चिह्नित करने के लिए भी किया जा सकता है (समस्याओं का वर्ग जिसे अंतर्निहित निर्देशित ग्राफ़ में पहुंच योग्यता द्वारा विशेषता दी जा सकती है जिनके शीर्ष ओ (लॉग n) हैं )-बिट बिटस्ट्रिंग्स), एसएल (अप्रत्यक्ष ग्राफ़ के लिए अनुरूप वर्ग), और पीएसपीएसीई (समस्याओं का वर्ग जिसे बहुपद-लंबाई बिटस्ट्रिंग्स के साथ अंतर्निहित ग्राफ़ में पहुंच द्वारा विशेषता दी जा सकती है)। इस जटिलता-सैद्धांतिक संदर्भ में, एक अंतर्निहित ग्राफ़ के शीर्ष एक गैर-नियतात्मक ट्यूरिंग मशीन की स्थितियों का प्रतिनिधित्व कर सकते हैं, और किनारे संभावित राज्य परिवर्तनों का प्रतिनिधित्व कर सकते हैं, लेकिन अंतर्निहित ग्राफ़ का उपयोग कई अन्य प्रकार की संयोजन संरचना का प्रतिनिधित्व करने के लिए भी किया जा सकता है। ] पीएलएस, एक अन्य जटिलता वर्ग, एक अंतर्निहित ग्राफ़ में स्थानीय ऑप्टिमा खोजने की जटिलता को पकड़ता है। [5]

कम्प्यूटेशनल जटिलता सिद्धांत में, अंतर्निहित ग्राफ़ के संबंध में कई जटिलता वर्गों को परिभाषित किया गया है, जैसा कि एक शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक नियम या एल्गोरिदम द्वारा ऊपर परिभाषित किया गया है। उदाहरण के लिए, पीपीए (जटिलता) समस्याओं का वह वर्ग है जिसमें इनपुट के रूप में एक अप्रत्यक्ष अंतर्निहित ग्राफ दिया जाता है (जिसमें कोने होते हैं) n-बिट बाइनरी स्ट्रिंग्स, किसी भी शीर्ष के पड़ोसियों को सूचीबद्ध करने के लिए एक बहुपद समय एल्गोरिथ्म के साथ) और ग्राफ़ में विषम डिग्री का एक शीर्ष, और विषम डिग्री का दूसरा शीर्ष खोजना होगा। हाथ मिलाने की प्रमेयिका द्वारा, ऐसा शीर्ष मौजूद है; किसी को ढूंढना एनपी (जटिलता) में एक समस्या है, लेकिन जिन समस्याओं को इस तरह से परिभाषित किया जा सकता है, जरूरी नहीं कि वे एनपी-पूर्ण हों, क्योंकि यह अज्ञात है कि पीपीए = एनपी है या नहीं। पीपीएडी (जटिलता) अंतर्निहित निर्देशित ग्राफ़ पर परिभाषित एक अनुरूप वर्ग है जिसने एल्गोरिथम गेम सिद्धांत में ध्यान आकर्षित किया है क्योंकि इसमें नैश संतुलन की गणना करने की समस्या शामिल है।[3] एक अंतर्निहित ग्राफ़ में एक शीर्ष से दूसरे तक पहुंचने की क्षमता का परीक्षण करने की समस्या का उपयोग एनएल (जटिलता) सहित अंतरिक्ष-बद्ध गैर-नियतात्मक जटिलता वर्गों को चिह्नित करने के लिए भी किया जा सकता है (समस्याओं का वर्ग जो अंतर्निहित निर्देशित ग्राफ़ में पहुंच योग्यता द्वारा विशेषता हो सकती है जिनके कोने हैं) O(log n)-बिट बिटस्ट्रिंग्स), एसएल (जटिलता) (अप्रत्यक्ष ग्राफ़ के लिए अनुरूप वर्ग), और पीएसपीएसीई (समस्याओं का वर्ग जिसे बहुपद-लंबाई बिटस्ट्रिंग्स के साथ अंतर्निहित ग्राफ़ में पहुंच द्वारा विशेषता दी जा सकती है)। इस जटिलता-सैद्धांतिक संदर्भ में, एक अंतर्निहित ग्राफ़ के शीर्ष एक गैर-नियतात्मक ट्यूरिंग मशीन की स्थितियों का प्रतिनिधित्व कर सकते हैं, और किनारे संभावित राज्य परिवर्तनों का प्रतिनिधित्व कर सकते हैं, लेकिन अंतर्निहित ग्राफ़ का उपयोग कई अन्य प्रकार की संयोजन संरचना का प्रतिनिधित्व करने के लिए भी किया जा सकता है।[4] पीएलएस (जटिलता), एक अन्य जटिलता वर्ग, एक अंतर्निहित ग्राफ़ में स्थानीय ऑप्टिमा खोजने की जटिलता को पकड़ता है।[5]

जटिलता वर्गों के बीच अलगाव को साबित करने के लिए अंतर्निहित ग्राफ़ मॉडल का उपयोग सापेक्षता के एक रूप के रूप में भी किया गया है जो गैर-सापेक्ष मॉडल के लिए ज्ञात अलगाव से अधिक मजबूत हैं। उदाहरण के लिए, चिल्ड्स एट अल। ग्राफ़ ट्रैवर्सल समस्या को परिभाषित करने के लिए अंतर्निहित ग्राफ़ के प्रतिवेशी प्रतिनिधित्व का उपयोग किया जाता है जिसे एक कंप्यूटर जितना पर बहुपद समय में हल किया जा सकता है लेकिन किसी भी शास्त्रीय कंप्यूटर पर हल करने के लिए घातीय समय की आवश्यकता होती है।[6]


आसन्नता लेबलिंग योजनाएं

ग्राफ़ के कुशल प्रतिनिधित्व के संदर्भ में, जे.एच. मुलर ने ग्राफ़ के लिए एक स्थानीय संरचना या आसन्न लेबलिंग योजना को परिभाषित किया G किसी दिए गए परिवार में F ग्राफ़ का एक असाइनमेंट होना O(log n)-प्रत्येक शीर्ष के लिए बिट पहचानकर्ता G, एक एल्गोरिदम के साथ (जो इस पर निर्भर हो सकता है F लेकिन व्यक्तिगत ग्राफ़ से स्वतंत्र है G) जो इनपुट के रूप में दो शीर्ष पहचानकर्ताओं को लेता है और यह निर्धारित करता है कि वे किनारे के अंतिम बिंदु हैं या नहीं G. अर्थात्, इस प्रकार का अंतर्निहित प्रतिनिधित्व एक आसन्न मैट्रिक्स के अनुरूप है: यह जांचना सीधा है कि क्या दो शीर्ष आसन्न हैं, लेकिन किसी भी शीर्ष के पड़ोसियों को खोजने में सभी शीर्षों के माध्यम से लूपिंग और परीक्षण करना शामिल हो सकता है कि कौन पड़ोसी हैं।[7] निकटवर्ती लेबलिंग योजनाओं वाले ग्राफ़ परिवारों में शामिल हैं:

परिबद्ध डिग्री ग्राफ़
यदि प्रत्येक शीर्ष Gअधिकतम है d पड़ोसियों, कोई भी शीर्षों को क्रमांकित कर सकता है G 1 से n और शीर्ष के लिए पहचानकर्ता होने दें (d + 1)-अपनी स्वयं की संख्या और अपने पड़ोसियों की संख्या का योग। दो शीर्ष तब आसन्न होते हैं जब उनके पहचानकर्ताओं में पहली संख्या बाद में दूसरे शीर्ष के पहचानकर्ता में दिखाई देती है। अधिक आम तौर पर, एक ही दृष्टिकोण का उपयोग बाउंडेड आर्बोरिसिटी या बाउंडेड डिजनरेसी (ग्राफ सिद्धांत) वाले ग्राफ़ के लिए एक अंतर्निहित प्रतिनिधित्व प्रदान करने के लिए किया जा सकता है, जिसमें समतलीय ग्राफ और किसी भी रॉबर्टसन-सेमुर प्रमेय | लघु-बंद ग्राफ़ परिवार में ग्राफ़ शामिल हैं।[8][9]
इंटरसेक्शन ग्राफ
एक अंतराल ग्राफ वास्तविक रेखा में रेखा खंडों के एक सेट का इंटरसेक्शन ग्राफ है। इसे एक आसन्नता लेबलिंग योजना दी जा सकती है जिसमें रेखा खंडों के अंतिम बिंदुओं को 1 से 2n तक क्रमांकित किया जाता है और ग्राफ़ के प्रत्येक शीर्ष को उसके संबंधित अंतराल के दो समापन बिंदुओं की संख्या द्वारा दर्शाया जाता है। इस प्रतिनिधित्व के साथ, कोई यह जांच सकता है कि क्या दो शीर्ष उन संख्याओं की तुलना करके आसन्न हैं जो उनका प्रतिनिधित्व करते हैं और यह सत्यापित करते हैं कि ये संख्याएं ओवरलैपिंग अंतराल को परिभाषित करती हैं। यही दृष्टिकोण अन्य ज्यामितीय प्रतिच्छेदन ग्राफ़ के लिए भी काम करता है, जिसमें सीमाबद्ध बॉक्सिसिटी और वृत्त ग्राफ के ग्राफ़ और इन परिवारों के उपपरिवार जैसे दूरी-वंशानुगत ग्राफ़ और कॉग्रफ़ ़ शामिल हैं।[8][10]हालाँकि, एक ज्यामितीय प्रतिच्छेदन ग्राफ प्रतिनिधित्व हमेशा एक आसन्नता लेबलिंग योजना के अस्तित्व का संकेत नहीं देता है, क्योंकि प्रत्येक ज्यामितीय वस्तु को निर्दिष्ट करने के लिए बिट्स की लघुगणकीय संख्या से अधिक की आवश्यकता हो सकती है। उदाहरण के लिए, एक ग्राफ़ को एक यूनिट डिस्क ग्राफ़ के रूप में प्रस्तुत करने के लिए डिस्क केंद्रों के निर्देशांक के लिए तेजी से कई बिट्स की आवश्यकता हो सकती है।[11]
निम्न-आयामी तुलनीयता ग्राफ़
आंशिक रूप से ऑर्डर किए गए सेट के लिए तुलनीयता ग्राफ़ में प्रत्येक सेट तत्व के लिए एक शीर्ष होता है और दो सेट तत्वों के बीच एक किनारा होता है जो आंशिक क्रम से संबंधित होते हैं। आंशिक क्रम का क्रम आयाम रैखिक आदेशों की न्यूनतम संख्या है जिसका प्रतिच्छेदन दिया गया आंशिक क्रम है। यदि किसी आंशिक क्रम में सीमाबद्ध क्रम आयाम है, तो इसके तुलनीयता ग्राफ में शीर्षों के लिए एक आसन्नता लेबलिंग योजना को प्रत्येक परिभाषित रैखिक क्रम में अपनी स्थिति के साथ प्रत्येक शीर्ष को लेबल करके परिभाषित किया जा सकता है, और यह निर्धारित किया जा सकता है कि दो शीर्ष आसन्न हैं यदि उनके लेबल में संख्याओं की प्रत्येक संगत जोड़ी का एक दूसरे जोड़े के समान क्रम संबंध है। विशेष रूप से, यह कॉर्डल ग्राफ़ तुलनीयता ग्राफ़ के लिए एक आसन्नता लेबलिंग योजना की अनुमति देता है, जो अधिकतम चार आयामों के आंशिक आदेशों से आते हैं।[12][13]


अंतर्निहित ग्राफ़ अनुमान

Unsolved problem in mathematics:

Does every slowly-growing hereditary family of graphs have an implicit representation?

(more unsolved problems in mathematics)

सभी ग्राफ़ परिवारों में स्थानीय संरचनाएँ नहीं होती हैं। कुछ परिवारों के लिए, एक साधारण गिनती तर्क साबित करता है कि आसन्नता लेबलिंग योजनाएं मौजूद नहीं हैं: केवल 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]


यह भी देखें

संदर्भ

  1. ↑ 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.
  2. ↑ 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.
  3. ↑ 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
  4. ↑ 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.
  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.
  6. ↑ 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. ↑ 7.0 7.1 Muller, John Harold (1988), Local structure in graph classes, Ph.D. thesis, Georgia Institute of Technology.
  8. ↑ 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.
  9. ↑ 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. ↑ 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.
  11. ↑ 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.
  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.
  13. ↑ 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.
  14. ↑ 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.
  15. ↑ 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.
  16. ↑ 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.
  17. ↑ 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.
  18. ↑ 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).
  19. ↑ 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.
  20. ↑ 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अंतर्निहित_ग्राफ&oldid=264567’