مطابقة الرسوم البيانية

مطابقة الرسوم البيانية هي مشكلة إيجاد تشابه بين الرسوم البيانية . ^{[ 1 ]}

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

تُعرف حالة المطابقة التامة للرسوم البيانية بمشكلة تماثل الرسوم البيانية . ^{[ 1 ]} وتُسمى مشكلة المطابقة التامة لرسم بياني مع جزء من رسم بياني آخر بمشكلة تماثل الرسوم البيانية الجزئية .

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

هناك فئتان من طرق البحث: الأولى تعتمد على تحديد أزواج الرؤوس الممكنة والمستحيلة بين الرسمين البيانيين، والثانية تُصاغ فيها مطابقة الرسوم البيانية كمسألة تحسين . ^{[ 3 ]} تُعدّ مسافة تحرير الرسم البياني أحد مقاييس التشابه المقترحة لمطابقة الرسوم البيانية. ^{[ 4 ] [ 5 ]} يُطلق على فئة الخوارزميات هذه اسم مطابقة الرسوم البيانية المتسامحة مع الأخطاء. ^{[ 5 ]}

• مطابقة السلاسل
• مطابقة الأنماط