Get best of the week

التحقق من تماثل الرسم البياني والبحث عن مخططات فرعية متشابهة: نهج قائم على تحليل مسارات ملحوظة

تحية للجميع.

هناك مثل هذه المهمة - للتحقق مما إذا كان رسمان بيانيان متماثلان لبعضهما البعض. وهذا ، ببساطة ، لمعرفة ما إذا كان كلا الرسمين البيانيين "نفس" الرسم البياني ، ولكن مع أرقام قمة مختلفة ، وإذا تم تحديد الرسوم البيانية ، مع مواقع مكانية مختلفة. إن حل هذه المشكلة ليس واضحًا كما قد يبدو لشخص ما للوهلة الأولى: حتى بالنسبة للرسوم البيانية الصغيرة ، فإن نظرة على تمثيلهم البياني لن تعطي دائمًا إجابة لا لبس فيها. انظر ، على سبيل المثال ، رسم على نفس ويكي: en.wikipedia.org/wiki/Graph_isomorphism#Example .

حسن من الواضح؟

ولكن هناك مهمة أكثر صعوبة: البحث في رسم بياني "كبير" عن كل الرسوم البيانية الفرعية غير متماثل إلى رسم بياني "أصغر" آخر. هذه هي "غابة مظلمة". هذا بالطبع ليس مظلمًا تمامًا ، لكن المهمة ، كما ترى ، ليست أسهل.

اذن ماذا عندنا؟

1. لماذا كل هذا ضروري؟


وعلى الرغم من أن مشكلة الرسوم البيانية المتشابهة ، كما ذكرنا من قبل ، معقدة ، إلا أنها ضرورية ومفيدة للغاية. لماذا؟ وبعد ذلك ، على سبيل المثال ، للبحث في قاعدة البيانات عن المركبات الكيميائية المشابهة لجزيء معين من خلال تركيبته الهيكلية. بعد كل شيء ، يمكن تخيله كرسم بياني ، أليس كذلك؟ تقوم المعلوماتية الكيميائية بذلك - هناك مثل هذا العلم. ولكن هناك أيضًا مهام للمقارنة مع العينة ، ومهام معلوماتية حيوية متنوعة ، والعديد من الأشياء الأخرى المثيرة للاهتمام.

2. كيف يمكن حل هذه المشكلة؟


تم وضع النهج الكلاسيكي لحل هذه المشكلة من قبل ج. أولمان في عام 1976 [3] ، وبعد ذلك قام بتحسين الخوارزمية بشكل كبير [4]. أيضًا ، تم تطوير هذا النهج أيضًا في أعمال العديد من المؤلفين الآخرين ، على سبيل المثال ، كورديلا وآخرون. [2] (خوارزمية VF2) ، بونتسي وآخرون. [1] (خوارزمية RI) ، إلخ.

باختصار ، جوهر هذا النهج هو "ذكي تعداد "المراسلات المحتملة لرؤوس عينة الرسم البياني B والرسم البياني A الذي يتم البحث فيه. هذا البحث يجعل من "الذكي" إدخال شروط وقيود مختلفة تسمح لك بقطع الخيارات غير المناسبة في أقرب وقت ممكن. أيضًا ، لهذه الأغراض ، يمكن إجراء معالجة أولية مختلفة لبيانات المصدر.

لن نشارك في إعادة سرد هذه الأعمال هنا ، ولكننا سندعو القارئ للتعرف عليها بشكل مستقل. ومع ذلك ، "العرض أفضل من الطلب" ، وتجدر الإشارة إلى أن هناك أمثلة بيانية جيدة وتفسيرات لهذه الخوارزميات على الويب. انظر ، على سبيل المثال ، ما يلي:
coderoad.ru/17480142/Is-or-simple-example-for-explanation-algorithm-Ulman - شرح جيد جدًا وواضح بمثال ،
problem.life/questions/8176298 - خطوات خوارزمية VF2 مع مثال .

ومع ذلك ، يطرح السؤال - هل هناك أي طرق ونهج ممكنة أخرى لحل هذه المشكلة ، وإن كان ذلك لبعض الحالات الخاصة؟ وأود أن أقدم لكم أحد الإجابات المحتملة لهذا السؤال.

2. تماثل الرسوم البيانية ومسارات ملحوظة


دعنا نتفق على الفور: تحت NB-paths (وليس من اللغة الإنجليزية ، ولكن ببساطة لأنها أقصر من ذلك بكثير) سنستدعي المسارات غير المتفرعة القصوى ، أي المسارات الطويلة غير المتفرعة إلى أقصى حد لبعض الرسوم البيانية.

لذلك ، إذا كان لدينا رسمان بيانيان متماثلان لبعضهما البعض ، فعند أي تمثيل للرسم البياني الأول كتسلسل من المسارات غير المتفرعة الممتدة إلى أقصى حد (أي ، مسارات NB الخاصة بنا) ، يوجد دائمًا نفس التمثيل للرسم البياني الثاني المقابل له ، وفي هذه الحالة

  • بالنسبة إلى الرسوم البيانية الموجهة ، سيتم محاذاة المسارات المقابلة لبعضها البعض ،
  • درجات القمم المقابلة لبعضها البعض للرسومات البيانية غير الموجهة (وللرسوم البيانية الموجهة ، أعداد الحواف الواردة والصادرة ، على التوالي) ستكون مساوية لـ
  • عند "دمج" مثل هذه التمثيلات نتيجة لذلك ، سيكون لدينا مراسلات من قمم الرسوم البيانية الأولى والثانية.

مثال . الرسم البياني A = {1-> 2، 1-> 6، 4-> 5، 5-> 1، 3-> 3}. الرسم البياني B = {3-> 4، 3-> 5، 1-> 2، 2-> 3، 6-> 6}
PathsA ( القصوى غير المتفرعة-مسارات A ): 1-> 2، 1-> 6، 4-> 5-> 1 ، 3-> 3 مسارات B
( أقصى المسارات غير المتفرعة من B ): 3-> 4 ، 3-> 5 ، 1-> 2-> 3 ، 6-> 6 مطابقة الرأس
: 1 ( أ): 3 (ب) ، 2 (أ): 4 (ب) ، 6 (أ): 5 (ب) ، 4 (أ): 1 (ب) ، 5 (أ): 2 (ب) ، 3 ( أ): 6 (ب).

وبالتالي ، يمكن حل مهمة التحقق من تماثل رسمين بيانيين من خلال إيجاد مثل هذه المسارات المقابلة لبعضها البعض ثم التحقق من مساواة مصفوفات الجوار التي تم إنشاؤها بناءً على حفظها لترتيب الذروات في تسلسل المسار الذي تم الحصول عليه (تتم إضافة كل قمة إلى التسلسل مرة واحدة ، "ذكر" الأول). في مثالنا ، سيتم استخدام أوامر القمة التالية لإنشاء مصفوفات مجاورة:

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

مصفوفة المجاورة لـ A لترتيب معين من القمم:

صورة

مصفوفة المجاورة بالنسبة لـ B لترتيب معين من القمم:

صورة

المصفوفات متساوية ؛ وبالتالي ، فإن الرسوم البيانية A و B متشابهة.

علاوة على ذلك ، فإن هذا النهج (1) ينطبق على كل من الرسوم البيانية الموجهة وغير الموجهة ، (2) ينطبق على الرسوم البيانية التي تحتوي على أكثر من مكون متصل / اتصال قوي ، (3) ينطبق على الرسوم البيانية التي تحتوي على حواف وحلقات (متعددة) متعددة ، ومع ذلك (4) لا تأخذ في الاعتبار الذروات التي لا يوجد لها حواف بها.

3. حسنًا ، تحقق من تماثل الرسوم البيانية. ولكن ماذا عن البحث عن الرسوم البيانية الفرعية؟


وهنا ، بصراحة ، كل شيء أكثر تعقيدًا. هنا سيكون لدينا التقييد التالي: بناءً على جوهر الطريقة ، لا يمكنك العثور على أي منها ، ولكن فقط الرسوم البيانية الفرعية "المسجلة" . و سنطالب "المدرج" رسم بياني ثانوي من الرسم البياني وهذا رسم بياني ثانوي يمكن أن يكون "لصقها" إلى أجزاء أخرى من الرسم البياني A فقط بسبب الحادث الحواف فقط إلى القمم حدود له من (رسم بياني ثانوي) غير المتفرعة مسارات الحد الأقصى لطول (علاوة على ذلك، يمكن أن تحتوي على الرسم البياني ل مكونات أخرى متصلة). لا تقلق ، سيكون أدناه مثالًا ، وسيكون كل شيء أكثر وضوحًا.

بالإضافة إلى ذلك ، عند حل هذه المشكلة ، بالإضافة إلى العثور على مراسلات مسارات NB للرسم البياني A و B في الطول (كما كان الحال مع التحقق من التماثل الذي نوقش أعلاه) ، من الضروري أيضًا البحث بشكل منفصل عن المراسلات المحتملة التالية بينهما:

  • مطابقة مسارات NB - سلاسل بسيطة من الرسم البياني B إلى مسارات NB - سلاسل بسيطة / دورات بسيطة من الرسم البياني A. علاوة على ذلك ، في البداية يمكن أن تكون هذه المسارات في الرسم البياني A أطول - في هذه الحالة ، يتم أخذ مقاطعها التي تكون متساوية في الطول إلى المسار المطلوب من B.
  • مراسلة NB- المسارات "النهائية" للرسم البياني B إلى أي مسارات ملحوظة للرسم البياني A (في هذه الحالة ، يمكن أن تكون المسارات من الرسم البياني A أطول أيضًا - في هذه الحالة ، يتم أخذ مقاطعها التي تكون متساوية في الطول للمسار المطلوب من الرسم البياني B).

دعونا نلقي نظرة على مثال:

صورة

عند البحث عن مخطط فرعي متماثل "منقوش" للرسم البياني B في العمود A (انظر الشكل أعلاه) ، سيتم العثور على المراسلات التالية:

  • المسار الداخلي 2-> 3-> 4 من العمود B: المسار الداخلي 2-> 3-> 4 من العمود A ،
  • المسارات النهائية 1-> 2 و 10-> 2 من الرسم البياني B: مسار النهاية 0-> 2 من الرسم البياني A وجزء من مسار النهاية 7-> 1-> 2 من الرسم البياني A ، أي 1-> 2 ،
  • 7->8 B: 9->10->11 A, 9->10 10->11, 12->13->14->12 A, 12->13, 13->14, 14->12.

وبالتالي ، بصفتها الرسوم البيانية الفرعية "المدرجة" في الرسم البياني أ والتي تكون متماثلة في الرسم البياني ب ، يمكن العثور على الخيارات الخمسة التالية:

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 أعمدة ب لن يتم العثور عليها.

4. الآن الخوارزمية نفسها


يمكننا الآن الانتقال إلى دراسة أكثر تفصيلاً لخوارزمية البحث للرسومات الفرعية "المنقوشة" في العمود A المتشابهة في العمود B.

لذلك ، ستتكون الخوارزمية من 4 مراحل:

  • المعالجة المسبقة
  • المطابقة
  • رقيق،
  • استنتاج

المرحلة الأولى


في هذه المرحلة ، نجد جميع مسارات NB لكل من الرسوم البيانية ، وكذلك تقييم العوامل التي تحد من مساحة الاختيار أثناء التعداد. أولئك. نقوم بما يلي:

  1. نجد جميع مسارات NB في العمود A ونضعها في مصفوفة ديناميكية (في C ++ - في متجه) PathsA
  2. نجد جميع مسارات NB في العمود B ونضعها في صفيف ديناميكي (ناقل) PathB
  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.

المرحلة الثانية. رسم الخرائط


في هذه المرحلة ، سنحدد مسارات NB المرشحة (المشار إليها فيما يلي ببساطة باسم "المسارات المرشحة") من العمود A لكل مسار من المسارات الملحوظة في العمود B. تمييز كل مسار مرشح من PathsA لكل مسار Iith PathsB [i ] سيتم كتابتها إلى مصفوفة ديناميكية ثنائية الأبعاد (في C ++ - إلى متجه للمتجهات) NPaths - على التوالي للمتجه i-th (الخط i-th) - في شكل ثلاثي مرتبة من الأرقام: رقم المسار المقابل في PathAA - عدد موضع البداية فيه - طول المسار .

على سبيل المثال ، PathsB [2] = {1، 0، 3، 3، 1، 3} يعني أن المسارات PathsB [2] مرتبطة بمسارين مرشحين من A: من PathsA [1] - أول 3 عناصر مسار تبدأ من الصفر ( الأولي) ، ومن PathsA [3] - أيضًا 3 عناصر تبدأ من الأول (بجوار الأول).

في نفس الوقت ، سنبحث عن (اختر) المسارات المرشحة في 4 اتجاهات:

  1. ابحث عن المسارات المرشحة لجميع مسارات NB الداخلية للرسم البياني B من PathsB ، أي أولئك الذين ترتبط كلتا القمتين الحدوديتين في الرسم البياني ب مع رأسين آخرين على الأقل (بغض النظر عن اتجاه مثل هذا الاتصال) وفي نفس الوقت هذا المسار ليس دورة بسيطة (موجهة - للرسوم البيانية الموجهة).
  2. البحث عن مسارات مرشحة لتتبع مسارات ملحوظة ملحوظة من PathsB.
  3. البحث عن المسارات المرشحة لمسارات ملحوظة - حلقات بسيطة من PathsB.
  4. ابحث عن المسارات المرشحة لمسارات ملحوظة - مسارات بسيطة من PathsB.

عند اختيار المسارات المرشحة لكل مسار إيث من PathsB ، تتم مقارنتها (هذا هو المكان الذي تكون فيه بعض معلمات المحدد المحسوبة مسبقًا مفيدة):

  • طوله وطول المسار المرشح (يجب أن يكون متساويًا في الحالتين 1 و 3 ، وفي الحالتين 2 و 4 يمكن أن يكون المسار المرشح من PathA أيضًا أطول) ،
  • درجات القمم الحدودية والقمم المقابلة للمسار المرشح (بالنسبة للقمم من المسار المرشح ، يجب أن تكون هذه القيم على الأقل المسار من PathB).

إذا لم يتم العثور على مسار مرشح واحد من PathsA ، وفقًا لنتائج المرحلة الثانية ، لأي مسار من المسارات في PathBB ، فيعتبر أن A لا يحتوي على مخططات فرعية "مدرجة" متشابهة للعمود B.

رقيق


الآن دعونا نحاول "ضغط" الرسم البياني أ. نترك فيه فقط تلك الحواف التي دخلت في المسارات المرشحة التي وجدناها. إذا في الوقت نفسه ، فقد الرسم البياني أ حافة واحدة على الأقل مقارنة بالحالة الأولية ، نعود إلى المرحلة الأولى "المعالجة المسبقة": درجات رؤوس الرسم البياني أ ، وبالتالي ، يمكن تقليل قائمة المسارات المرشحة ، وبالتالي ، يمكن تقليل مساحة البحث.

المرحلة الثالثة. ترقق قائمة المسارات المرشحة


الغرض من هذه الخطوة هو القضاء على أكبر عدد ممكن من المرشحين غير المناسب. للقيام بذلك ، نقوم بتنفيذ الخطوات التالية.

  1. استبعاد المسارات المرشحة غير الملائمة بشكل واضح استنادًا إلى الحد الأدنى للمسافات بين الذروات في العمود B. المسار المرشح لكل PathBB [i] والتي تم العثور على مسار واحد على الأقل [j] لم يتم العثور على مسار مرشح لأقصر كانت المسافة بين رؤوس حدودها في الرسم البياني A أقل أو تساوي أقصر مسافة بين رؤوس الحدود المقابلة للمسيرات PathsB [i] و PathsB [j] من الرسم البياني B.
  2. استثناء لجميع الدورات من PathsB إلى المسارات المرشحة غير الدورية المرتبطة به والعكس بالعكس.
  3. استثناء المسارات المرشحة المشابهة للقسم 1 ، ولكن ليس بمعيار أقصر مسافة بين رؤوس الحدود ، ولكن من خلال (رؤوس الحدود) إلى المساواة أو عدم المساواة المتبادلين.

على سبيل المثال ، إذا:

  • عنصر البداية لـ PathsB [i] لا يساوي عنصر البداية لـ PathsB [j] و
  • العنصر الأخير من PathsB [i] لا يساوي العنصر النهائي من PathsB [j] و
  • عنصر البداية لـ PathsB [i] يساوي عنصر النهاية لـ PathsB [j] و
  • عنصر البداية لـ PathsB [j] لا يساوي عنصر النهاية لـ PathsB [i] ،

المسار المرشح على طول المسار PathsB [i] الذي لم يعثر فيه على الأقل PathsB [j] على أي مسارات مرشحة تستوفي الشرط أعلاه فيما يتعلق بالمساواة / عدم المساواة في (المسارات المرشحة) الأولية والنهائية القمم.

أي ، تقريبًا ، نرمي تلك المسارات المرشحة التي من الواضح أنها لن يتم تضمينها في المخططات الفرعية المرغوبة - استنادًا إلى المسافة إلى جميع المسارات المرشحة الأخرى (هذه المسارات بعيدة جدًا عن جميع المسارات الأخرى) ، استنادًا إلى دورتهم الدورية / غير الدورية ، و تستند أيضًا إلى المساواة / عدم المساواة الواجبة في القمم الحدودية مع القمم الحدودية للمسارات المرشحة الأخرى.

إذا تم ، وفقًا لنتائج المرحلة الثالثة ، حذف مسار مرشح واحد على الأقل من PathsA ، ثم - مرة أخرى - يتم تحديث العمود A - تبقى فقط الحواف المضمنة في المسارات المرشحة المتبقية فيه. ومرة أخرى ، إذا ، في نفس الوقت ، الرسم البياني A "فقدان الوزن" بحافة واحدة على الأقل ، نعود مرة أخرى إلى المرحلة الأولى "المعالجة المسبقة": درجات رؤوس الرسم البياني A ، وبالتالي ، يمكن تقليل قائمة المسارات المرشحة ، وبالتالي يمكن تقليلها مساحة البحث.

المرحلة الرابعة. استنتاج


تحدد كل مجموعة ممكنة من جميع المسارات المرشحة المتبقية مخططًا فرعيًا للعمود A. لكل مخطط فرعي ، يتم إنشاء مصفوفة مجاورة مع مراعاة ترتيب المسارات المرشحة بنفس الطريقة التي تم بها إنشاء مصفوفة المجاورة B00 للرسم البياني B ، ثم تتم مقارنة مصفوفات المجاورة.

إذا كانت متساوية ، يتم مقارنة تعدد الحواف (انظر القسم 3 من المعالجة الأولية للمرحلة الأولى). إذا تم استيفاء جميع هذه الشروط ، يُعتبر الرسم الفرعي الموجود متماثلًا في الرسم البياني B ويضاف إلى مجموعة النتائج التي تم العثور عليها.

خلال المرحلة الرابعة "الخاتمة" ، يمكن استخدام العديد من الفحوصات الإضافية لتسريع تحديد ورسم مخطط فرعي غير مناسب.

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 } و ب = {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}. مهمتنا أن نجد في الرسم البياني أ جميع الرسومات الفرعية "المنقوشة" متشابهة إلى الرسم البياني ب. والنتيجة تظهر أيضًا في الشكل: يتم تمييز القمم والحواف الموجودة في الرسم البياني أ بخط سميك ، ويتم الإشارة إلى أرقام القمم المقابلة للرسم البياني ب بين قوسين (إذا كان هناك العديد من الخيارات ، يتم الإشارة إليها من خلال جزء).

صورة

عند حل مشكلة البحث في العمود A من المخططات الفرعية "المنقوشة" المتشابهة للعمود B ،لدينا النتائج التالية من الخوارزمية.

المرحلة الأولى: تم تنفيذ جميع الإجراءات والحسابات وفقا ل p.p. 1-5 من هذه الخطوة ، فيما يلي PathSA الناتجة و PathsB.

المسارات أ:

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

المسارات B:

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 ، وتم اختصار PathsA من خلال نتائج التخفيف الأولي. في مرحلة الترقق الرئيسي (III) ، لم يحدث انخفاض إضافي في PathA. ونتيجة لذلك ، اتخذ 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

المسارات B:

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] تحدد المسار المرشح المناسب لـ PathsB [i] من A بالتنسيق: رقم المسار المقابل من PathsA - موضع بداية المقطع من هذا المسار - طول المقطع. وبالتالي ، من السهل التحقق من أن المسار B [0] = {1-> 1} (i = 0: 3 0 2) يتوافق مع المسار الوحيد من A ، أي الجزء من PathsA [3] ، بدءًا من البداية ويبلغ طوله 2.

المرحلة الرابعة. ونتيجة لذلك ، تم العثور على رسم فرعي فريد A1 في العمود A ، مشابه لـ B. A1 = {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. عندما يتم تقديم ميزات إضافية لرؤوس العمودين A و B (على سبيل المثال ، عندما يتم تحديد المركبات بواسطة الرسوم البيانية للمركبات الكيميائية ، يمكن ربط رمز رقمي يتوافق مع ذرة واحدة فقط (نظير) مع كل قمة) ، يمكن تسريع عملية البحث بسبب زيادة دقة المقارنات وفقًا للمرحلة الثانية: إضافية سيكون شرط اختيار المسارات المرشحة هو مراسلات تسميات قمة الرأس.
  2. . , «», «» - B.
  3. , , , «» :
    (1) «» , ,
    (2) .
    «» « - », , , .
  4. , - , .


معلومات عامة حول المشاكل:
1. بونيسي ، ف. ، جويجنو ، ر. ، بولفيرينتي ، أ. وآخرون. خوارزمية تشابه ثانوية تحت الرسم وتطبيقها على البيانات البيوكيميائية. BMC Bioinformatics 14 ، S13 (2013). doi.org/10.1186/1471-2105-14-S7-S13 .
2. Cordella L ، Foggia P ، Sansone C ، Vento M: A (Sub) Graph Isomorphism Algorithm لمطابقة الرسوم البيانية الكبيرة. معاملات IEEE على تحليل الأنماط وذكاء الآلة. 2004 ، 26 (10): 1367-1372. 10.1109 / TPAMI.2004.75.
3. أولمان جوليان ر.: خوارزمية ل Subgraph Isomorphism. مجلة جمعية الحاسبات الآلية. 1976 ، 23: 31-42. 10.1145 / 321921.321925.
4. أولمان جوليان ر.: خوارزميات متجه البت لإرضاء القيود الثنائية والتشكل الثانوي. خوارزميات J Exp. 2011 ، 15 (1.6): 1.1-1.6. 1.64

إن الكتابة التمهيدية للمؤلف المكتوبة بلغة أكثر رسمية حول هذا هو أكثر "خوارزمية تستند إلى مسارات NB" ، والتي تحتوي أيضًا على معلومات حول محاولة تنفيذها في C ++:
5. Chernoukhov SA 2020. طبعات. التحقق من تشابه رسمين بيانيين والبحث عن مخططات فرعية "منقوشة" متشابهة: نهج قائم على تحليل نهج المسارات غير المتفرعة إلى أقصى حد لحل مشكلة تشكل الرسم البياني (الفرعي). DOI: dx.doi.org/10.24108/preprints-3111977

مصادر إنترنت مفيدة حول هذا الموضوع:
6. coderoad.ru/17480142/Is-li- simple-example-for -شرح- algorithm-Ulman
7. issue.life/questions / 8176298 .

More articles:


All Articles