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

للمقارنة بين رسمين بيانيين، انظر مطابقة الرسوم البيانية.^[1]^[2]

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

تعريف

عند الحصول على رسم بياني 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 هو

$\sum _{K\geq 0}^{N}MKX^{k}$

$\sum _{K\geq 0}(-1)^{K}MKX^{-}2K$

التوصيفات والملاحظات

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

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

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

((تطبيقات))

1: لمطابقة في الرسوم البيانية العامة

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

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

2 : التطابق في الرسوم البيانية الثنائية

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

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

انظر أيضا

Dulmage–Mendelsohn decomposition قسم من رؤوس الرسومات البيانية ثنائية الاتجاه إلى مجموعات فرعية بحيث تنتمي كل حافة إلى مطابقة كاملة إذا وفقط إذا كانت نهاياتها تنتمي إلى نفس المجموعة الفرعية

Edge coloring قسم من حواف الرسم البياني في التطابقات

Matching preclusion ، الحد الأدنى لعدد الحواف للحذف لمنع مطابقة مثالية من الموجودة

، مطابقة في الرسم البياني ثنائي اللون ذو الحافة اللونية بدون أي ألوان متكررة Rainbow matching

===