ग्राफ समरूपता समस्या: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 14: Line 14:


इससे पूर्व, सबसे अच्छा वर्तमान में स्वीकृत सैद्धांतिक एल्गोरिथम  {{harvtxt|बाबई|लुक्स|1983}} के कारण था, और यह लुक्स (1982) के पहले कार्य पर आधारित है, जो वी. एन. ज़ेमल्याचेंको {{harv|ज़ेम्लियाचेंको|कोर्नीनको|टायीशकेविच|1985}} के सबफैक्टोरियल एल्गोरिथम  के साथ संयुक्त है। एल्गोरिथम का रन टाइम 2 है, <sup>({{sqrt|''n''&nbsp;log&nbsp;''n''}})</sup> n शीर्षों वाले ग्राफ़ के लिए और परिमित सरल समूहों के वर्गीकरण पर निर्भर करता है। इस वर्गीकरण में प्रमेय के अतिरिक्त, थोड़ा कमजोर बंधन होता है।
इससे पूर्व, सबसे अच्छा वर्तमान में स्वीकृत सैद्धांतिक एल्गोरिथम  {{harvtxt|बाबई|लुक्स|1983}} के कारण था, और यह लुक्स (1982) के पहले कार्य पर आधारित है, जो वी. एन. ज़ेमल्याचेंको {{harv|ज़ेम्लियाचेंको|कोर्नीनको|टायीशकेविच|1985}} के सबफैक्टोरियल एल्गोरिथम  के साथ संयुक्त है। एल्गोरिथम का रन टाइम 2 है, <sup>({{sqrt|''n''&nbsp;log&nbsp;''n''}})</sup> n शीर्षों वाले ग्राफ़ के लिए और परिमित सरल समूहों के वर्गीकरण पर निर्भर करता है। इस वर्गीकरण में प्रमेय के अतिरिक्त, थोड़ा कमजोर बंधन होता है।
  {{math|2<sup>O({{sqrt|''n''}}&nbsp;log<sup>2</sup>&nbsp;''n'')</sup>|size=100%}} द्वारा सबसे पहले {{harvs|authorlink=László Babai|first=लेज़्लो|last=बाबई|year=1980|txt}} द्वारा दृढ़ता से नियमित रेखांकन के लिए प्राप्त किया गया था, और उसके पश्चात {{harvtxt|बाबई|लुक्स|1983}} द्वारा सामान्य रेखांकन तक बढ़ाया गया,घातांक में सुधार √n एक प्रमुख खुली समस्या है; दृढ़ता से नियमित रेखांकन के लिए यह स्पीलमैन (1996) द्वारा किया गया था। बाउंडेड रैंक के हाइपरग्राफ के लिए, बाबई और कोडनोटी (2008) द्वारा ग्राफ़ के विषय से मेल खाने वाली एक उप-घातीय ऊपरी सीमा प्राप्त की गई थी।
  {{math|2<sup>O({{sqrt|''n''}}&nbsp;log<sup>2</sup>&nbsp;''n'')</sup>|size=100%}} द्वारा सबसे पहले {{harvs|authorlink=László Babai|first=लेज़्लो|last=बाबई|year=1980|txt}} द्वारा दृढ़ता से नियमित ग्राफ के लिए प्राप्त किया गया था, और उसके पश्चात {{harvtxt|बाबई|लुक्स|1983}} द्वारा सामान्य ग्राफ तक बढ़ाया गया,घातांक में सुधार √n एक प्रमुख खुली समस्या है; दृढ़ता से नियमित ग्राफ के लिए यह स्पीलमैन (1996) द्वारा किया गया था। बाउंडेड रैंक के हाइपरग्राफ के लिए, बाबई और कोडनोटी (2008) द्वारा ग्राफ़ के विषय से मेल खाने वाली एक उप-घातीय ऊपरी सीमा प्राप्त की गई थी।


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


ग्राफ समरूपता समस्या संगणनात्मक रूप से एक ग्राफ के स्वसमाकृतिकता समूह की गणना करने की समस्या के समान है, [16] [17] और क्रमपरिवर्तन समूह समरूपता समस्या और क्रमचय समूह चौराहे की समस्या से कमजोर है। पश्चात की दो समस्याओं के लिए, बाबई, कांटोर और लुक्स (1983) ने ग्राफ समरूपता के समान जटिलता सीमाएँ प्राप्त कीं।
ग्राफ समरूपता समस्या संगणनात्मक रूप से एक ग्राफ के स्वसमाकृतिकता समूह की गणना करने की समस्या के समान है, [16] [17] और क्रमपरिवर्तन समूह समरूपता समस्या और क्रमचय समूह प्रतिच्छेद की समस्या से कमजोर है। पश्चात की दो समस्याओं के लिए, बाबई, कांटोर और लुक्स (1983) ने ग्राफ समरूपता के समान जटिलता सीमाएँ प्राप्त कीं।


== हल किए गए विशेष मामले ==
== हल किए गए विशेष विषय ==
ग्राफ समरूपता समस्या के कई महत्वपूर्ण विशेष मामलों में कुशल, बहुपद-समय समाधान हैं:
ग्राफ समरूपता समस्या के कई महत्वपूर्ण विशेष विषयों में कुशल, बहुपद-समय का समाधान हैं:
* [[ वृक्ष (ग्राफ सिद्धांत) ]] एस{{sfnp|Kelly|1957}}{{sfnp|Aho|Hopcroft|Ullman|1974|p=84-86}}
* [[ वृक्ष (ग्राफ सिद्धांत) ]] एस{{sfnp|Kelly|1957}}{{sfnp|Aho|Hopcroft|Ullman|1974|p=84-86}}
* प्लेनर रेखांकन{{sfnp|Hopcroft|Wong|1974}} (वास्तव में, प्लानर ग्राफ आइसोमोर्फिज्म [[एल (जटिलता)]] में है,{{sfnp|Datta|Limaye|Nimbhorkar|Thierauf|2009}} [[पी (जटिलता)]] में निहित एक वर्ग)
* प्लेनर ग्राफ {{sfnp|Hopcroft|Wong|1974}} (वास्तव में, प्लानर ग्राफ समरूपता [[एल (जटिलता)]] में है,{{sfnp|Datta|Limaye|Nimbhorkar|Thierauf|2009}} [[पी (जटिलता)]] में निहित एक वर्ग)
* अंतराल रेखांकन{{sfnp|Booth|Lueker|1979}}
* अंतराल ग्राफ{{sfnp|Booth|Lueker|1979}}
* क्रमपरिवर्तन रेखांकन{{sfnp|Colbourn|1981}}
* क्रमपरिवर्तन ग्राफ{{sfnp|Colbourn|1981}}
* परिपत्र रेखांकन{{sfnp|Muzychuk|2004}}
* परिपत्र ग्राफ{{sfnp|Muzychuk|2004}}
* परिबद्ध-पैरामीटर रेखांकन
* परिबद्ध-पैरामीटर ग्राफ
** परिबद्ध [[पेड़ की चौड़ाई]] का रेखांकन{{sfnp|Bodlaender|1990}}
** परिबद्ध [[पेड़ की चौड़ाई]] का ग्राफ{{sfnp|Bodlaender|1990}}
** बंधे हुए जीनस के रेखांकन (गणित)<ref>{{harvnb|Miller|1980}}; {{harvnb|Filotti|Mayer|1980}}.</ref> (प्लानर ग्राफ जीनस 0 के ग्राफ हैं।)
** बंधे हुए जीनस के ग्राफ (गणित)<ref>{{harvnb|Miller|1980}}; {{harvnb|Filotti|Mayer|1980}}.</ref> (प्लानर ग्राफ जीनस 0 के ग्राफ हैं।)
** बाउंडेड डिग्री के रेखांकन (ग्राफ सिद्धांत){{sfnp|Luks|1982}}
** बाउंडेड डिग्री के ग्राफ (ग्राफ सिद्धांत){{sfnp|Luks|1982}}
** बंधे हुए [[eigenvalue|आइनवैल्यू]] बहुलता वाले रेखांकन{{sfnp|Babai|Grigoryev|Mount|1982}}
** बंधे हुए [[eigenvalue|आइनवैल्यू]] बहुलता वाले ग्राफ{{sfnp|Babai|Grigoryev|Mount|1982}}
** के-संकुचन योग्य रेखांकन (परिबद्ध डिग्री और परिबद्ध जीनस का एक सामान्यीकरण){{sfnp|Miller|1983}}
** के-संकुचन योग्य ग्राफ (परिबद्ध डिग्री और परिबद्ध जीनस का एक सामान्यीकरण){{sfnp|Miller|1983}}
** रंग-संरक्षण आइसोमोर्फिज्म [[रंगीन ग्राफ]] का बंधी हुई रंग बहुलता के साथ (अर्थात, अधिकांश के कोने में एक निश्चित के के लिए समान रंग होता है) वर्ग एनसी (जटिलता) में है, जो पी (जटिलता) का एक उपवर्ग है।{{sfnp|Luks|1986}}
** रंग-संरक्षण समरूपता [[रंगीन ग्राफ]] का बंधी हुई रंग बहुलता के साथ (अर्थात, अधिकांश के कोने में एक निश्चित के के लिए समान रंग होता है) वर्ग एनसी (जटिलता) में है, जो पी (जटिलता) का एक उपवर्ग है।{{sfnp|Luks|1986}}


== जटिलता वर्ग जीआई ==
== जटिलता वर्ग जीआई ==
चूंकि ग्राफ समरूपता समस्या न तो एनपी-पूर्ण होने के लिए जानी जाती है, और न ही लचीला होने के लिए जानी जाती है, शोधकर्ताओं ने एक नई कक्षा जीआई को परिभाषित करके समस्या में अंतर्दृष्टि प्राप्त करने की मांग की है, ग्राफ समरूपता में [[बहुपद-समय ट्यूरिंग कमी]] के साथ समस्याओं का समुच्चय संकट।<ref>{{harvnb|Booth|Colbourn|1977}}; {{harvnb|Köbler|Schöning|Torán|1993}}.</ref> यदि वास्तव में ग्राफ समरूपता समस्या बहुपद समय में हल करने योग्य है, तो जीआई पी (जटिलता) के बराबर होगा। दूसरी ओर, यदि समस्या एनपी-पूर्ण है, तो जीआई [[एनपी (जटिलता)]] के बराबर होगा और एनपी में सभी समस्याएं अर्ध-बहुपद समय में हल करने योग्य होंगी।
चूंकि ग्राफ समरूपता समस्या न तो एनपी-पूर्ण होने के लिए जानी जाती है, और न ही लचीला होने के लिए जानी जाती है, शोधकर्ताओं ने एक नई कक्षा जीआई को परिभाषित करके समस्या में अंतर्दृष्टि प्राप्त करने की मांग की है, ग्राफ समरूपता में [[बहुपद-समय ट्यूरिंग कमी]] के साथ समस्याओं का समुच्चय संकट।<ref>{{harvnb|Booth|Colbourn|1977}}; {{harvnb|Köbler|Schöning|Torán|1993}}.</ref> यदि वास्तव में ग्राफ समरूपता समस्या बहुपद समय में हल करने योग्य है, तो जीआई पी (जटिलता) के समान होगा। दूसरी ओर, यदि समस्या एनपी-पूर्ण है, तो जीआई [[एनपी (जटिलता)]] के समान होगा और एनपी में सभी समस्याएं अर्ध-बहुपद समय में हल करने योग्य होंगी।


जैसा कि बहुपद समय पदानुक्रम के भीतर जटिलता वर्गों के लिए आम है, एक समस्या को जीआई-हार्ड कहा जाता है यदि जीआई में किसी भी समस्या से बहुपद-समय ट्यूरिंग कमी होती है, यानी, जीआई-हार्ड समस्या का बहुपद-समय समाधान ग्राफ समरूपता समस्या (और इसलिए जीआई में सभी समस्याएं) के लिए बहुपद-समय समाधान प्राप्त होगा। एक समस्या <math>X</math> जीआई, या जीआई-पूर्ण के लिए [[पूर्ण (जटिलता)]] कहा जाता है, यदि यह जीआई-हार्ड और जीआई समस्या का बहुपद-समय समाधान दोनों है, तो बहुपद-समय समाधान प्राप्त होगा <math>X</math>.
जैसा कि बहुपद समय पदानुक्रम के भीतर जटिलता वर्गों के लिए साधारण है, एक समस्या को जीआई-हार्ड कहा जाता है, यदि जीआई में किसी भी समस्या से बहुपद-समय ट्यूरिंग कमी होती है, अर्थात, जीआई-हार्ड समस्या का बहुपद-समय समाधान ग्राफ समरूपता समस्या (और इसलिए जीआई में सभी समस्याएं) के लिए बहुपद-समय समाधान प्राप्त होगा। एक समस्या <math>X</math> जीआई, या जीआई-पूर्ण के लिए [[पूर्ण (जटिलता)]] कहा जाता है, यदि यह जीआई-हार्ड और जीआई समस्या का बहुपद-समय समाधान दोनों है, तो बहुपद-समय समाधान प्राप्त होगा <math>X</math>.


ग्राफ समरूपता समस्या एनपी और सह-[[एएम (जटिलता)]] दोनों में समाहित है। जीआई समानता पी के लिए और निम्न (जटिलता) में निहित है, साथ ही संभावित रूप से बहुत छोटे वर्ग एसपीपी में निहित है।<ref>{{harvnb|Köbler|Schöning|Torán|1992}}; {{harvnb|Arvind|Kurur|2006}}</ref> यह समता पी में निहित है इसका तात्पर्य है, कि ग्राफ समरूपता समस्या यह निर्धारित करने से ज्यादा कठिन नहीं है कि क्या एक बहुपद-समय के [[गैर-नियतात्मक ट्यूरिंग मशीन]] में स्वीकृत पथों की एक सम या विषम संख्या है। जीआई भी [[ZPP (जटिलता)|जेडपीपी (जटिलता)]] के लिए निहित और निम्न है<sup>एनपी</sup>.{{sfnp|Arvind|Köbler|2000}} इसका अनिवार्य रूप से तात्पर्य है कि एनपी [[ओरेकल मशीन]] तक पहुंच के साथ एक कुशल [[लास वेगास एल्गोरिथम]] ग्राफ समरूपता को इतनी आसानी से हल कर सकता है, कि इसे निरंतर समय में ऐसा करने की क्षमता देने से कोई शक्ति नहीं मिलती है।
ग्राफ समरूपता समस्या एनपी और सह-[[एएम (जटिलता)]] दोनों में समाहित है। जीआई समानता पी के लिए और निम्न (जटिलता) में निहित है, साथ ही संभावित रूप से बहुत छोटे वर्ग एसपीपी में निहित है।<ref>{{harvnb|Köbler|Schöning|Torán|1992}}; {{harvnb|Arvind|Kurur|2006}}</ref> यह समता पी में निहित है इसका तात्पर्य है, कि ग्राफ समरूपता समस्या यह निर्धारित करने से ज्यादा कठिन नहीं है कि क्या एक बहुपद-समय के [[गैर-नियतात्मक ट्यूरिंग मशीन]] में स्वीकृत पथों की एक सम या विषम संख्या है। जीआई भी [[ZPP (जटिलता)|जेडपीपी<sup>एनपी</sup> (जटिलता)]] के लिए निहित और निम्न है,.{{sfnp|Arvind|Köbler|2000}} इसका अनिवार्य रूप से तात्पर्य है, कि एनपी [[ओरेकल मशीन]] तक पहुंच के साथ एक कुशल [[लास वेगास एल्गोरिथम]] ग्राफ समरूपता को इतनी आसानी से हल कर सकता है, कि इसे निरंतर समय में ऐसा करने की क्षमता देने से कोई शक्ति नहीं मिलती है।


===जीआई-पूर्ण और जीआई-हार्ड समस्याएं===
===जीआई-पूर्ण और जीआई-हार्ड समस्याएं===
Line 46: Line 46:
==== अन्य वस्तुओं की समरूपता ====
==== अन्य वस्तुओं की समरूपता ====
गणितीय वस्तुओं के कई वर्ग हैं जिनके लिए समरूपता की समस्या एक जीआई-पूर्ण समस्या है। उनमें से कई अतिरिक्त गुणों या प्रतिबंधों से संपन्न ग्राफ़ हैं:<ref name=zkt>{{harvtxt|Zemlyachenko|Korneenko|Tyshkevich|1985}}</ref>
गणितीय वस्तुओं के कई वर्ग हैं जिनके लिए समरूपता की समस्या एक जीआई-पूर्ण समस्या है। उनमें से कई अतिरिक्त गुणों या प्रतिबंधों से संपन्न ग्राफ़ हैं:<ref name=zkt>{{harvtxt|Zemlyachenko|Korneenko|Tyshkevich|1985}}</ref>
* [[निर्देशित ग्राफ]]<ref name=zkt/>* लेबल वाले ग्राफ़, इस प्रावधान के साथ कि लेबल को संरक्षित करने के लिए एक समरूपता की आवश्यकता नहीं है,<ref name=zkt/>लेकिन केवल समान लेबल वाले शीर्षों के युग्मों वाला [[तुल्यता संबंध]]
* [[निर्देशित ग्राफ]]<ref name=zkt/>* लेबल वाले ग्राफ़, इस प्रावधान के साथ कि लेबल को संरक्षित करने के लिए एक समरूपता की आवश्यकता नहीं है,<ref name=zkt/>परन्तु केवल समान लेबल वाले शीर्षों के युग्मों वाला [[तुल्यता संबंध]]
* ध्रुवीकृत रेखांकन (एक पूर्ण ग्राफ K से बना है<sub>m</sub> और एक [[खाली ग्राफ]] K<sub>n</sub> साथ ही दोनों को जोड़ने वाले कुछ किनारे; उनके समरूपता को विभाजन को बनाए रखना चाहिए)<ref name=zkt/>* 2-रंगीन रेखांकन<ref name=zkt/>* स्पष्ट रूप से दी गई परिमित [[संरचना (गणितीय तर्क)]]।<ref name=zkt/>* [[मल्टीग्राफ]]<ref name=zkt/>* हाइपरग्राफ<ref name=zkt/>*स्वचालित रूप से समाप्त<ref name=zkt/>* [[मार्कोव निर्णय प्रक्रिया]]{{sfnp|Narayanamurthy|Ravindran|2008}}
* ध्रुवीकृत ग्राफ (एक पूर्ण ग्राफ K से बना है<sub>m</sub> और एक [[खाली ग्राफ]] K<sub>n</sub> साथ ही दोनों को जोड़ने वाले कुछ किनारे; उनके समरूपता को विभाजन को बनाए रखना चाहिए)<ref name=zkt/>* 2-रंगीन ग्राफ<ref name=zkt/>* स्पष्ट रूप से दी गई परिमित [[संरचना (गणितीय तर्क)]]।<ref name=zkt/>* [[मल्टीग्राफ]]<ref name=zkt/>* हाइपरग्राफ<ref name=zkt/>*स्वचालित रूप से समाप्त<ref name=zkt/>* [[मार्कोव निर्णय प्रक्रिया]]{{sfnp|Narayanamurthy|Ravindran|2008}}
* क्रम[[विनिमेय]] वर्ग 3 [[ nilpotent ]] (यानी, xyz = 0 हर तत्व x, y, z) [[ semigroup ]] के लिए<ref name=zkt/>* रेडिकल पर जीरो स्क्वेयर रेडिकल और कम्यूटेटिव फैक्टर के साथ फिक्स्ड बीजगणितीय रूप से बंद फील्ड पर एक फील्ड पर परिमित रैंक सहयोगी बीजगणित।<ref name=zkt/>{{sfnp|Grigor'ev|1981}}
* क्रम[[विनिमेय]] वर्ग 3 [[Index.php?title=निल्पोटेंट|निलपोटेंट]] (अर्थात, xyz = 0 हर तत्व x, y, z) [[ semigroup | उपसमूह]] के लिए<ref name=zkt/>* रेडिकल पर जीरो स्क्वेयर रेडिकल और संगड़कीय फैक्टर के साथ फिक्स्ड बीजगणितीय रूप से बंद क्षेत्र पर एक परिमित रैंक सहयोगी बीजगणित।<ref name=zkt/>{{sfnp|Grigor'ev|1981}}
*संदर्भ-मुक्त व्याकरण<ref name=zkt/>*[[संतुलित अपूर्ण ब्लॉक अभिकल्पना]]एँ<ref name=zkt/>* वर्टेक्स-पहलू घटनाओं द्वारा दर्शाए गए [[उत्तल पॉलीटॉप]] के [[कॉम्बिनेटरियल आइसोमोर्फिज्म]] को पहचानना।<ref>{{harvtxt|Johnson|2005}}; {{harvtxt|Kaibel|Schwartz|2003}}.</ref>
*संदर्भ-मुक्त व्याकरण<ref name=zkt/>*[[संतुलित अपूर्ण ब्लॉक अभिकल्पना]]एँ<ref name=zkt/>* वर्टेक्स-पहलू घटनाओं द्वारा दर्शाए गए [[उत्तल पॉलीटॉप]] के [[कॉम्बिनेटरियल आइसोमोर्फिज्म|मिश्रित समरूपता]] को पहचानना।<ref>{{harvtxt|Johnson|2005}}; {{harvtxt|Kaibel|Schwartz|2003}}.</ref>
==== जीआई - रेखांकन की पूरी कक्षाएं ====
==== जीआई - ग्राफ की पूरी कक्षाएं ====
ग्राफ़ के एक वर्ग को जीआई-पूर्ण कहा जाता है यदि इस उपवर्ग से ग्राफ़ के लिए समरूपता की पहचान एक जीआई-पूर्ण समस्या है। निम्नलिखित वर्ग जीआई-पूर्ण हैं:<ref name=zkt/>* जुड़े रेखांकन<ref name=zkt/>
ग्राफ़ के एक वर्ग को जीआई-पूर्ण कहा जाता है यदि इस उपवर्ग से ग्राफ़ के लिए समरूपता की पहचान एक जीआई-पूर्ण समस्या है। निम्नलिखित वर्ग जीआई-पूर्ण हैं:<ref name=zkt/>* जुड़े ग्राफ<ref name=zkt/>
* व्यास के रेखांकन (ग्राफ सिद्धांत) 2 और [[त्रिज्या (ग्राफ सिद्धांत)]] 1<ref name=zkt/>* निर्देशित विश्वकोश रेखांकन<ref name=zkt/>
* व्यास के ग्राफ (ग्राफ सिद्धांत) 2 और [[त्रिज्या (ग्राफ सिद्धांत)]] 1<ref name=zkt/>* निर्देशित विश्वकोश ग्राफ<ref name=zkt/>
* नियमित रेखांकन<ref name=zkt/>
* नियमित ग्राफ<ref name=zkt/>
* गैर-तुच्छ दृढ़ता से नियमित ग्राफ के बिना द्विदलीय ग्राफ<ref name=zkt/>
* गैर-तुच्छ दृढ़ता से नियमित ग्राफ के बिना द्विदलीय ग्राफ<ref name=zkt/>
* द्विदलीय ऑयलरीय रेखांकन<ref name=zkt/>
* द्विदलीय ऑयलरीय ग्राफ<ref name=zkt/>
* द्विदलीय नियमित रेखांकन<ref name=zkt/>
* द्विदलीय नियमित ग्राफ<ref name=zkt/>
* रेखा रेखांकन<ref name=zkt/>
* रेखा ग्राफ<ref name=zkt/>
* रेखांकन विभाजित करें{{sfnp|Chung|1985}}
* ग्राफ विभाजित करें{{sfnp|Chung|1985}}
* तारकीय रेखांकन<ref name=zkt/>
* तारकीय ग्राफ<ref name=zkt/>
* नियमित स्व-पूरक रेखांकन<ref name=zkt/>
* नियमित स्व-पूरक ग्राफ<ref name=zkt/>
* मनमाना आयामों में सामान्य, सरल पॉलीटोप, और [[[[साधारण पॉलीटॉप]]]] उत्तल पॉलीटोप्स के [[पॉलीटॉपल ग्राफ]]।{{sfnp|Kaibel|Schwartz|2003}}
* मनमाना आयामों में सामान्य, सरल पॉलीटोप, और [[[[साधारण पॉलीटॉप]]]] उत्तल पॉलीटोप्स के [[पॉलीटॉपल ग्राफ]]।{{sfnp|Kaibel|Schwartz|2003}}
डिग्राफ के कई वर्ग भी जीआई-पूर्ण हैं।
डिग्राफ के कई वर्ग भी जीआई-पूर्ण हैं।
Line 67: Line 67:
समरूपता समस्याओं के अलावा अन्य गैर-तुच्छ जीआई-पूर्ण समस्याएं भी हैं।
समरूपता समस्याओं के अलावा अन्य गैर-तुच्छ जीआई-पूर्ण समस्याएं भी हैं।
* किसी ग्राफ या डिग्राफ की आत्म-पूरकता की मान्यता।{{sfnp|Colbourn|Colbourn|1978}}
* किसी ग्राफ या डिग्राफ की आत्म-पूरकता की मान्यता।{{sfnp|Colbourn|Colbourn|1978}}
*तथाकथित एम-ग्राफ के एक वर्ग के लिए एक [[क्लिक समस्या]]। यह दिखाया गया है कि एन-वर्टेक्स ग्राफ के लिए एक आइसोमोर्फिज्म खोजना आकार एन के एम-ग्राफ में एन-क्लिक खोजने के बराबर है।<sup>2</उप>। यह तथ्य दिलचस्प है क्योंकि आकार n के एम-ग्राफ में क्रम (1−−ε)n के एक समूह को खोजने की समस्या<sup>2</sup> मनमाने ढंग से छोटे सकारात्मक ε के लिए एनपी-पूर्ण है।{{sfnp|Kozen|1978}}
*तथाकथित एम-ग्राफ के एक वर्ग के लिए एक [[क्लिक समस्या]]। यह दिखाया गया है कि एन-वर्टेक्स ग्राफ के लिए एक समरूपता खोजना आकार एन के एम-ग्राफ में एन-क्लिक खोजने के बराबर है।<sup>2</उप>। यह तथ्य दिलचस्प है क्योंकि आकार n के एम-ग्राफ में क्रम (1−−ε)n के एक समूह को खोजने की समस्या<sup>2</sup> मनमाने ढंग से छोटे सकारात्मक ε के लिए एनपी-पूर्ण है।{{sfnp|Kozen|1978}}
*2-परिसरों के होमोमोर्फिज्म की समस्या।{{sfnp|Shawe-Taylor|Pisanski|1994}}
*2-परिसरों के होमोमोर्फिज्म की समस्या।{{sfnp|Shawe-Taylor|Pisanski|1994}}


Line 74: Line 74:
* यह तय करने की समस्या कि [[वी-विवरण]] या [[एच-विवरण]] द्वारा दिए गए दो उत्तल पॉलीटोप्स प्रोजेक्टिवली या एफ़िनली आइसोमोर्फिक हैं। उत्तरार्द्ध का मतलब रिक्त स्थान के बीच एक प्रोजेक्टिव या एफ़िन मानचित्र का अस्तित्व है जिसमें दो पॉलीटोप्स होते हैं (जरूरी नहीं कि समान आयाम हों) जो पॉलीटोप्स के बीच एक आक्षेप को प्रेरित करता है।{{sfnp|Kaibel|Schwartz|2003}}
* यह तय करने की समस्या कि [[वी-विवरण]] या [[एच-विवरण]] द्वारा दिए गए दो उत्तल पॉलीटोप्स प्रोजेक्टिवली या एफ़िनली आइसोमोर्फिक हैं। उत्तरार्द्ध का मतलब रिक्त स्थान के बीच एक प्रोजेक्टिव या एफ़िन मानचित्र का अस्तित्व है जिसमें दो पॉलीटोप्स होते हैं (जरूरी नहीं कि समान आयाम हों) जो पॉलीटोप्स के बीच एक आक्षेप को प्रेरित करता है।{{sfnp|Kaibel|Schwartz|2003}}


== प्रोग्राम चेकिंग ==
== प्रोग्राम की जाँच ==


{{harvs|first1=Manuel|last1=Blum|author1-link=Manuel Blum|first2=Sampath|last2=Kannan|year=1995|txt}} ने ग्राफ समरूपता के कार्यक्रमों के लिए एक संभाव्य जांचकर्ता दिखाया है। मान लीजिए कि पी एक दावा किया गया बहुपद-समय प्रक्रिया है जो जांचता है कि दो ग्राफ आइसोमोर्फिक हैं, लेकिन यह भरोसेमंद नहीं है। यह जाँचने के लिए कि क्या रेखांकन G और H तुल्याकारी हैं:
{{harvs|first1=मैनुअल|last1=ब्लूम|author1-link=मैनुअल|first2=संपथ|last2=कन्नन|year=1995|और}} ने ग्राफ समरूपता के कार्यक्रमों के लिए एक संभाव्य जांचकर्ता प्रदर्शित किया है। मान लीजिए कि पी द्वारा एक दावा किया गया बहुपद-समय प्रक्रिया है, जो जांचता है कि दो ग्राफ संरूपित हैं, परन्तु यह भरोसेमंद नहीं है। यह जाँचने के लिए कि क्या ग्राफ जी और एच तुल्याकारी हैं:


* P से पूछिए कि क्या G और H तुल्याकारी हैं।
* पी से पूछिए कि क्या जी और एच तुल्याकारी हैं।
** यदि उत्तर हाँ है:
** यदि उत्तर हाँ है:
*** पी को उपनेमका के रूप में उपयोग करके एक समरूपता बनाने का प्रयास। G में एक शीर्ष u और H में v चिह्नित करें, और उन्हें विशिष्ट बनाने के लिए ग्राफ़ को संशोधित करें (एक छोटे से स्थानीय परिवर्तन के साथ)। पी से पूछें कि क्या संशोधित ग्राफ आइसोमोर्फिक हैं। यदि नहीं, तो v को भिन्न शीर्ष में बदलें। खोजना जारी रखें।
*** पी को उपनेमका के रूप में उपयोग करके एक समरूपता बनाने का प्रयास। जी में एक शीर्ष यू और एच में वी चिह्नित करें, और उन्हें विशिष्ट बनाने के लिए ग्राफ़ को संशोधित करें (एक छोटे से स्थानीय परिवर्तन के साथ)। पी से पूछें कि क्या संशोधित ग्राफ समरूप हैं। यदि नहीं, तो v को भिन्न शीर्ष में बदलें। खोजना जारी रखें।
*** या तो समरूपता मिल जाएगी (और सत्यापित की जा सकती है), या पी खुद का खंडन करेगा।
*** या तो समरूपता मिल जाएगी (और सत्यापित की जा सकती है), या पी खुद का खंडन करेगा।
** यदि उत्तर नहीं है:
** यदि उत्तर नहीं है:
*** निम्नलिखित 100 बार करें। यादृच्छिक रूप से जी या एच चुनें, और इसके शीर्षों को यादृच्छिक रूप से क्रमबद्ध करें। पी से पूछें कि क्या ग्राफ जी और एच के लिए आइसोमोर्फिक है।
*** निम्नलिखित 100 बार करें। यादृच्छिक रूप से जी या एच चुनें, और इसके शीर्षों को यादृच्छिक रूप से क्रमबद्ध करें। पी से पूछें कि क्या ग्राफ जी और एच के लिए समरूप है।
*** यदि कोई भी परीक्षण विफल हो जाता है, तो P को अमान्य प्रोग्राम के रूप में जज करें। अन्यथा उत्तर ना में दें।
*** यदि कोई भी परीक्षण विफल हो जाता है, तो पी को अमान्य प्रोग्राम के रूप में जज करें। अन्यथा उत्तर ना में दें।


यह प्रक्रिया बहुपद-समय है और सही उत्तर देती है यदि पी ग्राफ समरूपता के लिए एक सही कार्यक्रम है। यदि P एक सही प्रोग्राम नहीं है, लेकिन G और H पर सही उत्तर देता है, तो चेकर या तो सही उत्तर देगा, या P के अमान्य व्यवहार का पता लगाएगा।
यह प्रक्रिया बहुपद-समय है और सही उत्तर देती है यदि पी ग्राफ समरूपता के लिए एक सही कार्यक्रम है। यदि P एक सही प्रोग्राम नहीं है, परन्तु जी और एच पर सही उत्तर देता है, तो जाँचकर्ता या तो सही उत्तर देगा, या पी के अमान्य व्यवहार का पता लगाएगा।
यदि P एक सही प्रोग्राम नहीं है, और G और H पर गलत उत्तर देता है, तो चेकर उच्च संभावना के साथ P के अमान्य व्यवहार का पता लगाएगा, या प्रायिकता 2 के साथ गलत उत्तर देगा।<sup>-100</sup>.


विशेष रूप से, P का उपयोग केवल एक ब्लैकबॉक्स के रूप में किया जाता है।
यदि पी एक सही प्रोग्राम नहीं है, और जी और एच पर गलत उत्तर देता है, तो जाँचकर्ता उच्च संभावना के साथ पी के अमान्य व्यवहार का पता लगाएगा, या प्रायिकता 2 के साथ गलत उत्तर देगा।<sup>-100</sup>.
 
विशेष रूप से, पी का उपयोग केवल एक ब्लैक बॉक्स के रूप में किया जाता है।


== अनुप्रयोग ==
== अनुप्रयोग ==


ग्राफ़ का उपयोग आमतौर पर कई क्षेत्रों में संरचनात्मक जानकारी को एन्कोड करने के लिए किया जाता है, जिसमें [[कंप्यूटर दृष्टि]] और पैटर्न की पहचान शामिल है, और ग्राफ़ मिलान, यानी ग्राफ़ के बीच समानता की पहचान, इन क्षेत्रों में एक महत्वपूर्ण उपकरण है। इन क्षेत्रों में ग्राफ समरूपता समस्या को सटीक [[ग्राफ मिलान]] के रूप में जाना जाता है।<ref name=endikaAbstract>Endika Bengoetxea, Ph.D., [http://www.sc.ehu.es/acwbecae/ikerkuntza/these/ Abstract]</ref>
ग्राफ़ का उपयोग सामान्यतः कई क्षेत्रों में संरचनात्मक जानकारी को संकेतीकरण करने के लिए किया जाता है, जिसमें [[कंप्यूटर दृष्टि|संगणक दृष्टि]] और स्वरूप की पहचान सम्मिलित है, और ग्राफ़ मिलान, अर्थात ग्राफ़ के बीच समानता की पहचान, इन क्षेत्रों में एक महत्वपूर्ण उपकरण है। इन क्षेत्रों में ग्राफ समरूपता समस्या को सटीक [[ग्राफ मिलान]] के रूप में जाना जाता है।<ref name=endikaAbstract>Endika Bengoetxea, Ph.D., [http://www.sc.ehu.es/acwbecae/ikerkuntza/these/ Abstract]</ref>
रासायनिक सूचना विज्ञान और गणितीय [[रसायन विज्ञान]] में, [[रासायनिक डेटाबेस]] के भीतर एक [[रासायनिक यौगिक]] की पहचान करने के लिए ग्राफ समरूपता परीक्षण का उपयोग किया जाता है।{{sfnp|Irniger|2005}} इसके अलावा, कार्बनिक गणितीय रसायन शास्त्र ग्राफ आइसोमोर्फिज्म परीक्षण में [[आणविक ग्राफ]] और [[संयुक्त रसायन]] के निर्माण के लिए उपयोगी है।
रासायनिक सूचना विज्ञान और गणितीय [[रसायन विज्ञान]] में, [[रासायनिक डेटाबेस]] के भीतर एक [[रासायनिक यौगिक]] की पहचान करने के लिए ग्राफ समरूपता परीक्षण का उपयोग किया जाता है।{{sfnp|Irniger|2005}} इसके अतिरिक्त, कार्बनिक गणितीय रसायन शास्त्र ग्राफ समरूपता परीक्षण में [[आणविक ग्राफ]] और [[संयुक्त रसायन]] के निर्माण के लिए उपयोगी है।


रासायनिक डेटाबेस खोज ग्राफ़िकल [[डेटा खनन]] का एक उदाहरण है, जहाँ [[ग्राफ कैनोनाइजेशन]] दृष्टिकोण का अक्सर उपयोग किया जाता है।{{sfnp|Cook|Holder|2007}} विशेष रूप से, [[रासायनिक पदार्थ]]ों के लिए कई [[पहचानकर्ता]], जैसे [[SMILES]] और [[InChI]], आणविक जानकारी को एन्कोड करने के लिए एक मानक और मानव-पठनीय तरीका प्रदान करने के लिए डिज़ाइन किए गए हैं और डेटाबेस और वेब पर ऐसी जानकारी की खोज को सुविधाजनक बनाने के लिए कैनोनाइजेशन चरण का उपयोग करते हैं। उनकी गणना में, जो अनिवार्य रूप से ग्राफ का कैनोनाइजेशन है जो अणु का प्रतिनिधित्व करता है।
रासायनिक डेटाबेस खोज चित्रात्मक [[डेटा खनन|डेटा माइनिंग]] का एक उदाहरण है, जहाँ [[ग्राफ कैनोनाइजेशन]] दृष्टिकोण का प्रायः  उपयोग किया जाता है।{{sfnp|Cook|Holder|2007}} विशेष रूप से, [[रासायनिक पदार्थ|रासायनिक]] पदार्थो के लिए कई [[पहचानकर्ता]], जैसे स्माइल्स और [[InChI]], आणविक जानकारी को संकेतीकरण करने के लिए एक मानक और मानव-पठनीय तरीका प्रदान करने के लिए प्रारूपित किए गए हैं, और डेटाबेस और वेब पर ऐसी जानकारी की खोज को सुविधाजनक बनाने के लिए कैनोनाइजेशन चरण का उपयोग करते हैं। उनकी गणना में, जो अनिवार्य रूप से ग्राफ का कैनोनाइजेशन है जो अणु का प्रतिनिधित्व करता है।


[[इलेक्ट्रॉनिक डिजाइन स्वचालन]] ग्राफ में समरूपता [[लेआउट बनाम योजनाबद्ध]] (LVS) सर्किट डिज़ाइन चरण का आधार है, जो एक सत्यापन है कि क्या [[सर्किट आरेख]] और एक [[एकीकृत सर्किट लेआउट]] द्वारा दर्शाए गए विद्युत सर्किट समान हैं।{{sfnp|Baird|Cho|1975}}
[[इलेक्ट्रॉनिक डिजाइन स्वचालन|इलेक्ट्रॉनिक प्रारूप स्वचालन]] ग्राफ में समरूपता [[लेआउट बनाम योजनाबद्ध]] (एलवीएस) परिपथ प्रारूप चरण का आधार है, जो एक सत्यापन है, कि क्या [[सर्किट आरेख|परिपथ आरेख]] और एक [[एकीकृत सर्किट लेआउट|एकीकृत परिपथ लेआउट]] द्वारा दर्शाए गए विद्युत परिपथ समान हैं।{{sfnp|Baird|Cho|1975}}


== यह भी देखें ==
== यह भी देखें ==

Revision as of 13:56, 25 May 2023

ग्राफ समरूपता समस्या यह निर्धारित करने की कम्प्यूटेशनल समस्या है, कि क्या दो परिमित ग्राफ समरूपता समरूपी हैं।

समस्या को बहुपद समय में हल करने योग्य और न ही एनपी-पूर्ण होने के लिए जाना जाता है, और इसलिए संगणनात्मक जटिलता वर्ग एनपी-मध्यवर्ती में हो सकता है। यह ज्ञात है, कि ग्राफ समरूपता समस्या वर्ग एनपी के निम्न पदानुक्रम में है, जिसका अर्थ है कि यह एनपी-पूर्ण नहीं है, जब तक कि बहुपद समय पदानुक्रम अपने दूसरे स्तर तक गिर न जाए।[1] इसी समय, ग्राफ के कई विशेष वर्गों के लिए समरूपता को बहुपद समय में हल किया जा सकता है, और व्यवहार में ग्राफ समरूपता को प्रायः कुशलता से हल किया जा सकता है।[2][3]

यह समस्या ग्राफ समरूपता समस्या का एक विशेष सन्दर्भ है,[4] जो पूछता है कि, क्या दिए गए ग्राफ जी में एक सबग्राफ है, जो दूसरे को दिए गए ग्राफ एच के लिए समरूप है; इस समस्या को एनपी-पूर्ण के रूप में जाना जाता है। यह सममित समूह पर एबेलियन समूह, गैर-अबेलियन समस्या का एक विशेष सन्दर्भ भी माना जाता है।[5]

छवि पहचान के क्षेत्र में इसे सटीक ग्राफ़ मिलान के रूप में जाना जाता है।[6]


अत्याधुनिक

नवंबर 2015 में, लेज़्लो बाबई ने सभी ग्राफ़ों के लिए एक समय जटिलता अर्ध-बहुपद समय एल्गोरिथ्म की घोषणा की, जो कि चलने वाले समय के साथ है कुछ निश्चित के लिए .[7][8][9][10] 4 जनवरी, 2017 को, बाबई ने अर्ध-बहुपद दावे को वापस ले लिया और हेराल्ड हेलफगोट ने प्रमाण में एक दोष की खोज के पश्चात एक उप-घातीय समय बद्धता को बताया। 9 जनवरी, 2017 को, बाबई ने सुधार की घोषणा की (19 जनवरी को पूर्ण रूप से प्रकाशित) और अर्ध-बहुपद दावे को बहाल किया, साथ ही हेलफगॉट ने फिक्स की पुष्टि की।[11][12] हेलफगोट आगे दावा करता है कि, c = 3 कोई भी ले सकता है, इसलिए चलने का समय है 2O((log n)3) है।[13][14]

इससे पूर्व, सबसे अच्छा वर्तमान में स्वीकृत सैद्धांतिक एल्गोरिथम बाबई & लुक्स (1983) के कारण था, और यह लुक्स (1982) के पहले कार्य पर आधारित है, जो वी. एन. ज़ेमल्याचेंको (ज़ेम्लियाचेंको, कोर्नीनको & टायीशकेविच 1985) के सबफैक्टोरियल एल्गोरिथम के साथ संयुक्त है। एल्गोरिथम का रन टाइम 2 है, (n log n) n शीर्षों वाले ग्राफ़ के लिए और परिमित सरल समूहों के वर्गीकरण पर निर्भर करता है। इस वर्गीकरण में प्रमेय के अतिरिक्त, थोड़ा कमजोर बंधन होता है।

2O(n log2 n) द्वारा सबसे पहले लेज़्लो बाबई (1980) द्वारा दृढ़ता से नियमित ग्राफ के लिए प्राप्त किया गया था, और उसके पश्चात बाबई & लुक्स (1983) द्वारा सामान्य ग्राफ तक बढ़ाया गया,घातांक में सुधार √n एक प्रमुख खुली समस्या है; दृढ़ता से नियमित ग्राफ के लिए यह स्पीलमैन (1996) द्वारा किया गया था। बाउंडेड रैंक के हाइपरग्राफ के लिए, बाबई और कोडनोटी (2008) द्वारा ग्राफ़ के विषय से मेल खाने वाली एक उप-घातीय ऊपरी सीमा प्राप्त की गई थी।

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

ग्राफ समरूपता समस्या संगणनात्मक रूप से एक ग्राफ के स्वसमाकृतिकता समूह की गणना करने की समस्या के समान है, [16] [17] और क्रमपरिवर्तन समूह समरूपता समस्या और क्रमचय समूह प्रतिच्छेद की समस्या से कमजोर है। पश्चात की दो समस्याओं के लिए, बाबई, कांटोर और लुक्स (1983) ने ग्राफ समरूपता के समान जटिलता सीमाएँ प्राप्त कीं।

हल किए गए विशेष विषय

ग्राफ समरूपता समस्या के कई महत्वपूर्ण विशेष विषयों में कुशल, बहुपद-समय का समाधान हैं:

  • वृक्ष (ग्राफ सिद्धांत) एस[15][16]
  • प्लेनर ग्राफ [17] (वास्तव में, प्लानर ग्राफ समरूपता एल (जटिलता) में है,[18] पी (जटिलता) में निहित एक वर्ग)
  • अंतराल ग्राफ[19]
  • क्रमपरिवर्तन ग्राफ[20]
  • परिपत्र ग्राफ[21]
  • परिबद्ध-पैरामीटर ग्राफ
    • परिबद्ध पेड़ की चौड़ाई का ग्राफ[22]
    • बंधे हुए जीनस के ग्राफ (गणित)[23] (प्लानर ग्राफ जीनस 0 के ग्राफ हैं।)
    • बाउंडेड डिग्री के ग्राफ (ग्राफ सिद्धांत)[24]
    • बंधे हुए आइनवैल्यू बहुलता वाले ग्राफ[25]
    • के-संकुचन योग्य ग्राफ (परिबद्ध डिग्री और परिबद्ध जीनस का एक सामान्यीकरण)[26]
    • रंग-संरक्षण समरूपता रंगीन ग्राफ का बंधी हुई रंग बहुलता के साथ (अर्थात, अधिकांश के कोने में एक निश्चित के के लिए समान रंग होता है) वर्ग एनसी (जटिलता) में है, जो पी (जटिलता) का एक उपवर्ग है।[27]

जटिलता वर्ग जीआई

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

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

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

जीआई-पूर्ण और जीआई-हार्ड समस्याएं

अन्य वस्तुओं की समरूपता

गणितीय वस्तुओं के कई वर्ग हैं जिनके लिए समरूपता की समस्या एक जीआई-पूर्ण समस्या है। उनमें से कई अतिरिक्त गुणों या प्रतिबंधों से संपन्न ग्राफ़ हैं:[31]

जीआई - ग्राफ की पूरी कक्षाएं

ग्राफ़ के एक वर्ग को जीआई-पूर्ण कहा जाता है यदि इस उपवर्ग से ग्राफ़ के लिए समरूपता की पहचान एक जीआई-पूर्ण समस्या है। निम्नलिखित वर्ग जीआई-पूर्ण हैं:[31]* जुड़े ग्राफ[31]

  • व्यास के ग्राफ (ग्राफ सिद्धांत) 2 और त्रिज्या (ग्राफ सिद्धांत) 1[31]* निर्देशित विश्वकोश ग्राफ[31]
  • नियमित ग्राफ[31]
  • गैर-तुच्छ दृढ़ता से नियमित ग्राफ के बिना द्विदलीय ग्राफ[31]
  • द्विदलीय ऑयलरीय ग्राफ[31]
  • द्विदलीय नियमित ग्राफ[31]
  • रेखा ग्राफ[31]
  • ग्राफ विभाजित करें[35]
  • तारकीय ग्राफ[31]
  • नियमित स्व-पूरक ग्राफ[31]
  • मनमाना आयामों में सामान्य, सरल पॉलीटोप, और [[साधारण पॉलीटॉप]] उत्तल पॉलीटोप्स के पॉलीटॉपल ग्राफ[36]

डिग्राफ के कई वर्ग भी जीआई-पूर्ण हैं।

अन्य जीआई-पूर्ण समस्याएं

समरूपता समस्याओं के अलावा अन्य गैर-तुच्छ जीआई-पूर्ण समस्याएं भी हैं।

  • किसी ग्राफ या डिग्राफ की आत्म-पूरकता की मान्यता।[37]
  • तथाकथित एम-ग्राफ के एक वर्ग के लिए एक क्लिक समस्या। यह दिखाया गया है कि एन-वर्टेक्स ग्राफ के लिए एक समरूपता खोजना आकार एन के एम-ग्राफ में एन-क्लिक खोजने के बराबर है।2</उप>। यह तथ्य दिलचस्प है क्योंकि आकार n के एम-ग्राफ में क्रम (1−−ε)n के एक समूह को खोजने की समस्या2 मनमाने ढंग से छोटे सकारात्मक ε के लिए एनपी-पूर्ण है।[38]
  • 2-परिसरों के होमोमोर्फिज्म की समस्या।[39]

जीआई-कठिन समस्याएं

  • दो ग्राफों के बीच समरूपताओं की संख्या की गणना करने की समस्या बहुपद-समय है जो यह बताने की समस्या के बराबर है कि क्या एक भी मौजूद है।[40]
  • यह तय करने की समस्या कि वी-विवरण या एच-विवरण द्वारा दिए गए दो उत्तल पॉलीटोप्स प्रोजेक्टिवली या एफ़िनली आइसोमोर्फिक हैं। उत्तरार्द्ध का मतलब रिक्त स्थान के बीच एक प्रोजेक्टिव या एफ़िन मानचित्र का अस्तित्व है जिसमें दो पॉलीटोप्स होते हैं (जरूरी नहीं कि समान आयाम हों) जो पॉलीटोप्स के बीच एक आक्षेप को प्रेरित करता है।[36]

प्रोग्राम की जाँच

(मैनुअल ब्लूम & संपथ कन्नन 1995) ने ग्राफ समरूपता के कार्यक्रमों के लिए एक संभाव्य जांचकर्ता प्रदर्शित किया है। मान लीजिए कि पी द्वारा एक दावा किया गया बहुपद-समय प्रक्रिया है, जो जांचता है कि दो ग्राफ संरूपित हैं, परन्तु यह भरोसेमंद नहीं है। यह जाँचने के लिए कि क्या ग्राफ जी और एच तुल्याकारी हैं:

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

यह प्रक्रिया बहुपद-समय है और सही उत्तर देती है यदि पी ग्राफ समरूपता के लिए एक सही कार्यक्रम है। यदि P एक सही प्रोग्राम नहीं है, परन्तु जी और एच पर सही उत्तर देता है, तो जाँचकर्ता या तो सही उत्तर देगा, या पी के अमान्य व्यवहार का पता लगाएगा।

यदि पी एक सही प्रोग्राम नहीं है, और जी और एच पर गलत उत्तर देता है, तो जाँचकर्ता उच्च संभावना के साथ पी के अमान्य व्यवहार का पता लगाएगा, या प्रायिकता 2 के साथ गलत उत्तर देगा।-100.

विशेष रूप से, पी का उपयोग केवल एक ब्लैक बॉक्स के रूप में किया जाता है।

अनुप्रयोग

ग्राफ़ का उपयोग सामान्यतः कई क्षेत्रों में संरचनात्मक जानकारी को संकेतीकरण करने के लिए किया जाता है, जिसमें संगणक दृष्टि और स्वरूप की पहचान सम्मिलित है, और ग्राफ़ मिलान, अर्थात ग्राफ़ के बीच समानता की पहचान, इन क्षेत्रों में एक महत्वपूर्ण उपकरण है। इन क्षेत्रों में ग्राफ समरूपता समस्या को सटीक ग्राफ मिलान के रूप में जाना जाता है।[41] रासायनिक सूचना विज्ञान और गणितीय रसायन विज्ञान में, रासायनिक डेटाबेस के भीतर एक रासायनिक यौगिक की पहचान करने के लिए ग्राफ समरूपता परीक्षण का उपयोग किया जाता है।[42] इसके अतिरिक्त, कार्बनिक गणितीय रसायन शास्त्र ग्राफ समरूपता परीक्षण में आणविक ग्राफ और संयुक्त रसायन के निर्माण के लिए उपयोगी है।

रासायनिक डेटाबेस खोज चित्रात्मक डेटा माइनिंग का एक उदाहरण है, जहाँ ग्राफ कैनोनाइजेशन दृष्टिकोण का प्रायः उपयोग किया जाता है।[43] विशेष रूप से, रासायनिक पदार्थो के लिए कई पहचानकर्ता, जैसे स्माइल्स और InChI, आणविक जानकारी को संकेतीकरण करने के लिए एक मानक और मानव-पठनीय तरीका प्रदान करने के लिए प्रारूपित किए गए हैं, और डेटाबेस और वेब पर ऐसी जानकारी की खोज को सुविधाजनक बनाने के लिए कैनोनाइजेशन चरण का उपयोग करते हैं। उनकी गणना में, जो अनिवार्य रूप से ग्राफ का कैनोनाइजेशन है जो अणु का प्रतिनिधित्व करता है।

इलेक्ट्रॉनिक प्रारूप स्वचालन ग्राफ में समरूपता लेआउट बनाम योजनाबद्ध (एलवीएस) परिपथ प्रारूप चरण का आधार है, जो एक सत्यापन है, कि क्या परिपथ आरेख और एक एकीकृत परिपथ लेआउट द्वारा दर्शाए गए विद्युत परिपथ समान हैं।[44]

यह भी देखें

टिप्पणियाँ

  1. Schöning (1987).
  2. Babai, László; Erdős, Paul; Selkow, Stanley M. (1980-08-01). "रैंडम ग्राफ समरूपता". SIAM Journal on Computing. 9 (3): 628–635. doi:10.1137/0209047. ISSN 0097-5397.
  3. McKay (1981).
  4. Ullman (1976).
  5. Moore, Russell & Schulman (2008).
  6. Endika Bengoetxea, "Inexact Graph Matching Using Estimation of Distribution Algorithms", Ph. D., 2002, Chapter 2:The graph matching problem (retrieved June 28, 2017)
  7. "गणितज्ञ जटिलता सिद्धांत में सफलता का दावा करते हैं". Science. November 10, 2015.
  8. Babai (2015)
  9. Video of first 2015 lecture linked from Babai's home page
  10. "ग्राफ समरूपता समस्या". Communications of the ACM. Retrieved 4 May 2021.
  11. Babai, László (January 9, 2017), Graph isomorphism update
  12. Erica Klarreich (January 14, 2017). "Graph Isomorphism Vanquished — Again". Quanta Magazine.
  13. Helfgott, Harald (January 16, 2017), Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...), arXiv:1701.04372, Bibcode:2017arXiv170104372A
  14. Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (October 12, 2017). "अर्धबहुपद समय में ग्राफ समरूपता" (in English). arXiv:1710.04574 [math.GR].
  15. Kelly (1957).
  16. Aho, Hopcroft & Ullman (1974), p. 84-86.
  17. Hopcroft & Wong (1974).
  18. Datta et al. (2009).
  19. Booth & Lueker (1979).
  20. Colbourn (1981).
  21. Muzychuk (2004).
  22. Bodlaender (1990).
  23. Miller 1980; Filotti & Mayer 1980.
  24. Luks (1982).
  25. Babai, Grigoryev & Mount (1982).
  26. Miller (1983).
  27. Luks (1986).
  28. Booth & Colbourn 1977; Köbler, Schöning & Torán 1993.
  29. Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
  30. Arvind & Köbler (2000).
  31. 31.00 31.01 31.02 31.03 31.04 31.05 31.06 31.07 31.08 31.09 31.10 31.11 31.12 31.13 31.14 31.15 31.16 31.17 31.18 31.19 31.20 31.21 31.22 31.23 Zemlyachenko, Korneenko & Tyshkevich (1985)
  32. Narayanamurthy & Ravindran (2008).
  33. Grigor'ev (1981).
  34. Johnson (2005); Kaibel & Schwartz (2003).
  35. Chung (1985).
  36. 36.0 36.1 Kaibel & Schwartz (2003).
  37. Colbourn & Colbourn (1978).
  38. Kozen (1978).
  39. Shawe-Taylor & Pisanski (1994).
  40. Mathon (1979); Johnson 2005.
  41. Endika Bengoetxea, Ph.D., Abstract
  42. Irniger (2005).
  43. Cook & Holder (2007).
  44. Baird & Cho (1975).


संदर्भ



सर्वेक्षण और मोनोग्राफ

  • Read, Ronald C.; Corneil, Derek G. (1977), "The graph isomorphism disease", Journal of Graph Theory, 1 (4): 339–363, doi:10.1002/jgt.3190010410, MR 0485586.
  • Gati, G. (1979), "Further annotated bibliography on the isomorphism disease", Journal of Graph Theory, 3 (2): 95–109, doi:10.1002/jgt.3190030202.
  • Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), "Graph isomorphism problem", Journal of Mathematical Sciences, 29 (4): 1426–1481, doi:10.1007/BF02104746, S2CID 121818465. (Zapiski Nauchnykh Seminarov Leningradskogo विभाग के Matematicheskogo Instituta im. V. A. Steklova AN SSSR से अनुवादित (यूएसएसआर एकेडमी ऑफ साइंसेज के स्टेक्लोव इंस्टीट्यूट ऑफ मैथमेटिक्स के लेनिनग्राद विभाग के सेमिनारों का रिकॉर्ड), वॉल्यूम 118, पीपी। 83-158, 1982। )
  • Arvind, V.; Torán, Jacobo (2005), "Isomorphism testing: Perspectives and open problems" (PDF), Bulletin of the European Association for Theoretical Computer Science, 86: 66–84. (ग्राफ, रिंग और समूहों के लिए समरूपता समस्या से संबंधित मुक्त प्रश्नों का एक संक्षिप्त सर्वेक्षण।)
  • Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0-8176-3680-7. (बुक कवर से: पुस्तकें समस्या की कम्प्यूटेशनल जटिलता के मुद्दे पर ध्यान केंद्रित करती हैं और कई हालिया परिणाम प्रस्तुत करती हैं जो कक्षा एनपी के साथ-साथ अन्य जटिलता वर्गों में समस्या की सापेक्ष स्थिति की बेहतर समझ प्रदान करती हैं।)
  • Johnson, David S. (2005), "The NP-Completeness Column", ACM Transactions on Algorithms, 1 (1): 160–176, doi:10.1145/1077464.1077476, S2CID 12604799. (कॉलम का यह 24वां संस्करण विशेष रूप से ग्राफ आइसोमोर्फिज्म के लिए कंप्यूटर और इंट्रेक्टेबिलिटी और पिछले कॉलम से खुली समस्याओं के लिए कला की स्थिति पर चर्चा करता है।)
  • Torán, Jacobo; Wagner, Fabian (2009), "The complexity of planar graph isomorphism" (PDF), Bulletin of the European Association for Theoretical Computer Science, 97, archived from the original (PDF) on 2010-09-20, retrieved 2010-06-03.
  • Stoichev, Stoicho D. (2019), "New Exact and Heuristic Algorithms for Graph Automorphism Group and Graph Isomorphism", Journal of Experimental Algorithmics, 24: 1–27, doi:10.1145/3333250, S2CID 202676274.

सॉफ्टवेयर

श्रेणी:ग्राफ़ एल्गोरिदम श्रेणी:रूपवाद श्रेणी:ग्राफ़ थ्योरी में कम्प्यूटेशनल समस्याएं श्रेणी:कंप्यूटर विज्ञान में अनसुलझी समस्याएं श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत