مشكلة تماثل الرسوم البيانية الفرعية

في علم الحاسوب النظري ، تُعد مشكلة تماثل الرسم البياني الجزئي مهمة حسابية يتم فيها تحويل رسمين بيانيين${\displaystyle G}$و${\displaystyle H}$يتم تقديمها كمدخلات، ويجب على المرء تحديد ما إذا كان${\displaystyle G}$يحتوي على رسم بياني فرعي متماثل مع${\displaystyle H}$يُعدّ تماثل الرسوم البيانية الجزئية تعميمًا لكلٍّ من مسألة الزمرة القصوى ومسألة اختبار ما إذا كان الرسم البياني يحتوي على دورة هاميلتونية ، ولذلك فهو مسألة كاملة من فئة NP . ^{[ 1 ]} مع ذلك، يمكن حلّ بعض الحالات الأخرى لتماثل الرسوم البيانية الجزئية في وقت متعدد الحدود. ^{[ 2 ]}

أحيانًا يُستخدم مصطلح " مطابقة الرسم البياني الفرعي" لنفس المشكلة. ويركز هذا المصطلح على إيجاد هذا الرسم البياني الفرعي بدلاً من مجرد مشكلة اتخاذ القرار.

لإثبات أن تماثل الرسوم البيانية الجزئية مسألة NP-كاملة، يجب صياغتها كمسألة قرار . المدخل لمسألة القرار هو زوج من الرسوم البيانية${\displaystyle G}$و H. تكون الإجابة على المسألة موجبة إذا كان H متماثلًا مع رسم بياني جزئي من G ، وسالبة خلاف ذلك.

سؤال رسمي:

يترك${\displaystyle G=(V,E)}$،${\displaystyle H=(V^{\prime },E^{\prime })}$لنفترض وجود رسوم بيانية. هل يوجد رسم بياني فرعي؟${\displaystyle G_{0}=(V_{0},E_{0})\mid V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})}$بحيث${\displaystyle G_{0}\cong H}$أي، هل يوجد تقابل؟${\displaystyle f\colon V_{0}\rightarrow V^{\prime }}$بحيث${\displaystyle \{\,v_{1},v_{2}\,\}\in E_{0}\iff \{\,f(v_{1}),f(v_{2})\,\}\in E^{\prime }}$؟

برهان كون مسألة تماثل الرسوم البيانية الجزئية مسألةً كاملةً من فئة NP بسيط، ويعتمد على اختزال مسألة الزمر ، وهي مسألة قرار كاملة من فئة NP يكون مُدخلها رسمًا بيانيًا واحدًا G وعددًا k ، والسؤال هو ما إذا كان G يحتوي على رسم بياني جزئي كامل ذي k رأسًا. ولترجمة هذا إلى مسألة تماثل الرسوم البيانية الجزئية، نفرض أن H هو الرسم البياني الكامل K = _k ؛ عندئذٍ يكون جواب مسألة تماثل الرسوم البيانية الجزئية لـ G و H مساويًا لجواب مسألة الزمر لـ G و k . وبما أن مسألة الزمر كاملة من فئة NP، فإن هذا الاختزال متعدد الحدود ذو العدد الواحد يُظهر أن مسألة تماثل الرسوم البيانية الجزئية كاملة أيضًا من فئة NP. ^{[ 3 ]}

يُحوّل اختزال بديل لمسألة دورة هاميلتون الرسم البياني G المراد اختباره من حيث خاصية الهاميلتونية إلى زوج من الرسوم البيانية G و H ، حيث H دورة لها نفس عدد رؤوس G. ولأن مسألة دورة هاميلتون هي مسألة NP-كاملة حتى بالنسبة للرسوم البيانية المستوية ، فإن هذا يُظهر أن مسألة تماثل الرسوم البيانية الجزئية تظل مسألة NP-كاملة حتى في الحالة المستوية. ^{[ 4 ]}

يُعدّ تماثل الرسوم البيانية الجزئية تعميمًا لمسألة تماثل الرسوم البيانية ، التي تسأل عما إذا كان G متماثلًا مع H : تكون إجابة مسألة تماثل الرسوم البيانية صحيحة إذا وفقط إذا كان لكل من G و H نفس عدد الرؤوس والحواف، وتكون مسألة تماثل الرسوم البيانية الجزئية لـ G و H صحيحة. مع ذلك، يبقى الوضع النظري لتماثل الرسوم البيانية من منظور نظرية التعقيد سؤالًا مفتوحًا.

في سياق حدسية أنديرا-كارب-روزنبرغ حول تعقيد الاستعلام لخصائص الرسم البياني الرتيب، أظهر غروغر (1992) أن أي مسألة تماثل الرسم البياني الجزئي لها تعقيد استعلام Ω( n³ ^{/² )؛ أي أن حل مسألة تماثل الرسم البياني الجزئي يتطلب خوارزمية للتحقق من وجود أو عدم وجود Ω(} n³ ^/² ) من الحواف المختلفة في الرسم البياني في المدخلات . ^{[ 5 ]}

يصف أولمان (1976) إجراءً تراجعيًا متكررًا لحل مشكلة تماثل الرسوم البيانية الجزئية. على الرغم من أن زمن تشغيله، بشكل عام، أُسّي، إلا أنه يستغرق زمنًا متعدد الحدود لأي اختيار ثابت لـ H (مع متعدد حدود يعتمد على اختيار H ). عندما يكون G رسمًا بيانيًا مستويًا (أو بشكل أعم رسمًا بيانيًا ذا توسع محدود ) و H ثابتًا، يمكن تقليل زمن تشغيل تماثل الرسوم البيانية الجزئية إلى زمن خطي . ^{[ 2 ]}

يُعدّ بحث أولمان (2010) تحديثًا جوهريًا لورقة بحثية حول خوارزمية تماثل الرسوم البيانية الفرعية لعام 1976.

اقترح كورديلا (2004) في عام 2004 خوارزمية أخرى تعتمد على خوارزمية أولمان، VF2، والتي تعمل على تحسين عملية التحسين باستخدام طرق استدلالية مختلفة وتستخدم ذاكرة أقل بكثير.

اقترح بونيتشي وجيوجنو (2013) ^{[ 6 ] [ 7 ]} خوارزمية أفضل تعمل على تحسين الترتيب الأولي للرؤوس باستخدام بعض الطرق الاستدلالية.

يُعدّ برنامج Glasgow Subgraph Solver ( McCreesh, Prosser & Trimble (2020) ) أحدثَ برنامجٍ لحلّ المسائل المعقدة متوسطة الحجم . ^{[ 8 ]} يعتمد هذا البرنامج على منهجية البرمجة المقيدة ، مستخدمًا هياكل بيانات متوازية البتات وخوارزميات نشر متخصصة لتحسين الأداء. وهو يدعم معظم الصيغ الشائعة للمسألة، وقادر على عدّ الحلول أو تعدادها، بالإضافة إلى تحديد ما إذا كان هناك حلٌّ من عدمه.

بالنسبة للرسوم البيانية الكبيرة، تشمل أحدث الخوارزميات CFL-Match و Turboiso، والامتدادات عليها مثل DAF بواسطة Han et al. (2019) .

استنادًا إلى المناهج القائمة على البرمجة المقيدة ومنهجية DAF، قدم ArcMatch ^{[ 9 ]} تقنية اختزال تعمل على مسارات ما يسمى "الرسم البياني للمجال"، وهو هيكل بيانات يتكون من رؤوس وحواف المجالات.

نظرًا لتطبيق تماثل الرسوم البيانية الفرعية في مجال المعلوماتية الكيميائية لإيجاد أوجه التشابه بين المركبات الكيميائية انطلاقًا من صيغها البنائية ، يُستخدم مصطلح " البحث عن البنية الفرعية" في هذا المجال. ^{[ 10 ]} غالبًا ما تُعرَّف بنية الاستعلام بيانيًا باستخدام برنامج تحرير البنية ؛ وتُعرِّف أنظمة قواعد البيانات القائمة على SMILES الاستعلامات عادةً باستخدام SMARTS ، وهو امتداد لـ SMILES .

تم تطبيق المشكلة ذات الصلة الوثيقة المتمثلة في حساب عدد النسخ المتماثلة من الرسم البياني H في رسم بياني أكبر G على اكتشاف الأنماط في قواعد البيانات، ^{[ 11 ]} والمعلوماتية الحيوية لشبكات تفاعل البروتين-البروتين، ^{[ 12 ]} وفي طرق الرسم البياني العشوائي الأسي للنمذجة الرياضية للشبكات الاجتماعية . ^{[ 13 ]}

يصف أولريش وآخرون (1993) تطبيقًا لتماثل الرسوم البيانية الجزئية في التصميم بمساعدة الحاسوب للدوائر الإلكترونية . كما أن مطابقة الرسوم البيانية الجزئية هي خطوة فرعية في إعادة كتابة الرسوم البيانية (وهي الأكثر استهلاكًا لوقت التشغيل)، وبالتالي توفرها أدوات إعادة كتابة الرسوم البيانية .

تُعدّ هذه المشكلة ذات أهمية أيضاً في مجال الذكاء الاصطناعي ، حيث تُعتبر جزءاً من مجموعة مسائل مطابقة الأنماط في الرسوم البيانية؛ كما أن امتداداً لتماثل الرسوم البيانية الجزئية يُعرف باسم استخراج البيانات من الرسوم البيانية يحظى باهتمام في هذا المجال. ^{[ 14 ]}

• استخراج الأشجار الفرعية المتكررة
• مشكلة تماثل الرسم البياني الفرعي المستحث
• مشكلة الرسم البياني الفرعي للحافة المشتركة القصوى
• مشكلة تماثل الرسم البياني الفرعي المشترك الأقصى

• كوك، إس. أ. (1971)، "تعقيد إجراءات إثبات النظريات" ، وقائع الندوة الثالثة لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 151-158 ، doi : 10.1145/800157.805047 ، S2CID 7573663  .
• إبستين، ديفيد (1999)، "تماثل الرسوم البيانية الجزئية في الرسوم البيانية المستوية والمشاكل ذات الصلة" (ملف PDF) ، مجلة خوارزميات وتطبيقات الرسوم البيانية ، 3 (3): 1-27 ، arXiv : cs.DS/9911003 ، doi : 10.7155/jgaa.00014 ، S2CID 2303110 .
• غاري، مايكل ر.؛ جونسون ، ديفيد س. (1979)، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ISBN 978-0-7167-1045-5. A1.4: GT48، صفحة 202.
• غروغر، هانز ديتمار (1992)، "حول التعقيد العشوائي لخصائص الرسم البياني الرتيب" (ملف PDF) ، مجلة أكتا سايبرنيتيكا ، 10 ( 3): 119-127.
• هان، ميونغجي؛ كيم، هيونجون؛ غو، جيونمو؛ بارك، كونسو؛ هان، ووكشين (2019)، مطابقة الرسوم البيانية الفرعية الفعالة: مواءمة البرمجة الديناميكية، وترتيب المطابقة التكيفي، ومجموعة الفشل معًا ، doi : 10.1145/3299869.3319880 ، S2CID 195259296 
• كوراموتشي، ميتشيهيرو؛ كاريبس، جورج (2001)، "اكتشاف الرسوم البيانية الفرعية المتكررة"، المؤتمر الدولي الأول لمعهد مهندسي الكهرباء والإلكترونيات حول استخراج البيانات ، ص  313، CiteSeerX 10.1.1.22.4992 ، doi : 10.1109/ICDM.2001.989534 ، ISBN  978-0-7695-1119-1، S2CID 8684662 .
• أولريش، مايلز؛ إيبيلينغ، كارل؛ جينتينغ، إيكا؛ ساثر، ليزا (1993)، "ساب جيميني: تحديد الدوائر الفرعية باستخدام خوارزمية سريعة لتماثل الرسوم البيانية الفرعية"، وقائع المؤتمر الدولي الثلاثين لأتمتة التصميم ، الصفحات 31-37 ، doi : 10.1145/157485.164556 ، ISBN  978-0-89791-577-9، S2CID 5889119 .
• نيشيتريل، ياروسلاف ؛ أوسونا دي مينديز، باتريس (2012)، "18.3 مشكلة تماثل الرسوم البيانية الفرعية والاستعلامات المنطقية"، التناثر: الرسوم البيانية، والهياكل، والخوارزميات ، الخوارزميات والتوافقية، المجلد  28، سبرينغر، الصفحات 400-401 ، doi : 10.1007/978-3-642-27875-4 ، ISBN  978-3-642-27874-7MR 2920058​ .
• برزولج، ن.؛ كورنيل، د.ج .؛ جوريسيكا، إ. (2006)، "التقدير الفعال لتوزيعات ترددات الجرافيت في شبكات تفاعل البروتين-البروتين"، المعلوماتية الحيوية ، 22 (8): 974-980 ، doi : 10.1093/bioinformatics/btl030 ، PMID 16452112 .
• سنايدرز، تي إيه بي؛ باتيسون، بي إي؛ روبينز، جي؛ هاندكوك، إم إس (2006)، "مواصفات جديدة لنماذج الرسوم البيانية العشوائية الأسية"، منهجية علم الاجتماع ، 36 (1): 99-153 ، CiteSeerX 10.1.1.62.7975 ، doi : 10.1111/j.1467-9531.2006.00176.x ، S2CID 10800726  .
• أولمان، جوليان ر. (1976)، "خوارزمية لتماثل الرسوم البيانية الفرعية"، مجلة ACM ، 23 (1): 31-42 ، doi : 10.1145/321921.321925 ، S2CID 17268751 .
• جميل، حسن (2011)، "حساب استعلامات متماثلة للرسوم البيانية الفرعية باستخدام التوحيد الهيكلي وهياكل الرسوم البيانية الدنيا"، الندوة السادسة والعشرون لجمعية الحوسبة الآلية حول الحوسبة التطبيقية ، الصفحات 1058-1063 .
• أولمان، جوليان ر. (2010)، "خوارزميات المتجهات الثنائية لتحقيق إرضاء القيود الثنائية وتماثل الرسوم البيانية الفرعية"، مجلة الخوارزميات التجريبية ، 15 : 1.1، CiteSeerX 10.1.1.681.8766 ، doi : 10.1145/1671970.1921702 ، S2CID 15021184  .
• كورديلا، لويجي ب. (2004)، "خوارزمية تماثل (فرعي) للرسوم البيانية لمطابقة الرسوم البيانية الكبيرة"، معاملات IEEE في تحليل الأنماط والذكاء الآلي ، 26 (10): 1367-1372 ، Bibcode : 2004ITPAM..26.1367C ، CiteSeerX 10.1.1.101.5342 ، doi : 10.1109/tpami.2004.75 ، PMID 15641723 ، S2CID 833657   
• بونيتشي، ف.؛ جيونو، ر. (2013)، "خوارزمية تماثل الرسوم البيانية الفرعية وتطبيقها على البيانات البيوكيميائية"، BMC Bioinformatics ، 14 (ملحق 7): S13، doi : 10.1186/1471-2105-14-s7-s13 ، PMC 3633016 ، PMID 23815292  
• كارليتي، ف.؛ فوجيا، ب.؛ ساجيس، أ.؛ فينتو، م. (2018)، "تحدي التعقيد الزمني لتماثل الرسوم البيانية الجزئية التام للرسوم البيانية الضخمة والكثيفة باستخدام VF3"، معاملات IEEE في تحليل الأنماط والذكاء الآلي ، 40 (4): 804-818 ، Bibcode : 2018ITPAM..40..804C ، doi : 10.1109/TPAMI.2017.2696940 ، PMID 28436848 ، S2CID 3709576  
• سولنون، ​​كريستين (2019)، "التقييم التجريبي لحلول تماثل الرسوم البيانية الفرعية" ، تمثيلات الرسوم البيانية في التعرف على الأنماط - ورشة العمل الدولية الثانية عشرة IAPR-TC-15، GbRPR 2019، تور، فرنسا، 19-21 يونيو 2019، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد  11510، سبرينغر، الصفحات 1-13 ، doi : 10.1007/978-3-030-20081-7_1 ، ISBN  978-3-030-20080-0، S2CID 128270779 
• مكريش، كياران؛ بروسر، باتريك؛ تريمبل، جيمس (2020)، "حلّ مشكلة غلاسكو للرسوم البيانية الفرعية: استخدام البرمجة المقيدة لمعالجة متغيرات مشكلة تماثل الرسوم البيانية الفرعية الصعبة"، تحويل الرسوم البيانية - المؤتمر الدولي الثالث عشر، ICGT 2020، الذي عُقد كجزء من STAF 2020، بيرغن، النرويج، 25-26 يونيو 2020، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد  12150، سبرينغر، الصفحات 316-324 ، doi : 10.1007/978-3-030-51372-6_19 ، ISBN  978-3-030-51371-9PMC 7314700​ 
• بونيتشي، ف.، غراسو، ر.، ميكالي، ج . وآخرون. ArcMatch : مطابقة الرسوم البيانية الفرعية عالية الأداء للرسوم البيانية المصنفة من خلال استغلال نطاقات الحواف. Data Min Knowl Disc 38 ، 3868-3921 (2024). https://doi.org/10.1007/s10618-024-01061-8