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

ग्राफ सिद्धांत में, ग्राफ (असतत गणित) G और H का एक समरूपता G और H के वर्टेक्स सेट के बीच एक आक्षेप है।

f\colon V(G)\to V(H)

जैसे कि G के कोई भी दो शीर्ष u और v आसन्न हैं (ग्राफ़ सिद्धांत) G में यदि और केवल यदि $f(u)$ और $f(v)$ एच में आसन्न हैं। इस तरह के आक्षेपण को आमतौर पर धार-संरक्षण वाले आक्षेप के रूप में वर्णित किया जाता है, समरूपता की सामान्य धारणा के अनुसार एक संरचना-संरक्षण आक्षेप है। यदि दो ग्राफ़ के बीच एक तुल्याकारिता मौजूद है, तो ग्राफ़ को 'समरूपी' कहा जाता है और इसे इस रूप में निरूपित किया जाता है $G\simeq H$ . इस मामले में जब आपत्ति स्वयं पर एक ग्राफ का मानचित्रण होता है, यानी, जब जी और एच एक और एक ही ग्राफ होते हैं, तो आपत्ति को जी के ग्राफ ऑटोमोर्फिज्म कहा जाता है। यदि एक ग्राफ परिमित है, तो हम इसे एकैकी/आच्छादक दिखा कर इसे एकैकी/आच्छादक सिद्ध कर सकते हैं; दोनों को दिखाने की जरूरत नहीं है। ग्राफ़ आइसोमोर्फिज़्म ग्राफ़ पर एक तुल्यता संबंध है और इस तरह यह तुल्यता वर्ग ों में सभी ग्राफ़ के वर्ग (सेट सिद्धांत) को विभाजित करता है। रेखांकन का एक सेट एक दूसरे के लिए समरूपता को रेखांकन का 'समरूपता वर्ग ' कहा जाता है। कंप्यूटर विज्ञान में एक बड़ी अनसुलझी समस्या है कि क्या ग्राफ समरूपता को बहुपद समय में निर्धारित किया जा सकता है।

नीचे दिखाए गए दो ग्राफ़ आइसोमॉर्फिक हैं, उनके अलग-अलग दिखने वाले ग्राफ ड्राइंग के बावजूद।

Graph G	Graph H	An isomorphism between G and H
		f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7

रूपांतर

उपरोक्त परिभाषा में, ग्राफ़ को निर्देशित ग्राफ ़ लेबल किए गए ग्राफ़ के रूप में समझा जाता है | गैर-लेबल वाले भारित ग्राफ ़ | गैर-भारित ग्राफ़। हालांकि, संरचना के संबंधित अतिरिक्त तत्वों को संरक्षित करने के लिए आवश्यकताओं को जोड़कर, आइसोमॉर्फिक की धारणा को ग्राफ की धारणा के अन्य सभी प्रकारों पर लागू किया जा सकता है: चाप दिशाएं, बढ़त भार, आदि, निम्नलिखित अपवाद के साथ।

लेबल किए गए रेखांकन की समरूपता

लेबल किए गए रेखांकन के लिए, समरूपता की दो परिभाषाएँ उपयोग में हैं।

एक परिभाषा के तहत, एक समरूपता एक चरम आक्षेप है जो बढ़त-संरक्षण और लेबल-संरक्षण दोनों है।^[1]^[2] एक अन्य परिभाषा के तहत, एक समरूपता एक बढ़त-संरक्षण वर्टेक्स आक्षेप है जो लेबल के समतुल्य वर्गों को संरक्षित करता है, अर्थात, समतुल्य (जैसे, समान) लेबल वाले शीर्षों को समतुल्य लेबल वाले शीर्षों पर मैप किया जाता है और इसके विपरीत; बढ़त लेबल के साथ ही।^[3] उदाहरण के लिए, द $K_{2}$ 1 और 2 के साथ लेबल किए गए दो कोने वाले ग्राफ में पहली परिभाषा के तहत एक ऑटोमोर्फिज्म है, लेकिन दूसरी परिभाषा के तहत दो ऑटो-मॉर्फिज्म हैं।

दूसरी परिभाषा कुछ स्थितियों में ग्रहण की जाती है जब ग्राफ़ अद्वितीय लेबल के साथ संपन्न होते हैं जो आमतौर पर पूर्णांक श्रेणी 1,..., n से लिए जाते हैं, जहाँ n ग्राफ़ के शीर्षों की संख्या होती है, जिसका उपयोग केवल विशिष्ट रूप से शीर्षों की पहचान करने के लिए किया जाता है। ऐसे मामलों में दो लेबल वाले ग्राफ़ को कभी-कभी आइसोमोर्फिक कहा जाता है यदि संबंधित अंतर्निहित लेबल रहित ग्राफ़ आइसोमॉर्फिक होते हैं (अन्यथा आइसोमोर्फिज़्म की परिभाषा तुच्छ होगी)।

प्रेरणा

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

ग्राफ़ आइसोमोर्फिज़्म की धारणा हमें ग्राफ़ की संरचनाओं में निहित ग्राफ़ गुणों को ग्राफ़ प्रस्तुतियों से जुड़े गुणों से अलग करने की अनुमति देती है: ग्राफ़ चित्र, ग्राफ़ (डेटा संरचना), ग्राफ लेबलिंग , आदि। उदाहरण के लिए, यदि किसी ग्राफ़ में ठीक एक चक्र है ( ग्राफ़ थ्योरी), तो इसके समरूपता वर्ग के सभी ग्राफ़ों में भी ठीक एक चक्र होता है। दूसरी ओर, सामान्य स्थिति में जब किसी ग्राफ के शीर्ष पूर्णांक 1, 2,... N द्वारा दर्शाए जाते हैं, तब व्यंजक

\sum _{v\in V(G)}v\cdot {\text{deg }}v

दो आइसोमॉर्फिक ग्राफ के लिए भिन्न हो सकते हैं।

व्हिटनी प्रमेय

व्हिटनी के प्रमेय का अपवाद: ये दो ग्राफ़ आइसोमॉर्फिक नहीं हैं, लेकिन आइसोमॉर्फिक लाइन ग्राफ़ हैं।

व्हिटनी ग्राफ समरूपता प्रमेय,^[4] हस्लर व्हिटनी द्वारा दिखाया गया, बताता है कि दो जुड़े हुए ग्राफ़ आइसोमोर्फिक हैं यदि और केवल अगर उनके लाइन ग्राफ ़ आइसोमोर्फिक हैं, एक अपवाद के साथ: के₃, तीन शीर्षों पर पूर्ण ग्राफ़ और पूर्ण द्विदलीय ग्राफ ़ K_1,3, जो तुल्याकारी नहीं हैं लेकिन दोनों में K है₃ उनके लाइन ग्राफ के रूप में। व्हिटनी ग्राफ प्रमेय को hypergraph तक बढ़ाया जा सकता है।^[5]

ग्राफ समरूपता की पहचान

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

इसके व्यावहारिक अनुप्रयोगों में मुख्य रूप से रासायनिक सूचना विज्ञान, गणितीय रसायन विज्ञान (रासायनिक यौगिकों की पहचान), और इलेक्ट्रॉनिक डिजाइन स्वचालन (विद्युत सर्किट के डिजाइन के विभिन्न अभ्यावेदन के तुल्यता का सत्यापन) शामिल हैं।

ग्राफ़ आइसोमोर्फिज़्म समस्या एनपी (जटिलता) से संबंधित कम्प्यूटेशनल जटिलता सिद्धांत में कुछ मानक समस्याओं में से एक है, लेकिन इसके प्रसिद्ध (और, यदि पी बनाम एनपी समस्या | पी ≠ एनपी, अलग करना) उपसमुच्चय से संबंधित नहीं है: पी (जटिलता) और एनपी-पूर्ण। यह केवल दो में से एक है, कुल 12 में से, सूचीबद्ध समस्याओं में से एक है Garey & Johnson (1979) जिसकी जटिलता अनसुलझी बनी हुई है, दूसरा पूर्णांक गुणनखंडन है। हालांकि यह ज्ञात है कि यदि समस्या एनपी-पूर्ण है तो बहुपद पदानुक्रम एक परिमित स्तर तक गिर जाता है।^[6] नवंबर 2015 में, शिकागो विश्वविद्यालय के एक गणितज्ञ और कंप्यूटर वैज्ञानिक लेज़्ज़्लो बाबई ने दावा किया कि उन्होंने यह साबित कर दिया है कि ग्राफ समरूपता समस्या अर्ध-बहुपद समय में हल करने योग्य है।^[7]^[8] उन्होंने कंप्यूटिंग के सिद्धांत पर 2016 की संगोष्ठी की कार्यवाही में इन परिणामों के प्रारंभिक संस्करणों को प्रकाशित किया,^[9] और गणितज्ञों की 2018 अंतर्राष्ट्रीय कांग्रेस।^[10] जनवरी 2017 में, बाबई ने अर्ध-बहुपद के दावे को संक्षिप्त रूप से वापस ले लिया और इसके बजाय उप-घातीय समय जटिलता को बाध्य किया। उन्होंने पांच दिन बाद मूल दावा बहाल कर दिया।^[11] As of 2020^[update], बाबई के पेपर का पूर्ण जर्नल संस्करण अभी तक प्रकाशित नहीं हुआ है।

इसका सामान्यीकरण, सबग्राफ समरूपता समस्या , एनपी-पूर्ण के रूप में जाना जाता है।

समस्या के लिए अनुसंधान के मुख्य क्षेत्र सामान्य समस्या और ग्राफ के विशेष वर्गों के लिए तेजी से एल्गोरिदम का डिजाइन और एल्गोरिदम के विश्लेषण के सैद्धांतिक जांच हैं।

यह भी देखें

↑ p.424
↑ "Efficient Method to Perform Isomorphism Testing of Labeled Graphs" in: Computational Science and Its Applications - ICCSA 2006, pp 422–431
↑ Pierre-Antoine Champin, Christine Solnon, "Measuring the Similarity of Labeled Graphs" in: Lecture Notes in Computer Science, vol. 2689, pp 80–95
↑ Whitney, Hassler (January 1932). "Congruent Graphs and the Connectivity of Graphs". American Journal of Mathematics. 54 (1): 150–168. doi:10.2307/2371086. hdl:10338.dmlcz/101067. JSTOR 2371086.
↑ Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.
↑ Schöning, Uwe (1988). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37 (3): 312–323. doi:10.1016/0022-0000(88)90010-4.
↑ Cho, Adrian (November 10, 2015), "Mathematician claims breakthrough in complexity theory", Science, doi:10.1126/science.aad7416.
↑ Klarreich, Erica (December 14, 2015), "Landmark Algorithm Breaks 30-Year Impasse", Quanta Magazine
↑ Babai, László (2016), "Graph isomorphism in quasipolynomial time [extended abstract]", STOC'16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, pp. 684–697, doi:10.1145/2897518.2897542, MR 3536606, S2CID 17118954
↑ Babai, László (2018), "Group, graphs, algorithms: the graph isomorphism problem", Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, pp. 3319–3336, MR 3966534
↑ Babai, László (January 9, 2017), Graph isomorphism update

संदर्भ

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5श्रेणी: ग्राफ़ एल्गोरिदम श्रेणी: रूपवाद

[1] .424

[2] "Efficient Method to Perform Isomorphism Testing of Labeled Graphs" in: Computational Science and Its Applications - ICCSA 2006, pp 422–431

[3] Pierre-Antoine Champin, Christine Solnon, "Measuring the Similarity of Labeled Graphs" in: Lecture Notes in Computer Science, vol. 2689, pp 80–95

[4] Whitney, Hassler (January 1932). "Congruent Graphs and the Connectivity of Graphs". American Journal of Mathematics. 54 (1): 150–168. doi:10.2307/2371086. hdl:10338.dmlcz/101067. JSTOR 2371086.

[5] Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.

[6] Schöning, Uwe (1988). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37 (3): 312–323. doi:10.1016/0022-0000(88)90010-4.

[7] Cho, Adrian (November 10, 2015), "Mathematician claims breakthrough in complexity theory", Science, doi:10.1126/science.aad7416.

[8] Klarreich, Erica (December 14, 2015), "Landmark Algorithm Breaks 30-Year Impasse", Quanta Magazine

[9] Babai, László (2016), "Graph isomorphism in quasipolynomial time [extended abstract]", STOC'16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, pp. 684–697, doi:10.1145/2897518.2897542, MR 3536606, S2CID 17118954

[10] Babai, László (2018), "Group, graphs, algorithms: the graph isomorphism problem", Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, pp. 3319–3336, MR 3966534

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

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

Contents