التطابق المثالي

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

يُطلق على المطابقة المثالية أيضًا اسم 1-factor ؛ راجع تحليل العوامل البيانية للحصول على شرح لهذا المصطلح. في بعض المراجع، يُستخدم مصطلح المطابقة الكاملة .

كل مطابقة مثالية هي مطابقة ذات الحد الأقصى من الكاردينالية ، ولكن العكس ليس صحيحًا. على سبيل المثال، ضع في اعتبارك الرسوم البيانية التالية: ^[1]

في الرسم البياني (ب) يوجد تطابق مثالي (بحجم 3) حيث أن جميع الرؤوس الستة متطابقة؛ في الرسم البياني (أ) و(ج) يوجد تطابق أقصى عدد (بحجم 2) وهو ليس مثاليًا، حيث أن بعض الرؤوس غير متطابقة.

المطابقة المثالية هي أيضًا غطاء حافة بحجم أدنى . إذا كان هناك تطابق مثالي، فإن كلًا من رقم المطابقة ورقم غطاء الحافة يساوي | V | / 2 .

لا يمكن أن يحدث التطابق المثالي إلا عندما يحتوي الرسم البياني على عدد زوجي من الرؤوس. التطابق شبه المثالي هو التطابق الذي لا يوجد فيه سوى رأس واحد فقط غير مطابق. لا يمكن أن يحدث هذا إلا عندما يحتوي الرسم البياني على عدد فردي من الرؤوس، ويجب أن يكون هذا التطابق أقصى حد. في الشكل أعلاه، يوضح الجزء (ج) تطابقًا شبه مثالي. إذا كان هناك تطابق شبه مثالي لكل رأس في الرسم البياني يغفل فقط هذا الرأس، فإن الرسم البياني يسمى أيضًا حرجًا للعامل .

توفر نظرية زواج هول توصيفًا للرسوم البيانية ثنائية الأجزاء التي لها تطابق مثالي.

توفر نظرية توتي توصيفًا للرسوم البيانية التعسفية.

المطابقة المثالية هي رسم بياني فرعي منتظم ممتد بعامل واحد ، أو ما يعرف بعامل واحد . بشكل عام، الرسم البياني الفرعي المنتظم الممتد بعامل k هو عامل k .

أعطى حساني مونفريد وماليك توصيفًا طيفيًا لرسم بياني ليكون له تطابق مثالي على النحو التالي: دع يكون رسمًا بيانيًا على رؤوس زوجية وكن أرقامًا خيالية بحتة مميزة غير صفرية . ثم يكون له تطابق مثالي إذا وفقط إذا كان هناك مصفوفة مائلة متناظرة حقيقية مع رسم بياني وقيم ذاتية . ^[2] لاحظ أن الرسم البياني (البسيط) لمصفوفة مائلة متناظرة أو مائلة متناظرة حقيقية من الدرجة لها رؤوس وحواف تُعطى بواسطة الإدخالات غير الصفرية خارج القطر لـ . ${\displaystyle G}$${\displaystyle n}$${\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{\frac {n}{2}}>0}$${\displaystyle {\frac {n}{2}}}$${\displaystyle G}$ ${\displaystyle A}$${\displaystyle G}$ ${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{\frac {n}{2}}}$${\displaystyle A}$${\displaystyle n}$${\displaystyle n}$${\displaystyle A}$

يمكن تحديد ما إذا كان الرسم البياني يسمح بمطابقة مثالية في وقت متعدد الحدود ، باستخدام أي خوارزمية للعثور على الحد الأقصى لمطابقة الكاردينالية .

ومع ذلك، فإن حساب عدد المطابقات المثالية، حتى في الرسوم البيانية ثنائية الأجزاء ، هو #P-complete . وذلك لأن حساب الدوام لمصفوفة عشوائية 0–1 (مشكلة أخرى #P-complete) هو نفس حساب عدد المطابقات المثالية في الرسم البياني ثنائي الأجزاء الذي يحتوي على المصفوفة المحددة كمصفوفة ثنائية التجاور .

تنص نظرية كاستلين الرائعة على أنه يمكن حساب عدد المطابقات المثالية في الرسم البياني المستوي بدقة في وقت متعدد الحدود عبر خوارزمية FKT .

عدد المطابقات المثالية في الرسم البياني الكامل K _n (مع n زوجي) يتم تحديده بواسطة العامل المزدوج : ^[3]${\displaystyle (n-1)!!}$

يمكن أن يؤدي الرسم البياني الملون بالحواف إلى إحداث عدد من تلوينات الرؤوس (ليس بالضرورة صحيحًا) يساوي عدد المطابقات المثالية، حيث يتم تغطية كل رأس مرة واحدة بالضبط في كل مطابقة. وقد تم التحقيق في هذه الخاصية في الفيزياء الكمومية ^[4] ونظرية التعقيد الحسابي . ^[5]

متعدد السطوح المطابق المثالي للرسم البياني هو متعدد السطوح في R ^|E| حيث يكون كل زاوية عبارة عن متجه سقوط لمطابقة مثالية.

• مطابقة خالية من الحسد
• مطابقة الحد الأقصى لعدد العناصر
• المطابقة المثالية في الرسوم البيانية عالية الدرجة
• نظريات هول للرسوم البيانية الفائقة
• مشكلة المطابقة المثالية الفريدة ^{[6] [7] [8]}