المطابقة (نظرية الرسوم البيانية)
للمقارنة بين رسمين بيانيين ، انظر مطابقة الرسوم البيانية.
في الانضباط الرياضي لنظرية الرسم البياني ، تكون الحافة المطابقة أو المستقلة المحددة في الرسم البياني عبارة عن مجموعة من الحواف بدون رؤوس شائعة. في بعض التطابقات ، قد تكون جميع الرؤوس حادثة مع بعض حافة المطابقة ، ولكن هذا ليس مطلوبًا ولا يمكن أن يحدث إلا إذا كان عدد الرؤوس حتى. يمكن العثور على العثور على مطابقة في رسم بياني ثنائي المسار كمشكلة تدفق الشبكة
عند الحصول على رسم بياني G = (V، E) ، يكون M في 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 هو
formula_1
formula_2
تنص نظرية كونيغ على أنه في الرسوم البيانية الثنائية ، يكون الحد الأقصى المطابق مساوياً لحجم غطاء الرأس الأدنى. من خلال هذه النتيجة ، قد يتم حل الحد الأدنى من غطاء قمة الرأس ، وأقصى مجموعة مستقلة ، ومشاكل قمة الرأس ذات الحد الأقصى ، في وقت كثير الحدود للرسومات البيانية.
توفر نظرية هول في الزواج توصيفًا للرسومات البيانية التي تحتوي على تطابق تام وتوفر نظرية Tutte توصيفًا للرسوم البيانية العشوائية.
المطابقة المثالية هي عبارة عن مخطط فرعي منتظم 1 ، a.k.a. a 1-factor. بشكل عام ، يعد الخط الفرعي
يتكون هيكل Kekulé لمركب عطري من مطابقة كاملة لهيكله الكربوني ، مبينًا مواقع الروابط الثنائية في البنية الكيميائية. تمت تسمية هذه الهياكل على اسم فريدريش أوغست كيكولي فون سترادونيتز ، الذي أظهر أن البنزين (من الناحية النظرية ، دورة 6-قمة) يمكن إعطاؤه مثل هذا الهيكل. [22]
مؤشر هوسويا هو عدد من التطابقات غير الفارغة زائد واحد ؛ يتم استخدامه في الكيمياء الحسابية والتحقيقات الكيمياء الرياضية للمركبات العضوية.
تتمثل مشكلة التخرج في اختيار مجموعة من الفئات الدنيا من متطلبات معينة للتخرج.     تنطوي مشكلة النقل في هيتشكوك على مطابقة ثنائية الاتجاه باعتبارها مشكلة فرعية.
تنطوي مشكلة تشابه الشجرة الفرعية على مطابقة ثنائية الاتجاه كمشكلة فرعية.
https://en.wikipedia.org/wiki/Dulmage%E2%80%93Mendelsohn_decomposition قسم من رؤوس الرسومات البيانية ثنائية الاتجاه إلى مجموعات فرعية بحيث تنتمي كل حافة إلى مطابقة كاملة إذا وفقط إذا كانت نهاياتها تنتمي إلى نفس المجموعة الفرعية
https://en.wikipedia.org/wiki/Edge_coloring قسم من حواف الرسم البياني في التطابقات
https://en.wikipedia.org/wiki/Matching_preclusion ، الحد الأدنى لعدد الحواف للحذف لمنع مطابقة مثالية من الموجودة
، مطابقة في الرسم البياني ثنائي اللون ذو الحافة اللونية بدون أي ألوان متكررة https://en.wikipedia.org/wiki/Rainbow_matching
https://en.wikipedia.org/wiki/Matching_(graph_theory)
[[:en:Matching (graph theory)|https://en.wikipedia.org/wiki/Matching_(graph_theory)
[[تصنيف:نظريات رياضياتية]]