Get best of the week

दो रेखांकन की आइसोमोर्फिज्म का सत्यापन और आइसोमॉर्फिक सबग्राफ की खोज: एनबी-पाथ एनालिसिस पर आधारित एक दृष्टिकोण

सभी को नमस्कार।

ऐसा कार्य है - यह जांचने के लिए कि क्या दो ग्राफ एक-दूसरे के लिए समसामयिक हैं। यही है, इसे सीधे शब्दों में कहें, यह पता लगाने के लिए कि क्या ये दोनों ग्राफ़ "समान" ग्राफ़ हैं, लेकिन विभिन्न शीर्ष संख्याओं के साथ और, यदि ग्राफ़ को अलग-अलग स्थानिक स्थानों के साथ रेखांकन निर्दिष्ट किया गया है। इस समस्या का समाधान उतना स्पष्ट नहीं है जितना पहली नज़र में किसी को लग सकता है: यहां तक ​​कि छोटे रेखांकन के लिए, उनके चित्रमय प्रतिनिधित्व पर एक नज़र हमेशा एक स्पष्ट जवाब नहीं देगा। उदाहरण के लिए, समान विकी पर एक चित्र देखें: en.wikipedia.org/wiki/Graph_isomorphism.Example ।

प्रत्यक्ष रूप से?

लेकिन एक और मुश्किल काम है: सभी सबग्राफ के लिए "बड़े" ग्राफ में खोज करने के लिए कुछ अन्य "छोटे" ग्राफ के लिए आइसोमोर्फिक। यह एक और भी अधिक "अंधेरा जंगल" है। यह निश्चित रूप से, पूरी तरह से अंधेरा नहीं है, लेकिन कार्य, जिसे आप देखते हैं, सबसे आसान नहीं है।

तो हमारे पास क्या है?

1. यह सब क्यों जरूरी है?


और यद्यपि आइसोमॉर्फिक (उप) ग्राफ़ की समस्या, जैसा कि हमने पहले ही उल्लेख किया है, जटिल है, यह काफी आवश्यक और उपयोगी है। किस लिए? और फिर, उदाहरण के लिए, अपने संरचनात्मक सूत्र द्वारा दिए गए अणु के समान रासायनिक यौगिकों के लिए डेटाबेस की खोज करना। सब के बाद, यह एक ग्राफ के रूप में कल्पना की जा सकती है, है ना? रसायन विज्ञान यह करता है - ऐसा एक विज्ञान है। लेकिन नमूने के साथ तुलना के कार्य भी हैं, विभिन्न जैव सूचनात्मक कार्य, और कई अन्य दिलचस्प चीजें।

2. इस समस्या को कैसे हल करें?


इस समस्या को हल करने के लिए शास्त्रीय दृष्टिकोण जे। उल्मन द्वारा 1976 में रखा गया था [3], बाद में उन्होंने अपने एल्गोरिथ्म में काफी सुधार किया [4]। इसके अलावा, इस दृष्टिकोण को कई अन्य लेखकों के कामों में आगे विकसित किया गया था, उदाहरण के लिए, कॉर्डेला एट अल। [2] (एल्गोरिथ्म VF2), बोनित्सि एट अल। [1] (एल्गोरिथ्म आरआई), आदि

। संक्षेप में, इस दृष्टिकोण का सार "स्मार्ट" है। नमूना ग्राफ B और ग्राफ A के कोने के संभावित पत्राचारों की गणना करना जिसमें यह खोजा जा रहा है। यह खोज विभिन्न स्थितियों और प्रतिबंधों को दर्ज करने के लिए इसे "स्मार्ट" बनाती है जो आपको अनुपयुक्त विकल्पों को जल्द से जल्द काटने की अनुमति देता है। इन उद्देश्यों के लिए, स्रोत डेटा के विभिन्न प्रारंभिक प्रसंस्करण किए जा सकते हैं।

हम यहां इन कार्यों को वापस लेने में संलग्न नहीं होंगे, लेकिन हम पाठक को स्वतंत्र रूप से उनसे परिचित होने के लिए आमंत्रित करेंगे। हालांकि, "एक शो एक आदेश से बेहतर है", और यह ध्यान दिया जाना चाहिए कि वेब पर इन एल्गोरिदम के अच्छे ग्राफिक उदाहरण और स्पष्टीकरण हैं। उदाहरण के लिए, निम्न देखें:
coderoad.ru/17480142/Is-or-simple-example-for-explanation-algorithm-Ulman - एक उदाहरण के साथ बहुत अच्छी और स्पष्ट व्याख्या,
मुद्दा .life / questions / 8176298 - उदाहरण के साथ VF2 एल्गोरिथ्म के चरण। ।

हालांकि, सवाल उठता है - क्या इस समस्या को हल करने के लिए कोई अन्य संभव तरीके और दृष्टिकोण हैं, कुछ विशेष मामलों के लिए? और मैं आपको इस प्रश्न के संभावित उत्तरों में से एक से परिचित कराना चाहूंगा।

2. रेखांकन और नायब-रास्तों की समरूपता


आइए तुरंत सहमत हों: एनबी-पथों के तहत (और अंग्रेजी से नहीं, लेकिन सिर्फ इसलिए कि यह बहुत छोटा है) हम मैक्सिमल गैर-शाखाएं पथ कहेंगे, अर्थात्। कुछ ग्राफ के अधिकतम लंबे अनियंत्रित पथ।

इसलिए, यदि हमारे पास दो ग्राफ़ हैं जो एक-दूसरे के लिए आइसोमोर्फिक हैं , तो मैक्सिमली विस्तारित गैर-ब्रांचिंग पथ (यानी, हमारे एनबी पथ) के अनुक्रम के रूप में पहले ग्राफ़ के किसी भी प्रतिनिधित्व के लिए, हमेशा उसी के अनुरूप दूसरे ग्राफ़ के समान प्रतिनिधित्व मौजूद हैं, और एक ही समय में:

  • निर्देशित रेखांकन के लिए, एक दूसरे से संबंधित पथ संरेखित किए जाएंगे,
  • अप्रत्यक्ष रेखांकन (और उन्मुख रेखांकन के लिए, आवक और बाहर जाने वाले किनारों की संख्या, क्रमशः) के लिए एक-दूसरे के संगत कोने की डिग्री समान होगी
  • जब इस तरह के निरूपण के "संयोजन" के रूप में, हमारे पास पहले और दूसरे ग्राफ़ के कोने के पत्राचार होंगे।

एक उदाहरण है । ग्राफ A = {1-> 2, 1-> 6, 4-> 5, 5-> 1, 3-> 3}। ग्राफ B = {3-> 4, 3-> 5, 1-> 2, 2-> 3, 6-> 6}
पाथसा ( A का अधिकतम गैर-शाखा पथ ): 1-> 2, 1-> 6, 4-> 5-> 1, 3-> 3
पाथ्सबी ( बी का अधिकतम गैर-शाखा पथ ): 3-> 4, 3-> 5, 1-> 2-> 3, 6-> 6 वर्टेक्स मिलान
: 1 ( A): 3 (B), 2 (A): 4 (B), 6 (A): 5 (B), 4 (A): 1 (B), 5 (A): 2 (B), 3 ( ए): 6 (बी)।

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

A : 1, 2, 6, 4, 5, 3
B : 3, 4, 5, 1, 2, 6

वर्धमान मैट्रिक्स a के लिए दिए गए क्रम के लिए:

छवि

आसन्न मैट्रिक्स बी के लिए दिए गए क्रम के लिए:

छवि

मेट्रिसेस समान हैं, इसलिए, ए और बी ग्राफ आइसोमॉर्फिक हैं।

इसके अलावा, यह दृष्टिकोण (1) दोनों उन्मुख और गैर-उन्मुख रेखांकन के लिए लागू है, (2) यह एक से अधिक जुड़े घटक / मजबूत कनेक्शन वाले ग्राफ़ के लिए लागू है, (3) यह कई (एकाधिक) किनारों और छोरों वाले ग्राफ़ के लिए लागू है, हालांकि (4) उस कोने को ध्यान में नहीं रखता है जिसके लिए इसके किनारों की घटना नहीं है।

3. खैर, रेखांकन के समरूपता की जाँच की। लेकिन सबग्राफ की खोज के बारे में क्या?


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

इसके अलावा, जब इस समस्या को हल करते हैं, तो लंबाई में ए और बी के ग्राफ के एनबी रास्तों के पत्राचार की खोज के अलावा (जैसा कि ऊपर आइसोमॉर्फिज्म परीक्षण के साथ मामला था), उनके लिए निम्नलिखित संभावित पत्राचार को अलग से खोजना भी आवश्यक है:

  • एनबी रास्तों का पत्राचार - ग्राफ बी से एनबी रास्तों तक की सरल जंजीर - सरल जंजीरों / ग्राफ के सरल चक्र। इसके अलावा, शुरू में ग्राफ ए में ऐसे मार्ग अधिक लंबे हो सकते हैं - इस मामले में, उनके खंडों को लिया जाता है जो बी से वांछित पथ के बराबर हैं।
  • एनबी के पत्राचार - ग्राफ ए के किसी भी एनबी-रास्तों के लिए ग्राफ बी के पथ।

आइए एक उदाहरण देखें:

छवि

जब कॉलम A में ग्राफ B के "उत्कीर्ण" आइसोमोर्फिक सबग्राफ की खोज की जाती है (ऊपर चित्र देखें), निम्नलिखित पत्र मिलेंगे:

  • आंतरिक पथ 2-> 3-> कॉलम B का 4: आंतरिक पथ 2-> 3-> 4 कॉलम A का,
  • अंतिम रास्ते 1-> 2 और 10-> कॉलम 2 के बी: एंड पाथ 0-> कॉलम ए के 2 और अंतिम रास्ते के टुकड़े 7- ए> 1-> कॉलम ए के 2, अर्थात् 1-> 2,
  • 7->8 B: 9->10->11 A, 9->10 10->11, 12->13->14->12 A, 12->13, 13->14, 14->12.

इस प्रकार, ग्राफ A के "अंकित" उपग्रहों के रूप में, जो कि ग्राफ B के समद्विबाहु हैं, निम्नलिखित 5 विकल्प पाए जा सकते हैं:

A1 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 9-> 10}
A2 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 10-> 11}
A3 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 12-> 13}
A4 = {0-> 2, 1-> 2, 2 -> 3, 3-> 4, 4-> 5, 4-> 6, 13-> 14}
A5 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 14-> 12}

हालांकि, अगर हम ग्राफ ए में एक अतिरिक्त बढ़त 3-> 8 जोड़ते हैं, तो हमें ग्राफ ए '(समान आकृति में नीचे) मिलता है। और 'ए' में अब कोई भी "अंकित" सबग्राफ नहीं होगा ग्राफ बी के लिए समद्विभाजक। वास्तव में: किनारे 3-> 8 "विभाजन" पथ 2-> 3-> 4 ग्राफ के ए में दो और इसलिए, आंतरिक पथ 2 के लिए उम्मीदवार ->3- "4 कॉलम B नहीं मिलेगा।

4. अब एल्गोरिथ्म ही


अब हम कॉलम ए में उप-भाग "उत्कीर्ण" के लिए खोज एल्गोरिथ्म की अधिक विस्तृत परीक्षा में आगे बढ़ सकते हैं जो कि कुछ स्तंभ बी के समद्विबाहु हैं।

इसलिए, एल्गोरिथ्म में 4 चरण शामिल होंगे:

  • preprocessing
  • मेल मिलाना
  • thinning,
  • निष्कर्ष

चरण I प्रीप्रोसेसिंग


इस स्तर पर, हम प्रत्येक रेखांकन के लिए सभी NB-पाथ ढूँढते हैं, साथ ही उन कारकों का मूल्यांकन करते हैं, जो ज्ञान के दौरान पसंद स्थान को सीमित करते हैं। उन। हम निम्नलिखित करते हैं:

  1. हम कॉलम ए में सभी एनबी-पथों को ढूंढते हैं और उन्हें एक गतिशील सरणी (सी ++ में - एक वेक्टर में) पथ में डालते हैं
  2. हम कॉलम बी में सभी एनबी-पथ पाते हैं और उन्हें एक डायनामिक ऐरे (वेक्टर) पाथ्सबी में डालते हैं
  3. A B. II-IV , 1. A- B B: - , B.
  4. A B ( ).
  5. A B: DA DB .
  6. – B00 – B , , .

तो, हमारे पास ग्राफ़ और सीमा मापदंडों दोनों पर p.p. से एनबी-पथ हैं। 3-5।

स्टेज II। मानचित्रण


इस स्तर पर, हम कॉलम एन से प्रत्येक के लिए कॉलम एन से उम्मीदवार एनबी पथ (इसके बाद बस "उम्मीदवार पथ" के रूप में संदर्भित) का चयन करेंगे। प्रत्येक ith पथ PathsB के लिए पथ से प्रत्येक उम्मीदवार पथ को चिह्नित करना। ] को दो-आयामी गतिशील सरणी (C ++ में - वैक्टर के एक वेक्टर के लिए) लिखा जाएगा - NPaths - क्रमशः i-th वेक्टर (i-th लाइन) के लिए - क्रमबद्ध ट्रिपल संख्या के रूप में: PathsA में संबंधित पथ की संख्या - इसमें प्रारंभिक स्थिति की संख्या - पथ की लंबाई ।

उदाहरण के लिए, PathsB [2] = {1, 0, 3, 3, 1, 3} का अर्थ है कि PathsB [2] पथ A से 2 प्रत्याशी पथ से संबद्ध हैं: PathsA [1] से - शून्य से शुरू होने वाले पहले 3 पथ तत्व प्रारंभिक), और पाथ्स [3] से - पहले (शुरुआती के बगल में) से शुरू होने वाले 3 तत्व भी।

उसी समय, हम 4 दिशाओं में उम्मीदवार पथ का चयन (चयन) करेंगे:

  1. पाथ्सबी से ग्राफ बी के सभी आंतरिक एनबी पथों के लिए उम्मीदवार पथ खोजें, अर्थात। जिन लोगों की दोनों सीमाएं लंबवत बी में कम से कम 2 अन्य कोणों (इस तरह के कनेक्शन की दिशा की परवाह किए बिना) से जुड़ी हुई हैं और साथ ही यह पथ एक सरल चक्र नहीं है (उन्मुख रेखांकन के लिए उन्मुख)।
  2. पाथ्सबी से एनबी पथ की अनुगामी के लिए उम्मीदवार पथ की खोज करें।
  3. NB रास्तों के लिए उम्मीदवार पथ की खोज करें - PathsB से सरल लूप।
  4. NB रास्तों के लिए उम्मीदवार पथ की खोज करें - PathsB से सरल पथ।

PathsB से प्रत्येक ith पथ के लिए उम्मीदवार पथ का चयन करते समय, उनकी तुलना की जाती है (यह वह जगह है जहां पहले से गणना किए गए सीमक के कुछ पैरामीटर काम में आते हैं):

  • इसकी लंबाई और उम्मीदवार पथ की लंबाई (मामलों 1 और 3 के बराबर होनी चाहिए, और मामलों 2 और 4 के लिए, PathsA से उम्मीदवार का रास्ता भी लंबा हो सकता है)
  • इसकी सीमा कोने की सीमा और उम्मीदवार पथ के संबंधित कोने (उम्मीदवार पथ से कोने के लिए, ये मान पथ से कम से कम पथ होना चाहिए)।

यदि, चरण II के परिणामों के अनुसार, PathsA से कोई भी उम्मीदवार पथ PathsB में से किसी भी पथ के लिए नहीं मिला था, तो यह माना जाता है कि A में स्तंभ B के लिए "अंकित" सबग्राफ इस्मॉर्फिक नहीं है।

thinning


अब आइए ग्राफ ए को "निचोड़ने" का प्रयास करें। हम इसमें केवल उन किनारों को छोड़ते हैं जो हमने पाए गए उम्मीदवार पथों में गए थे। यदि एक ही समय में, ग्राफ ए ने अपनी प्रारंभिक स्थिति की तुलना में कम से कम एक बढ़त खो दी है, तो हम चरण I "प्रीप्रोसेसिंग" पर लौटते हैं: ग्राफ ए के कोने की डिग्री और, तदनुसार, उम्मीदवार पथों की सूची को कम किया जा सकता है और, तदनुसार, खोज स्थान को कम किया जा सकता है।

स्टेज III। उम्मीदवार रास्तों की सूची को पतला करना


इस कदम का उद्देश्य अधिक से अधिक उम्मीदवारों को यथासंभव अनुचित को खत्म करना है। ऐसा करने के लिए, हम निम्नलिखित चरणों को पूरा करते हैं।

  1. कॉलम B. में खामियों के बीच न्यूनतम दूरी के आधार पर स्पष्ट रूप से अनुचित उम्मीदवार पथों का बहिष्कार कॉलम A में पथ A की पथ सीमाएँ [i] और PathsB [j] की संगत सीमा रेखाओं के बीच कॉलम A में उनकी सीमा रेखाओं के बीच की दूरी सबसे कम या बराबर दूरी से कम थी।
  2. PathsB से गैर-चक्रीय उम्मीदवार पथ से जुड़े सभी चक्रों के लिए एक अपवाद और इसके विपरीत।
  3. अभ्यर्थी का अपवाद धारा 1 के समान है, लेकिन सीमा के अंतर के बीच कम से कम दूरी की कसौटी से नहीं, बल्कि आपसी समानता या असमानता के लिए उनकी (सीमा की ओर)।

उदाहरण के लिए, यदि:

  • PathsB का प्रारंभिक तत्व [i] PathsB [j] के शुरुआती तत्व के बराबर नहीं है, और
  • PathsB का अंतिम तत्व [i] PathsB [j] के अंतिम तत्व के बराबर नहीं है, और
  • PathsB [i] का प्रारंभिक तत्व PathsB [j] के अंतिम तत्व के बराबर है, और
  • PathsB [j] का प्रारंभिक तत्व, PathsB के अंतिम तत्व के बराबर नहीं है [i]

PathsB [i] पथ के साथ उम्मीदवार पथ, जिसके लिए कम से कम एक PathsB [j] को कोई भी उम्मीदवार पथ नहीं मिला जो उनके (उम्मीदवार पथों) की समानता / असमानता के बारे में उपरोक्त स्थिति को संतुष्ट करता हो। चोटियों।

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

यदि, चरण III के परिणामों के अनुसार, कम से कम 1 उम्मीदवार पथ PathsA से हटा दिया गया था, तो - फिर से - स्तंभ A अपडेट किया गया है - केवल उन किनारों को जो शेष उम्मीदवार पथों में शामिल हैं, उसमें बने हुए हैं। और, फिर से, यदि एक ही समय में, कम से कम एक किनारे पर ग्राफ ए "खो वजन", हम फिर से मंच I "प्रीप्रोसेसिंग" पर लौटते हैं: ग्राफ ए के कोने की डिग्री और, तदनुसार, उम्मीदवार पथों की सूची को कम किया जा सकता है, तदनुसार, कम किया जा सकता है। खोज स्थान।

चरण IV। निष्कर्ष


सभी शेष उम्मीदवार रास्तों का प्रत्येक संभावित संयोजन कॉलम ए के एक सबग्राफ को परिभाषित करता है। ऐसे प्रत्येक सबग्राफ के लिए, एक आसन्न मैट्रिक्स का निर्माण उसी तरह से उम्मीदवार पथों के क्रम को ध्यान में रखते हुए किया जाता है जैसे कि आसन्न मैट्रिक्स B00 को ग्राफ बी के लिए बनाया गया था, और फिर इन आसन्न मैट्रिक्स की तुलना की जाती है।

यदि वे समान हैं, तो किनारों की बहुलता की तुलना की जाती है (चरण I प्रीप्रोसेसिंग के सेकंड 3 देखें)। यदि ये सभी शर्तें पूरी हो जाती हैं, तो पाया गया उपसमूह ग्राफ बी में आइसोमोर्फिक माना जाता है और पाए गए परिणामों के सेट में जोड़ा जाता है।

चरण IV "निष्कर्ष" के दौरान, एक अनुचित उपसमूह की पहचान और अस्वीकृति को तेज करने के लिए विभिन्न अतिरिक्त जांच का उपयोग किया जा सकता है।

5. सब कुछ कैसे उलझन में है ... एल्गोरिथ्म के एक उदाहरण पर विचार करें


मैं आपके बारे में नहीं जानता, लेकिन यह मेरे लिए एक उदाहरण के बिना समझ से बाहर होगा। आइए एक उदाहरण देखें।

अंजीर में। नीचे दिए गए रेखांकन A = {1-> 2, 2-> 5, 5-> 15, 16-> 15, 5-> 5, 5-> 5, 5-> 4, 5-> 6, 7-> 6 हैं , 6-> 8, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 0-> 12, 4-> 13, 13-> 14, 14-> 4 } और B = {1-> 1, 4-> 5, 5-> 1, 1-> 3, 3-> 3, 3-> 2, 2-> 7, 2-> 8, 9-> 10 10-> 9, 1-> 6, 6-> 11, 11-> 12, 12-> 6}। हमारा कार्य ग्राफ ए में पाया जाना है। सभी "अंकित" सबग्राफ, आइसोमॉर्फिक से ग्राफ बी। परिणाम भी आकृति में दिखाया गया है: ग्राफ ए के पाए गए कोने और किनारों को एक मोटी रेखा द्वारा हाइलाइट किया गया है, और ग्राफ बी के संबंधित कोने की संख्या कोष्ठक में इंगित किया गया है (यदि कई विकल्प हैं, तो वे संकेत देते हैं। अंश)।

छवि

स्तंभ B के "अछूता" उपसमूह के स्तंभ A में खोज समस्या को हल करते समय,हमारे पास एल्गोरिथम के निम्नलिखित परिणाम हैं।

स्टेज I: सभी कार्य और गणना p.p के अनुसार किए गए थे। इस चरण के 1-5, निम्नलिखित परिणामी PathsA और PathsB हैं।

PathsA:

1-> 2-> 5
4-> 13-> 14 4
5-> 4
5-> 5
5-> 6
5-> 15
6-> 6
6-> 8
6-> 9
7-> 6
9 -> 10
9-> 11
16-> 15
0-> 12-> 0

PathsB:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4- > 5-> 1
6-> 11-> 12-> 6
9-> 10-> 9

चरण II-III। तुलना से पता चला है कि PathsA से प्रत्येक पथ के लिए PathsB से कम से कम एक उम्मीदवार पथ है, और प्रारंभिक thinning के परिणामों से PathsA को छोटा कर दिया गया था। मुख्य थिनिंग (III) के स्तर पर, पथ्सए की और कमी नहीं हुई। परिणामस्वरूप, PathsA और PathsB ने फॉर्म लिया:

PathsA:

1-> 2-> 5
4-> 13-> 14-> 4
5-> 4
5-> 5
5-> 6
6-> 6
6-> 9
9-> 10
9-> 11
0-> 12-> 0

पाथ्सबी:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4-> 5-> 1
6 -> 11-> 12-> 6
9-> 10->9

NPaths की अंतिम तुलना है:
NPaths:

i = 0: 3 0 2
i = 1: 4 0 2
i = 2: 2 0 2
i = 3: 7 0 2 8 0 2
i = 4: 7 0 2 8 0 2
i = 5: 6 0 2
i = 6: 5 0 2
i = 7: 0 0 3
i = 8: 1 0 4
i = 9: 9 0 3

यहाँ यह याद करने का समय है कि प्रत्येक ने NPaths में संख्याओं के तिहरे क्रम का आदेश दिया [i] इसी पथ को परिभाषित करता है [i] उम्मीदवार पथ प्रारूप में ए से: पथसे से संबंधित पथ की संख्या - इस पथ से खंड की प्रारंभिक स्थिति - खंड की लंबाई। इस प्रकार, यह सत्यापित करना आसान है कि pathsB [0] = {1-> 1} (i = 0: 3 0 2) A से एकमात्र पथ से संबंधित है, अर्थात्, PathsA से खंड [3], बहुत शुरुआत से शुरू होता है और लंबाई 2.

चरण IV। नतीजतन, कॉलम ए में एक अनोखा सबग्राफ ए 1 पाया गया, आइसोमोर्फिक से बी ए 1 = {0-> 12, 1-> 2, 2-> 5, 4-> 13, 5-> 4, 5-> 5, 5- > 6, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 13-> 14, 14-> 4}।

5. आगे क्या?


और फिर, सिद्धांत रूप में, यह सब है हालांकि काफी नहीं: लेखक को यह स्वीकार करना चाहिए कि एल्गोरिथ्म को अभी भी अंतिम रूप दिया जा सकता है और अंतिम रूप दिया जा सकता है। जोड़ने के लिए क्या है?

  1. जब कॉलम ए और बी के कोने की अतिरिक्त विशेषताएं पेश की जाती हैं (उदाहरण के लिए, जब यौगिकों को रासायनिक यौगिकों के ग्राफ द्वारा दिया जाता है, तो एक संख्यात्मक कोड एक और केवल एक परमाणु (आइसोटोप) प्रत्येक शीर्ष के साथ जुड़ा हो सकता है), चरण II के अनुसार तुलना की अधिक सटीकता के कारण खोज प्रक्रिया को तेज किया जा सकता है: अतिरिक्त उम्मीदवार पथ का चयन करने के लिए शर्त शीर्ष लेबल के पत्राचार होंगे।
  2. . , «», «» - B.
  3. , , , «» :
    (1) «» , ,
    (2) .
    «» « - », , , .
  4. , - , .


समस्याओं पर सामान्य:
1. बोनीकी, वी।, गियुगनो, आर।, पुलविरेन्ती, ए। एट अल। एक उपसमूह समरूपता एल्गोरिथ्म और जैव रासायनिक डेटा के लिए इसका अनुप्रयोग। बीएमसी जैव सूचना विज्ञान 14, एस 13 (2013)। doi.org/10.1186/1471-2105-14-S7-S13 ।
2. कॉर्डेला एल, फोगिया पी, सेन्सोन सी, वेंटो एम: ए (उप) ग्राफ इस्मोर्फिज्म एल्गोरिदम बड़े मिलान के लिए। पैटर्न एनालिसिस और मशीन इंटेलिजेंस पर आईईईई लेनदेन। 2004, 26 (10): 1367-1372। 10.1109 / TPAMI.2004.75।
3. उलेमन जूलियन आर।: सबग्राफ आइसोमॉर्फिज़्म के लिए एक एल्गोरिथ्म। कम्प्यूटिंग मशीनरी के लिए एसोसिएशन के जर्नल। 1976, 23: 31-42। 10.1145 / 321921.321925।
4. उल्मन जूलियन आर।: द्विआधारी बाधा संतुष्टि और उपसमूह समरूपता के लिए बिट-वेक्टर एल्गोरिदम। जम्मू ऍक्स्प एल्गोरिदम। 2011, 15 (1.6): 1.1-1.6। 1.64

इस बारे में अधिक आधिकारिक भाषा में लिखे गए लेखक की छाप सबसे "एनबी-पाथ्स-आधारित एल्गोरिथ्म" है, जिसमें इसे C ++ में लागू करने के प्रयास के बारे में जानकारी भी शामिल है:
5. चेरनखोव SA 2020. प्रीप्रिंट। RU। दो ग्राफ़ों के समरूपता की जाँच करना और समरूप "अछूता" उपसमूहों की खोज करना: अधिकतम (उप) ग्राफ़ समरूपतावाद समस्या को हल करने के लिए अधिकतम विस्तारित गैर-शाखा पथ के विश्लेषण के आधार पर एक दृष्टिकोण। DOI: dx.doi.org/10.24108/preprints-3111977

: विषय पर उपयोगी इंटरनेट स्रोतों
6. coderoad.ru/17480142/Is-li- सरल-उदाहरण के लिए स्पष्टीकरण-कलन विधि-Ulman
7. issue.life/questions / 8,176,298 ।

More articles:


All Articles