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

عند الحصول على رسم بياني 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. ويبين الشكل التالي أمثلة للتطابق الأقصى (أحمر) في ثلاثة رسوم بيانية.

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

[Main article: Matching polynomial 1]

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

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

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

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

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

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

(( تطبيقات ))

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

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

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

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

https://en.wikipedia.org/wiki/Matching_(graph_theory)

https://en.wikipedia.org/wiki/Matching_(graph_theory){{قالب:ويكيبيديا انجليزية}}

في كومنز صور وملفات عن: المطابقة

• بوابة رياضيات
• بوابة علم الحاسوب

1. Matching polynomial - Wikipedia "نسخة مؤرشفة". Archived from the original on 4 يناير 2016. اطلع عليه بتاريخ 16 مارس 2018. الوسيط |CitationClass= تم تجاهله (مساعدة)صيانة CS1: BOT: original-url status unknown (link)