مطابقة (نظرية البيان)

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

 تعريف 
عند الحصول على بيان G = (V، E)، يكون M في G هو مجموعة من الحواف غير المجاورة. أي، لا يوجد حافتان تشتركان في قمة الرأس المشتركة.

تتطابق قمة الرأس (أو التشبع) إذا كانت نقطة نهاية واحدة من الحواف في المطابقة. وإلا فإن قمة الرأس لا مثيل لها.المطابقة القصوى هي M مطابقة من بيان G مع الخاصية أنه إذا أضيفت أي حافة ليست في M إلى M ، فلم تعد مطابقة، أي أن M هو الحد الأقصى إذا لم تكن مجموعة فرعية من أي مطابقة أخرى في البيان G. وبعبارة أخرى،Mالمطابقة القصوى (المعروفة أيضًا باسم المطابقة القصوى للهوية [1]) هي مطابقة تحتوي على أكبر عدد ممكن من الحواف. قد يكون هناك العديد من التطابقات القصوى. إن رقم المطابقة (G) الخاص بالبيان هو حجم الحد الأقصى المطابق. لاحظ أن الحد الأقصى المطابق هو الحد الأقصى، ولكن ليس كل مطابقة قصوى هي المطابقة القصوى. يوضح الشكل التالي أمثلة عن الحد الأقصى من التطابقات في نفس الرسوم البيانية الثلاثة.

 الخصائص 
في أي بيان بدون رؤوس منفصلة، يكون مجموع الرقم المطابق ورقم غطاء الحافة مساوياً لعدد الرؤوس. [3] إذا كان هناك تطابق كامل، فكل من رقم المطابقة ورقم غطاء الحافة هما | V | / 2.

إذا كان A و B هما تطابقان قصوى، إذن | A | ≤ 2 | B | و | ب | ≤ 2 | A |. ولرؤية هذا، لاحظ أن كل حافة في B \ A يمكن أن تكون متاخمة لحرفين على الأكثر في A \ B لأن A مطابقة. علاوةً على ذلك، تكون كل حافة في A \ B متاخمة لحافة في B \ A إلى الحد الأقصى لـ B

من البيان G هو الحد الأقصى إذا كان لكل حافة في G تقاطع غير فارغ مع حافة واحدة على الأقل في M. ويبين الشكل التالي أمثلة للتطابق الأقصى (أحمر) في ثلاثة رسوم بيانية.

((مطابقة كثيرات الحدود))

يطلق على وظيفة توليد عدد المواءمة ك الحافة في بيان متعدد الحدود مطابقة. دعونا G يكون البيان وعضو الكنيست أن يكون عدد المواءمة ك الحافة. واحد متعدد الحدود مطابقة G هو

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

توفر نظرية هول في الزواج توصيفًا للرسومات البيانية التي تحتوي على تطابق تام وتوفر نظرية Tutte توصيفًا للرسوم البيانية العشوائية.

المطابقة المثالية هي عبارة عن بيان فرعي منتظم 1، a.k.a. a 1-factor. بشكل عام، يعد الخط الفرعي

((تطبيقات))

 1: لمطابقة في الرسوم البيانية العامة 
    يتكون هيكل Kekulé لمركب عطري من مطابقة كاملة لهيكله الكربوني، مبينًا مواقع الروابط الثنائية في البنية الكيميائية. تمت تسمية هذه الهياكل على اسم فريدريش أوغست كيكولي فون سترادونيتز، الذي أظهر أن البنزين (من الناحية النظرية، دورة 6-قمة) يمكن إعطاؤه مثل هذا الهيكل. [22]

    مؤشر هوسويا هو عدد من التطابقات غير الفارغة زائد واحد؛ يتم استخدامه في الكيمياء الحسابية والتحقيقات الكيمياء الرياضية للمركبات العضوية.

 2 : التطابق في الرسوم البيانية الثنائية 
    تتمثل مشكلة التخرج في اختيار مجموعة من الفئات الدنيا من متطلبات معينة للتخرج.     تنطوي مشكلة النقل في هيتشكوك على مطابقة ثنائية الاتجاه باعتبارها مشكلة فرعية.

    تنطوي مشكلة تشابه الشجرة الفرعية على مطابقة ثنائية الاتجاه كمشكلة فرعية.

تصنيف:استمثال توافقي
تصنيف:نظريات رياضياتية