مطابقة الرسم البياني
مطابقة الرسم البياني Graph matching هي مشكلة إيجاد تشابه بين الرسوم البيانية.[1]
تُستخدم الرسوم البيانية بشكل شائع لترميز المعلومات الهيكلية في العديد من المجالات، بما في ذلك الرؤية الحاسوبية و تمييز الأنماط، وتعد مطابقة الرسم البياني أداة مهمة في هذه المجالات. [2]في هذه المناطق، يُفترض عموماً أن تكون المقارنة بين الرسم البياني للبيانات و الرسم البياني للنماذج.
تُعرف حالة مطابقة الرسم البياني الدقيق باسم مشكلة تماثل الرسم البياني.[1] تسمى مشكلة المطابقة الدقيقة للرسم البياني بجزء من رسم بياني آخر مشكلة تماثل الرسم البياني الجزئي.
يشير مطابقة الرسم البياني غير الدقيق إلى مشاكل المطابقة عندما تكون المطابقة التامة مستحيلة، على سبيل المثال، عندما يكون عدد الرؤوس في الرسمين البيانيين مختلفين. في هذه الحالة، يلزم البحث عن أفضل تطابق ممكن. على سبيل المثال، في تطبيقات تمييز الصور، تنتج نتائج تقطيع الصور في معالجة الصورة عادةً رسوم بيانية للبيانات مع عدد من القمم أكبر بكثير من بيانات الرسوم البيانية للنموذج المتوقع أن تتطابق معها. في حالة الرسم البياني المنسوب، حتى إذا كانت أرقام الرؤوس والحواف متساوية، فقد تظل المطابقة غير دقيقة فقط. [1]
هناك فئتان من طرق البحث تعتمدان على تحديد الأزواج المحتملة والمستحيلة للرؤوس بين الرسمين البيانيين والطرق التي تصوغ مطابقة الرسم البياني على أنها مشكلة التحسين.[3] مسافة تحرير الرسم البياني هي إحدى مقاييس التشابه المقترحة لمطابقة الرسم البياني.[4][5] تسمى فئة الخوارزميات مطابقة الرسم البياني المتسامحة مع الخطأ.[5]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
انظر أيضاً
المراجع
- ^ أ ب ت Endika Bengoetxea, "Inexact Graph Matching Using Estimation of Distribution Algorithms", Ph. D., 2002, Chapter 2:The graph matching problem (retrieved June 28, 2017)
- ^ Endika Bengoetxea, Ph.D., Abstract
- ^ Graph-Based Methods in Computer Vision: Developments and Applications, p. 58
- ^ Bridging the Gap Between Graph Edit Distance and Kernel Machines, p. 16
- ^ أ ب Horst Bunke, Xiaoyi Jang, "Graph Matching and Similarity", in: Intelligent Systems and Interfaces, pp. 281-304 (2000) DOI:10.1007/978-1-4615-4401-2_10