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

Latest revision as of 14:25, 11 August 2023

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

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

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

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

अत्याधुनिक

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

निर्देशित ग्राफ^[30]* लेबल वाले ग्राफ़, इस प्रावधान के साथ कि लेबल को संरक्षित करने के लिए एक समरूपता की आवश्यकता नहीं है,^[30]परन्तु केवल समान लेबल वाले शीर्षों के युग्मों वाला तुल्यता संबंध
ध्रुवीकृत ग्राफ (एक पूर्ण ग्राफ K से बना है_m और एक खाली ग्राफ K_n साथ ही दोनों को जोड़ने वाले कुछ किनारे; उनके समरूपता को विभाजन को बनाए रखना चाहिए)^[30]* 2-रंगीन ग्राफ^[30]* स्पष्ट रूप से दी गई परिमित संरचना (गणितीय तर्क)।^[30]* मल्टीग्राफ^[30]* हाइपरग्राफ^[30]*स्वचालित रूप से समाप्त^[30]* मार्कोव निर्णय प्रक्रिया^[31]
क्रमविनिमेय वर्ग 3 निलपोटेंट (अर्थात, xyz = 0 हर तत्व x, y, z) उपसमूह के लिए^[30]* रेडिकल पर जीरो स्क्वेयर रेडिकल और संगड़कीय फैक्टर के साथ फिक्स्ड बीजगणितीय रूप से बंद क्षेत्र पर एक परिमित रैंक सहयोगी बीजगणित।^[30]^[32]
संदर्भ-मुक्त व्याकरण^[30]*संतुलित अपूर्ण ब्लॉक अभिकल्पनाएँ^[30]* वर्टेक्स-पहलू घटनाओं द्वारा दर्शाए गए उत्तल पॉलीटॉप के मिश्रित समरूपता को पहचानना।^[33]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

यह भी देखें

ग्राफ ऑटोमोर्फिज्म समस्या
ग्राफ कैनोनाइजेशन

↑ 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.
↑ McKay (1981).
↑ Ullman (1976).
↑ Moore, Russell & Schulman (2008).
↑ Endika Bengoetxea, "Inexact Graph Matching Using Estimation of Distribution Algorithms", Ph. D., 2002, Chapter 2:The graph matching problem (retrieved June 28, 2017)
↑ "गणितज्ञ जटिलता सिद्धांत में सफलता का दावा करते हैं". Science. November 10, 2015.
↑ Babai (2015)
↑ Video of first 2015 lecture linked from Babai's home page
↑ "ग्राफ समरूपता समस्या". Communications of the ACM. Retrieved 4 May 2021.
↑ Babai, László (January 9, 2017), Graph isomorphism update
↑ Erica Klarreich (January 14, 2017). "Graph Isomorphism Vanquished — Again". Quanta Magazine.
↑ 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
↑ Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (October 12, 2017). "अर्धबहुपद समय में ग्राफ समरूपता" (in English). arXiv:1710.04574 [math.GR].
↑ Kelly (1957).
↑ Aho, Hopcroft & Ullman (1974), p. 84-86.
↑ Hopcroft & Wong (1974).
↑ Datta et al. (2009).
↑ Booth & Lueker (1979).
↑ Colbourn (1981).
↑ Muzychuk (2004).
↑ Bodlaender (1990).
↑ Miller 1980; Filotti & Mayer 1980.
↑ Luks (1982).
↑ Babai, Grigoryev & Mount (1982).
↑ Miller (1983).
↑ Luks (1986).
↑ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993.
↑ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
↑ Arvind & Köbler (2000).
↑ ^30.00 ^30.01 ^30.02 ^30.03 ^30.04 ^30.05 ^30.06 ^30.07 ^30.08 ^30.09 ^30.10 ^30.11 ^30.12 ^30.13 ^30.14 ^30.15 ^30.16 ^30.17 ^30.18 ^30.19 ^30.20 ^30.21 ^30.22 ^30.23 Zemlyachenko, Korneenko & Tyshkevich (1985)
↑ Narayanamurthy & Ravindran (2008).
↑ Grigor'ev (1981).
↑ Johnson (2005); Kaibel & Schwartz (2003).
↑ Chung (1985).
↑ ^35.0 ^35.1 Kaibel & Schwartz (2003).
↑ Colbourn & Colbourn (1978).
↑ Kozen (1978).
↑ Shawe-Taylor & Pisanski (1994).
↑ Mathon (1979); Johnson 2005.
↑ Endika Bengoetxea, Ph.D., Abstract
↑ Irniger (2005).
↑ Cook & Holder (2007).
↑ Baird & Cho (1975).

संदर्भ

Aho, Alfred V.; Hopcroft, John; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading, MA: Addison-Wesley.
Arvind, Vikraman; Köbler, Johannes (2000), "Graph isomorphism is low for ZPP(NP) and other lowness results.", Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 1770, Springer-Verlag, pp. 431–442, doi:10.1007/3-540-46541-3_36, ISBN 3-540-67141-2, MR 1781752.
Arvind, Vikraman; Kurur, Piyush P. (2006), "Graph isomorphism is in SPP", Information and Computation, 204 (5): 835–852, doi:10.1016/j.ic.2006.02.002, MR 2226371.
Babai, László (1980), "On the complexity of canonical labeling of strongly regular graphs", SIAM Journal on Computing, 9 (1): 212–216, doi:10.1137/0209018, MR 0557839.
Babai, László; Codenotti, Paolo (2008), "Isomorphism of hypergraphs of low rank in moderately exponential time" (PDF), Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), IEEE Computer Society, pp. 667–676, doi:10.1109/FOCS.2008.80, ISBN 978-0-7695-3436-7, S2CID 14025744.
Babai, László; Grigoryev, D. Yu.; Mount, David M. (1982), "Isomorphism of graphs with bounded eigenvalue multiplicity", Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pp. 310–324, doi:10.1145/800070.802206, ISBN 0-89791-070-2, S2CID 12837287.
Babai, László; Kantor, William; Luks, Eugene (1983), "Computational complexity and the classification of finite simple groups", Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 162–171, doi:10.1109/SFCS.1983.10, S2CID 6670135.
Babai, László; Luks, Eugene M. (1983), "Canonical labeling of graphs", Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 171–183, doi:10.1145/800061.808746, ISBN 0-89791-099-0, S2CID 12572142.
Babai, László (2015), Graph Isomorphism in Quasipolynomial Time, arXiv:1512.03547, Bibcode:2015arXiv151203547B
Baird, H. S.; Cho, Y. E. (1975), "An artwork design verification system", Proceedings of the 12th Design Automation Conference (DAC '75), Piscataway, NJ, USA: IEEE Press, pp. 414–420.
Blum, Manuel; Kannan, Sampath (1995), "Designing programs that check their work", Journal of the ACM, 42 (1): 269–291, CiteSeerX 10.1.1.38.2537, doi:10.1145/200836.200880, S2CID 52151779.
Bodlaender, Hans (1990), "Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees", Journal of Algorithms, 11 (4): 631–643, doi:10.1016/0196-6774(90)90013-5, MR 1079454.
Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report, vol. CS-77-04, Computer Science Department, University of Waterloo.
Booth, Kellogg S.; Lueker, George S. (1979), "A linear time algorithm for deciding interval graph isomorphism", Journal of the ACM, 26 (2): 183–195, doi:10.1145/322123.322125, MR 0528025, S2CID 18859101.
Boucher, C.; Loker, D. (2006), Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs (PDF), Technical Report, vol. CS-2006-32, Computer Science Department, University of Waterloo.
Chung, Fan R. K. (1985), "On the cutwidth and the topological bandwidth of a tree", SIAM Journal on Algebraic and Discrete Methods, 6 (2): 268–277, doi:10.1137/0606026, MR 0778007.
Colbourn, C. J. (1981), "On testing isomorphism of permutation graphs", Networks, 11: 13–21, doi:10.1002/net.3230110103, MR 0608916.
Colbourn, Marlene Jones; Colbourn, Charles J. (1978), "Graph isomorphism and self-complementary graphs", ACM SIGACT News, 10 (1): 25–29, doi:10.1145/1008605.1008608, S2CID 35157300.
Cook, Diane J.; Holder, Lawrence B. (2007), "Section 6.2.1: Canonical Labeling", Mining Graph Data, Wiley, pp. 120–122, ISBN 978-0-470-07303-2.
Datta, S.; Limaye, N.; Nimbhorkar, P.; Thierauf, T.; Wagner, F. (2009), "Planar graph isomorphism is in log-space", 2009 24th Annual IEEE Conference on Computational Complexity, p. 203, arXiv:0809.2319, doi:10.1109/CCC.2009.16, ISBN 978-0-7695-3717-7, S2CID 14836820.
Filotti, I. S.; Mayer, Jack N. (1980), "A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus", Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 236–243, doi:10.1145/800141.804671, ISBN 0-89791-017-6, S2CID 16345164.
Foggia, P.; Sansone, C.; Vento, M. (2001), "A performance comparison of five algorithms for graph isomorphism" (PDF), Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, pp. 188–199.
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0-7167-1045-5.
Grigor'ev, D. Ju. (1981), "Complexity of 'wild' matrix problems and of the isomorphism of algebras and graphs", Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni V. A. Steklova Akademii Nauk SSSR (LOMI) (in Russian), 105: 10–17, 198, MR 0628981{{citation}}: CS1 maint: unrecognized language (link). English translation in Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
Hopcroft, John; Wong, J. (1974), "Linear time algorithm for isomorphism of planar graphs", Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 172–184, doi:10.1145/800119.803896, S2CID 15561884.
Irniger, Christophe-André Mario (2005), Graph Matching: Filtering Databases of Graphs Using Machine Learning, Dissertationen zur künstlichen Intelligenz, vol. 293, AKA, ISBN 1-58603-557-6.
Kaibel, Volker; Schwartz, Alexander (2003), "On the complexity of polytope isomorphism problems", Graphs and Combinatorics, 19 (2): 215–230, arXiv:math/0106093, doi:10.1007/s00373-002-0503-y, MR 1996205, S2CID 179936, archived from the original on 2015-07-21.
Kelly, Paul J. (1957), "A congruence theorem for trees", Pacific Journal of Mathematics, 7: 961–968, doi:10.2140/pjm.1957.7.961, MR 0087949.
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity, 2 (4): 301–330, doi:10.1007/BF01200427, MR 1215315, S2CID 8542603.
Kozen, Dexter (1978), "A clique problem equivalent to graph isomorphism", ACM SIGACT News, 10 (2): 50–52, doi:10.1145/990524.990529, S2CID 52835766.
Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, 25: 42–65, doi:10.1016/0022-0000(82)90009-5, MR 0685360, S2CID 2572728.
Luks, Eugene M. (1986), "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science, pp. 292–302.
Mathon, Rudolf (1979), "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (3): 131–132, doi:10.1016/0020-0190(79)90004-8, MR 0526453.
McKay, Brendan D. (1981), "Practical graph isomorphism", 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), Congressus Numerantium, vol. 30, pp. 45–87, MR 0635936.
Miller, Gary (1980), "Isomorphism testing for graphs of bounded genus", Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 225–235, doi:10.1145/800141.804670, ISBN 0-89791-017-6, S2CID 13647304.
Miller, Gary L. (1983), "Isomorphism testing and canonical forms for k-contractable graphs (a generalization of bounded valence and bounded genus)", Proc. Int. Conf. on Foundations of Computer Theory, Lecture Notes in Computer Science, vol. 158, pp. 310–327, doi:10.1007/3-540-12689-9_114. Full paper in Information and Control 56 (1–2): 1–20, 1983.
Moore, Cristopher; Russell, Alexander; Schulman, Leonard J. (2008), "The symmetric group defies strong Fourier sampling", SIAM Journal on Computing, 37 (6): 1842–1864, arXiv:quant-ph/0501056, doi:10.1137/050644896, MR 2386215, S2CID 9550284.
Muzychuk, Mikhail (2004), "A Solution of the Isomorphism Problem for Circulant Graphs", Proc. London Math. Soc., 88: 1–41, doi:10.1112/s0024611503014412, MR 2018956, S2CID 16704931.
Narayanamurthy, S. M.; Ravindran, B. (2008), "On the hardness of finding symmetries in Markov decision processes" (PDF), Proceedings of the Twenty-Fifth International Conference on Machine Learning (ICML 2008), pp. 688–696.
Schmidt, Douglas C.; Druffel, Larry E. (1976), "A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices", Journal of the ACM, 23 (3): 433–445, doi:10.1145/321958.321963, MR 0411230, S2CID 6163956.
Schöning, Uwe (1987), "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, pp. 114–124; also Journal of Computer and System Sciences 37: 312–323, 1988.
Shawe-Taylor, John; Pisanski, Tomaž (1994), "Homeomorphism of 2-complexes is graph isomorphism complete", SIAM Journal on Computing, 23 (1): 120–132, doi:10.1137/S0097539791198900, MR 1258998.
Spielman, Daniel A. (1996), "Faster isomorphism testing of strongly regular graphs", Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC '96), ACM, pp. 576–584, ISBN 978-0-89791-785-8.
Ullman, Julian R. (1976), "An algorithm for subgraph isomorphism" (PDF), Journal of the ACM, 23: 31–42, CiteSeerX 10.1.1.361.7741, doi:10.1145/321921.321925, MR 0495173, S2CID 17268751.

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

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.

सॉफ्टवेयर

ग्राफ समरूपता, कार्यान्वयन की समीक्षा, द स्टोनी ब्रुक एल्गोरिथम रिपॉजिटरी।

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

[1] 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.

[FOOTNOTEMcKay1981-2] McKay (1981).

[FOOTNOTEUllman1976-3] Ullman (1976).

[FOOTNOTEMooreRussellSchulman2008-4] Moore, Russell & Schulman (2008).

[endikaCh2-5] Endika Bengoetxea, "Inexact Graph Matching Using Estimation of Distribution Algorithms", Ph. D., 2002, Chapter 2:The graph matching problem (retrieved June 28, 2017)

[6] "गणितज्ञ जटिलता सिद्धांत में सफलता का दावा करते हैं". Science. November 10, 2015.

[7] Babai (2015)

[8] Video of first 2015 lecture linked from Babai's home page

[9] "ग्राफ समरूपता समस्या". Communications of the ACM. Retrieved 4 May 2021.

[10] Babai, László (January 9, 2017), Graph isomorphism update

[11] Erica Klarreich (January 14, 2017). "Graph Isomorphism Vanquished — Again". Quanta Magazine.

[12] 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

[13] Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (October 12, 2017). "अर्धबहुपद समय में ग्राफ समरूपता" (in English). arXiv:1710.04574 [math.GR].

[FOOTNOTEKelly1957-14] Kelly (1957).

[FOOTNOTEAhoHopcroftUllman197484-86-15] Aho, Hopcroft & Ullman (1974), p. 84-86.

[FOOTNOTEHopcroftWong1974-16] Hopcroft & Wong (1974).

[FOOTNOTEDattaLimayeNimbhorkarThierauf2009-17] Datta et al. (2009).

[FOOTNOTEBoothLueker1979-18] Booth & Lueker (1979).

[FOOTNOTEColbourn1981-19] Colbourn (1981).

[FOOTNOTEMuzychuk2004-20] Muzychuk (2004).

[FOOTNOTEBodlaender1990-21] Bodlaender (1990).

[22] Miller 1980; Filotti & Mayer 1980.

[FOOTNOTELuks1982-23] Luks (1982).

[FOOTNOTEBabaiGrigoryevMount1982-24] Babai, Grigoryev & Mount (1982).

[FOOTNOTEMiller1983-25] Miller (1983).

[FOOTNOTELuks1986-26] Luks (1986).

[27] Booth & Colbourn 1977; Köbler, Schöning & Torán 1993.

[28] Köbler, Schöning & Torán 1992; Arvind & Kurur 2006

[FOOTNOTEArvindKöbler2000-29] Arvind & Köbler (2000).

[zkt-30] 30.00 ^30.01 ^30.02 ^30.03 ^30.04 ^30.05 ^30.06 ^30.07 ^30.08 ^30.09 ^30.10 ^30.11 ^30.12 ^30.13 ^30.14 ^30.15 ^30.16 ^30.17 ^30.18 ^30.19 ^30.20 ^30.21 ^30.22 ^30.23 Zemlyachenko, Korneenko & Tyshkevich (1985)

[FOOTNOTENarayanamurthyRavindran2008-31] Narayanamurthy & Ravindran (2008).

[FOOTNOTEGrigor'ev1981-32] Grigor'ev (1981).

[33] Johnson (2005); Kaibel & Schwartz (2003).

[FOOTNOTEChung1985-34] Chung (1985).

[FOOTNOTEKaibelSchwartz2003-35] 35.0 ^35.1 Kaibel & Schwartz (2003).

[FOOTNOTEColbournColbourn1978-36] Colbourn & Colbourn (1978).

[FOOTNOTEKozen1978-37] Kozen (1978).

[FOOTNOTEShawe-TaylorPisanski1994-38] Shawe-Taylor & Pisanski (1994).

[39] Mathon (1979); Johnson 2005.

[endikaAbstract-40] Endika Bengoetxea, Ph.D., Abstract

[FOOTNOTEIrniger2005-41] Irniger (2005).

[FOOTNOTECookHolder2007-42] Cook & Holder (2007).

[FOOTNOTEBairdCho1975-43] Baird & Cho (1975).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

@@ Line 1: / Line 1: @@
 {{Short description|Unsolved problem in computational complexity theory}}
-[[ग्राफ समरूपता]] समस्या यह निर्धारित करने की [[कम्प्यूटेशनल समस्या]] है, कि क्या दो परिमित [[ग्राफ समरूपता]] समरूपी हैं।
+[[ग्राफ समरूपता]] समस्या एक [[कम्प्यूटेशनल समस्या|संगणनात्मक समस्या]] है,जो यह निर्धारित करने की समस्या है कि क्या दो नियत [[ग्राफ समरूपता|ग्राफ]] समरूपी हैं या नहीं।
-समस्या को बहुपद समय में हल करने योग्य और न ही एनपी-पूर्ण होने के लिए जाना जाता है, और इसलिए [[कम्प्यूटेशनल समस्या|संगणनात्मक]] [[जटिलता वर्ग]] [[ एनपी-मध्यवर्ती |एनपी-मध्यवर्ती]] में हो सकता है। यह ज्ञात है, कि ग्राफ समरूपता समस्या वर्ग एनपी के [[निम्न पदानुक्रम]] में है, जिसका अर्थ है कि यह एनपी-पूर्ण नहीं है, जब तक कि [[बहुपद समय पदानुक्रम]] अपने दूसरे स्तर तक गिर न जाए।{{sfnp|Schöning|1987}} इसी समय, ग्राफ के कई विशेष वर्गों के लिए समरूपता को बहुपद समय में हल किया जा सकता है, और व्यवहार में ग्राफ समरूपता को प्रायः कुशलता से हल किया जा सकता है।<ref>{{Cite journal|last1=Babai|first1=László|last2=Erdős|first2=Paul|last3=Selkow|first3=Stanley M.|date=1980-08-01|title=रैंडम ग्राफ समरूपता|url=https://epubs.siam.org/doi/10.1137/0209047|journal=SIAM Journal on Computing|volume=9|issue=3|pages=628–635|doi=10.1137/0209047|issn=0097-5397}}</ref>{{sfnp|McKay|1981}}
+समस्या को न ही बहुपद समय में हल करने योग्य, और न ही एनपी-पूर्ण होने के लिए जाना जाता है, एवं इसलिए [[कम्प्यूटेशनल समस्या|संगणनात्मक]] [[जटिलता वर्ग]] [[ एनपी-मध्यवर्ती |एनपी-मध्यवर्ती]] में हो सकता है। यह ज्ञात है, कि ग्राफ समरूपता समस्या वर्ग एनपी के [[निम्न पदानुक्रम]] में है, जिसका अर्थ है कि यह एनपी-पूर्ण नहीं है, जब तक कि [[बहुपद समय पदानुक्रम]] द्वितीय स्तर के लिए संकुचित नहीं हो जाता है, इसके साथ ही, अनेक विशेष ग्राफ के लिए समरूपता को बहुपद समय में हल किया जा सकता है, और व्यावहारिक रूप से ग्राफ समरूपता को प्रायः कुशलता से हल किया जा सकता है।<ref>{{Cite journal|last1=Babai|first1=László|last2=Erdős|first2=Paul|last3=Selkow|first3=Stanley M.|date=1980-08-01|title=रैंडम ग्राफ समरूपता|url=https://epubs.siam.org/doi/10.1137/0209047|journal=SIAM Journal on Computing|volume=9|issue=3|pages=628–635|doi=10.1137/0209047|issn=0097-5397}}</ref>{{sfnp|McKay|1981}}
-यह समस्या [[सबग्राफ समरूपता समस्या]] का एक विशेष मामला है,{{sfnp|Ullman|1976}} जो पूछता है कि क्या दिए गए ग्राफ जी में एक सबग्राफ है, जो दूसरे को दिए गए ग्राफ एच के लिए समरूप है; इस समस्या को एनपी-पूर्ण के रूप में जाना जाता है। यह [[सममित समूह]] पर [[एबेलियन समूह]], गैर-अबेलियन [[छिपी हुई उपसमूह समस्या|समस्या]] का एक विशेष सन्दर्भ भी माना जाता है।{{sfnp|Moore|Russell|Schulman|2008}}
+यह समस्या [[सबग्राफ समरूपता समस्या|ग्राफ समरूपता समस्या]] का एक विशेष सन्दर्भ है,{{sfnp|Ullman|1976}} जो पूछता है कि, क्या दिए गए ग्राफ जी में एक सबग्राफ है, जो दूसरे को दिए गए ग्राफ एच के समरूप है; इस समस्या को एनपी-पूर्ण के रूप में जाना जाता है। यह [[सममित समूह]] पर [[एबेलियन समूह]], गैर-अबेलियन [[छिपी हुई उपसमूह समस्या|समस्या]] का एक विशेष सन्दर्भ भी माना जाता है।{{sfnp|Moore|Russell|Schulman|2008}}
 [[छवि पहचान]] के क्षेत्र में इसे सटीक ग्राफ़ मिलान के रूप में जाना जाता है।<ref name=endikaCh2>Endika Bengoetxea, [http://www.sc.ehu.es/acwbecae/ikerkuntza/these/ "Inexact Graph Matching Using Estimation of Distribution Algorithms"], Ph.
@@ Line 11: / Line 11: @@
 == अत्याधुनिक ==
-नवंबर 2015 में, लेज़्लो बाबई ने सभी ग्राफ़ों के लिए एक समय जटिलता#अर्ध-बहुपद समय एल्गोरिथ्म की घोषणा की, जो कि चलने वाले समय के साथ एक है <math>2^{O((\log n)^c)}</math> कुछ निश्चित के लिए <math>c > 0</math>.<ref>{{cite news|title=गणितज्ञ जटिलता सिद्धांत में सफलता का दावा करते हैं|url=https://www.science.org/content/article/mathematician-claims-breakthrough-complexity-theory|work=Science|date=November 10, 2015}}</ref><ref>{{harvtxt|Babai|2015}}</ref><ref>[http://people.cs.uchicago.edu/~laci/  Video of first 2015 lecture linked from Babai's home page]</ref><ref>{{cite web |title=ग्राफ समरूपता समस्या|url=https://cacm.acm.org/magazines/2020/11/248220-the-graph-isomorphism-problem/fulltext?mobile=false |website=Communications of the ACM |access-date=4 May 2021}}</ref> 4 जनवरी, 2017 को, बाबई ने अर्ध-बहुपद दावे को वापस ले लिया और [[हेराल्ड हेलफगोट]] ने सबूत में एक दोष की खोज के बाद एक [[उप-घातीय समय]]बद्धता को बताया। 9 जनवरी, 2017 को, बाबई ने सुधार की घोषणा की (19 जनवरी को पूर्ण रूप से प्रकाशित) और अर्ध-बहुपद दावे को बहाल किया, साथ ही हेलफगॉट ने फिक्स की पुष्टि की।<ref>{{citation|last=Babai|first= László|url=http://people.cs.uchicago.edu/~laci/update.html|title=Graph isomorphism update|date=January 9, 2017}}</ref><ref>{{cite journal|author=[[Erica Klarreich]] |title=Graph Isomorphism Vanquished — Again |journal=Quanta Magazine |date=January 14, 2017 |url=https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/}}</ref> Helfgott आगे दावा करता है कि कोई भी ले सकता है {{math|1=''c'' = 3}}, तो चलने का समय है {{math|2<sup>O((log ''n'')<sup>3</sup>)</sup>}}.<ref>{{citation|last=Helfgott|first=Harald|arxiv=1701.04372|title=Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)|date=January 16, 2017|bibcode=2017arXiv170104372A}}</ref><ref>{{cite arXiv|last1=Dona|first1=Daniele|last2=Bajpai|first2=Jitendra|last3=Helfgott|first3=Harald Andrés|date=2017-10-12|title=अर्धबहुपद समय में ग्राफ समरूपता|class=math.GR|language=en|eprint=1710.04574|df=mdy-all}}</ref>
+नवंबर 2015 में, लेज़्लो बाबई ने सभी ग्राफ़ों के लिए एक समय जटिलता अर्ध-बहुपद समय एल्गोरिथ्म की घोषणा की, जो कि चलने वाले समय के साथ <math>2^{O((\log n)^c)}</math> है, कुछ निश्चित के लिए <math>c > 0</math>.<ref>{{cite news|title=गणितज्ञ जटिलता सिद्धांत में सफलता का दावा करते हैं|url=https://www.science.org/content/article/mathematician-claims-breakthrough-complexity-theory|work=Science|date=November 10, 2015}}</ref><ref>{{harvtxt|Babai|2015}}</ref><ref>[http://people.cs.uchicago.edu/~laci/  Video of first 2015 lecture linked from Babai's home page]</ref><ref>{{cite web |title=ग्राफ समरूपता समस्या|url=https://cacm.acm.org/magazines/2020/11/248220-the-graph-isomorphism-problem/fulltext?mobile=false |website=Communications of the ACM |access-date=4 May 2021}}</ref> 4 जनवरी, 2017 को, बाबई ने अर्ध-बहुपद दावे को वापस ले लिया, और [[हेराल्ड हेलफगोट]] ने प्रमाण में एक दोष की खोज के पश्चात एक [[उप-घातीय समय]] बद्धता को बताया। इसके पश्चात 9 जनवरी, 2017 को, बाबई ने सुधार की घोषणा की (19 जनवरी को पूर्ण रूप से प्रकाशित) और अर्ध-बहुपद दावे को बहाल किया, साथ ही हेलफगॉट ने फिक्स की पुष्टि भी की।<ref>{{citation|last=Babai|first= László|url=http://people.cs.uchicago.edu/~laci/update.html|title=Graph isomorphism update|date=January 9, 2017}}</ref><ref>{{cite journal|author=[[Erica Klarreich]] |title=Graph Isomorphism Vanquished — Again |journal=Quanta Magazine |date=January 14, 2017 |url=https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/}}</ref> [[हेराल्ड हेलफगोट|हेलफगोट]] आगे दावा करता है कि, {{math|1=''c'' = 3}} कोई भी ले सकता है, इसलिए चलने का समय है {{math|2<sup>O((log ''n'')<sup>3</sup>)</sup>}} है।<ref>{{citation|last=Helfgott|first=Harald|arxiv=1701.04372|title=Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)|date=January 16, 2017|bibcode=2017arXiv170104372A}}</ref><ref>{{cite arXiv|last1=Dona|first1=Daniele|last2=Bajpai|first2=Jitendra|last3=Helfgott|first3=Harald Andrés|date=2017-10-12|title=अर्धबहुपद समय में ग्राफ समरूपता|class=math.GR|language=en|eprint=1710.04574|df=mdy-all}}</ref>
-इससे पहले, सबसे अच्छा वर्तमान में स्वीकृत सैद्धांतिक एल्गोरिथम के कारण था {{harvtxt|Babai|Luks|1983}}, और द्वारा पहले के काम पर आधारित है {{harvtxt|Luks|1982}} V. N. Zemlyachenko के सबफ़ैक्टोरियल एल्गोरिथम के साथ संयुक्त {{harv|Zemlyachenko|Korneenko|Tyshkevich|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=László|last=Babai|year=1980|txt}}, और उसके बाद सामान्य रेखांकन तक बढ़ाया गया {{harvtxt|Babai|Luks|1983}}. प्रतिपादक में सुधार {{sqrt|''n''}} एक बड़ी खुली समस्या है; जोरदार नियमित रेखांकन के लिए यह द्वारा किया गया था {{Harvtxt|Spielman|1996}}. बाउंडेड रैंक के [[ hypergraph ]] के लिए, ग्राफ के मामले से मेल खाने वाली एक सब-एक्सपोनेंशियल टाइम अपर बाउंड द्वारा प्राप्त किया गया था {{Harvtxt|Babai|Codenotti|2008}}.
-ग्राफ समरूपता के लिए कई प्रतिस्पर्धी व्यावहारिक एल्गोरिदम हैं, जैसे कि इसके कारण {{harvtxt|McKay|1981}}, {{harvtxt|Schmidt|Druffel|1976}}, {{harvtxt|Ullman|1976}}, और {{harvtxt|Stoichev|2019}}. जबकि वे [[यादृच्छिक रेखांकन]] पर अच्छा प्रदर्शन करते दिखते हैं, इन एल्गोरिदम का एक बड़ा दोष सबसे अच्छा, सबसे खराब और औसत मामले में उनका घातीय समय प्रदर्शन है।{{sfnp|Foggia|Sansone|Vento|2001}}
+इससे पूर्व, सबसे अच्छा वर्तमान में स्वीकृत सैद्धांतिक एल्गोरिथम  {{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) द्वारा ग्राफ़ के विषय से मेल खाने वाली एक उप-घातीय ऊपरी सीमा प्राप्त की गई थी।
-ग्राफ़ समरूपता समस्या कम्प्यूटेशनल रूप से ग्राफ़ के ऑटोमोर्फिज़्म समूह की गणना करने की समस्या के समतुल्य है, <रेफ नाम = लुक्स पीपी। 139-175 >{{cite book | last=Luks | first=Eugene | title=असतत गणित और सैद्धांतिक कंप्यूटर विज्ञान में DIMACS श्रृंखला| chapter=Permutation groups and polynomial-time computation | publisher=American Mathematical Society | location=Providence, Rhode Island | date=1993-09-01 | volume=11 | isbn=978-0-8218-6599-6 | issn=1052-1798 | doi=10.1090/dimacs/011/11 | pages=139–175}}</ref><ref>Algeboy (https://cs.stackexchange.com/users/90177/algeboy), Graph isomorphism and the automorphism group, URL (version: 2018-09-20): https://cs.stackexchange.com/q/97575</ref> और क्रमचय समूह समरूपता समस्या और क्रमचय समूह प्रतिच्छेदन समस्या से कमजोर है। बाद की दो समस्याओं के लिए, {{harvtxt|Babai|Kantor|Luks|1983}} ग्राफ आइसोमोर्फिज्म के समान जटिलता सीमा प्राप्त की।
+ग्राफ समरूपता के लिए कई प्रतिस्पर्धी व्यावहारिक एल्गोरिदम हैं, जैसे कि मैकके (1981), श्मिट और ड्रफेल (1976), उल्मैन (1976), और स्टोइचेव (2019) के कारण। जबकि वे [[यादृच्छिक रेखांकन|यादृच्छिक ग्राफ]] पर अच्छा प्रदर्शन करते दिखते हैं, इन एल्गोरिदम का एक बड़ा दोष सबसे निम्न स्थिति में उनका घातीय समय प्रदर्शन है।
-== हल किए गए विशेष मामले ==
+ग्राफ समरूपता समस्या संगणनात्मक रूप से एक ग्राफ के स्वसमाकृतिकता समूह की गणना करने की समस्या के समान है, [16] [17] और क्रमपरिवर्तन समूह समरूपता समस्या और क्रमचय समूह प्रतिच्छेद की समस्या से कमजोर है। पश्चात की दो समस्याओं के लिए, बाबई, कांटोर और लुक्स (1983) ने ग्राफ समरूपता के समान जटिलता सीमाएँ प्राप्त कीं।
-ग्राफ समरूपता समस्या के कई महत्वपूर्ण विशेष मामलों में कुशल, बहुपद-समय समाधान हैं:
+== हल किए गए विशेष विषय ==
+ग्राफ समरूपता समस्या के कई महत्वपूर्ण विशेष विषयों में कुशल, बहुपद-समय का समाधान हैं:
 * [[ वृक्ष (ग्राफ सिद्धांत) ]] एस{{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}}
-** रंग-संरक्षण आइसोमोर्फिज्म [[रंगीन ग्राफ]]़ का बंधी हुई रंग बहुलता के साथ (अर्थात, अधिकांश k कोने में एक निश्चित k के लिए समान रंग होता है) वर्ग NC (जटिलता) में है, जो P (जटिलता) का एक उपवर्ग है।{{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 45: / Line 46: @@
 ==== अन्य वस्तुओं की समरूपता ====
 गणितीय वस्तुओं के कई वर्ग हैं जिनके लिए समरूपता की समस्या एक जीआई-पूर्ण समस्या है। उनमें से कई अतिरिक्त गुणों या प्रतिबंधों से संपन्न ग्राफ़ हैं:<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/>* रेडिकल पर जीरो स्क्वेयर रेडिकल और कम्यूटेटिव फैक्टर के साथ फिक्स्ड बीजगणितीय रूप से बंद फील्ड पर एक फील्ड पर परिमित रैंक सहयोगी बीजगणित।<!-- whoah --><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/>
-* रेखांकन विभाजित करें{{sfnp|Chung|1985}}
+* ग्राफ विभाजित करें{{sfnp|Chung|1985}}
-* तारकीय रेखांकन<ref name=zkt/>
+* तारकीय ग्राफ<ref name=zkt/>
-* नियमित स्व-पूरक रेखांकन<ref name=zkt/>
+* नियमित स्व-पूरक ग्राफ<ref name=zkt/>
 * मनमाना आयामों में सामान्य, सरल पॉलीटोप, और [[[[साधारण पॉलीटॉप]]]] उत्तल पॉलीटोप्स के [[पॉलीटॉपल ग्राफ]]।{{sfnp|Kaibel|Schwartz|2003}}
 डिग्राफ के कई वर्ग भी जीआई-पूर्ण हैं।
@@ Line 66: / Line 67: @@
 समरूपता समस्याओं के अलावा अन्य गैर-तुच्छ जीआई-पूर्ण समस्याएं भी हैं।
 * किसी ग्राफ या डिग्राफ की आत्म-पूरकता की मान्यता।{{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}}
@@ Line 73: / Line 74: @@
 * यह तय करने की समस्या कि [[वी-विवरण]] या [[एच-विवरण]] द्वारा दिए गए दो उत्तल पॉलीटोप्स प्रोजेक्टिवली या एफ़िनली आइसोमोर्फिक हैं। उत्तरार्द्ध का मतलब रिक्त स्थान के बीच एक प्रोजेक्टिव या एफ़िन मानचित्र का अस्तित्व है जिसमें दो पॉलीटोप्स होते हैं (जरूरी नहीं कि समान आयाम हों) जो पॉलीटोप्स के बीच एक आक्षेप को प्रेरित करता है।{{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}}
 == यह भी देखें ==
@@ Line 649: / Line 651: @@
 श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत
+[[Category:CS1]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:CS1 maint]]
 [[Category:Created On 06/05/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 14:25, 11 August 2023

Contents

अत्याधुनिक

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

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

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

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

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

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

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

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

अनुप्रयोग

यह भी देखें

टिप्पणियाँ

संदर्भ

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

सॉफ्टवेयर

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 14:25, 11 August 2023

अत्याधुनिक

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

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

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

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

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

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

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

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

अनुप्रयोग

यह भी देखें

टिप्पणियाँ

संदर्भ

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

सॉफ्टवेयर

Navigation

Wiki tools

Page tools

Other projects

Hidden categories