مرجع
آخر الزيارات

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

589 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في الانضباط الرياضي لنظرية البيان، تكون الحافة المطابقة أو المستقلة المحددة في البيان عبارة عن مجموعة من الحواف بدون رؤوس شائعة. تتناول المقالة 5 أقسام، منها «التوصيفات والملاحظات»، «الخصائص» و«1: لمطابقة في الرسوم البيانية العامة».
المحتويات
  1. التوصيفات والملاحظات
  2. الخصائص
  3. 1: لمطابقة في الرسوم البيانية العامة
  4. 2 : التطابق في الرسوم البيانية الثنائية
  5. تعريف

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

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

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

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

((تطبيقات))

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

الخصائص

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

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

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

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

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

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

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

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

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

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

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

تعريف

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.