ग्राफ समरूपता समस्या

From Vigyanwiki

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

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

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

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


अत्याधुनिक

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

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

2O(n log2 n) द्वारा सबसे पहले लेज़्लो बाबई (1980) द्वारा दृढ़ता से नियमित ग्राफ के लिए प्राप्त किया गया था, और उसके पश्चात बाबई & लुक्स (1983) द्वारा सामान्य ग्राफ तक बढ़ाया गया,घातांक में सुधार √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] यदि वास्तव में ग्राफ समरूपता समस्या बहुपद समय में हल करने योग्य है, तो जीआई पी (जटिलता) के समान होगा। दूसरी ओर, यदि समस्या एनपी-पूर्ण है, तो जीआई एनपी (जटिलता) के समान होगा और एनपी में सभी समस्याएं अर्ध-बहुपद समय में हल करने योग्य होंगी।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

यह भी देखें

टिप्पणियाँ

  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.
  2. McKay (1981).
  3. Ullman (1976).
  4. Moore, Russell & Schulman (2008).
  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].
  14. Kelly (1957).
  15. Aho, Hopcroft & Ullman (1974), p. 84-86.
  16. Hopcroft & Wong (1974).
  17. Datta et al. (2009).
  18. Booth & Lueker (1979).
  19. Colbourn (1981).
  20. Muzychuk (2004).
  21. Bodlaender (1990).
  22. Miller 1980; Filotti & Mayer 1980.
  23. Luks (1982).
  24. Babai, Grigoryev & Mount (1982).
  25. Miller (1983).
  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
  29. Arvind & Köbler (2000).
  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)
  31. Narayanamurthy & Ravindran (2008).
  32. Grigor'ev (1981).
  33. Johnson (2005); Kaibel & Schwartz (2003).
  34. Chung (1985).
  35. 35.0 35.1 Kaibel & Schwartz (2003).
  36. Colbourn & Colbourn (1978).
  37. Kozen (1978).
  38. Shawe-Taylor & Pisanski (1994).
  39. Mathon (1979); Johnson 2005.
  40. Endika Bengoetxea, Ph.D., Abstract
  41. Irniger (2005).
  42. Cook & Holder (2007).
  43. 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.

सॉफ्टवेयर

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