المطابقة المستحثة

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

يمكن أيضًا وصف المطابقة المستحثة بأنها مجموعة مستقلة في مربع الرسم البياني الخطي للرسم البياني المعطى. ^{[ 1 ]}

الحد الأدنى لعدد المطابقات المستحثة التي يمكن أن تتحول إليها حواف الرسم البياني${\displaystyle G}$يمكن تقسيمها، ويُطلق على ذلك مؤشرها اللوني القوي ، ويُرمز له بـ${\displaystyle \chi _{s}'(G)}$قياساً على المؤشر اللوني${\displaystyle \chi '(G)}$^{[ 2 ]} وهو يساوي العدد اللوني لمربع الرسم البياني الخطي . تُظهر نظرية بروكس ، عند تطبيقها على مربع الرسم البياني الخطي، أن المؤشر اللوني القوي يكون على الأكثر تربيعيًا بالنسبة للدرجة القصوى للرسم البياني المعطى، ولكن يمكن الحصول على عوامل ثابتة أفضل في الحد التربيعي بطرق أخرى. ^{[ 3 ]}

تتعلق مسألة روزا-سزيميريدي بكثافة الحواف في الرسوم البيانية الثنائية المتوازنة ذات المؤشر اللوني القوي الخطي. وبشكل مكافئ، تتعلق بكثافة فئة مختلفة من الرسوم البيانية، وهي الرسوم البيانية الخطية المحلية التي تكون فيها جوار كل رأس عبارة عن تطابق مستحث. ^{[ 4 ]} لا يمكن لأي من هذين النوعين من الرسوم البيانية أن يحتوي على عدد تربيعي من الحواف، ولكن توجد طرق معروفة لإنشاء رسوم بيانية من هذا النوع بأعداد حواف قريبة من التربيع. ^{[ 5 ]}

إيجاد تطابق مستحث بحجم لا يقل عن${\displaystyle k}$تُعدّ هذه المسألة من مسائل NP-complete (وبالتالي، فإنّ إيجاد تطابق مُستحثّ ذي حجم أقصى يُعدّ من مسائل NP-hard ). يُمكن حلّها في وقت متعدد الحدود في الرسوم البيانية الوترية ، لأنّ مربعات الرسوم البيانية الخطية للرسوم البيانية الوترية هي رسوم بيانية مثالية . ^{[ 6 ]} علاوة على ذلك، يُمكن حلّها في وقت خطي في الرسوم البيانية الوترية . ^{[ 7 ]} ما لم يحدث انهيار غير متوقع في التسلسل الهرمي متعدد الحدود ، لا يُمكن تقريب أكبر تطابق مُستحثّ ضمن أي${\displaystyle n^{1-\varepsilon }}$نسبة التقريب في وقت متعدد الحدود. ^{[ 8 ]}

تُعتبر هذه المشكلة أيضاً من نوع W[1]-hard ، مما يعني أنه حتى إيجاد تطابق مستحث صغير بحجم معين ليس بالأمر السهل.${\displaystyle k}$من غير المرجح أن يكون هناك خوارزمية أسرع بكثير من أسلوب البحث الشامل الذي يعتمد على تجربة كل شيء${\displaystyle k}$^{[ 9 ]} ومع ذلك، تكمن المشكلة في إيجاد${\displaystyle k}$إن مسألة الرؤوس التي يؤدي حذفها إلى تطابق مستحث قابلة للحل باستخدام معلمات ثابتة . ^{[ 10 ]} ويمكن أيضًا حل المسألة بدقة على${\displaystyle n}$الرسوم البيانية ذات الرؤوس في الزمن${\displaystyle O(1.3752^{n})}$مع مساحة أسية، أو في الزمن${\displaystyle O(1.4231^{n})}$مع فضاء متعدد الحدود . ^{[ 11 ]}

• المسار المستحث