الحد الأقصى لمطابقة واحد إلى متعدد

Question

يترك $G = (X+Y,E)$ يكون الرسم البياني ثنائي و $ك\جيك 1$ عدد صحيح.أ أقصى $ك$-مطابقة هي مجموعة فرعية من $E$ فيها كل قمة $X$ مجاور على الأكثر $ك$ حواف وكل قمة $ص$ مجاور على الأكثر $1$ حافة.

الحد الأقصى للأصل $ك$يمكن العثور على المطابقة من خلال الخوارزمية التالية:

• يخلق $ك$ نسخ من كل قمة $x\في X$, بحيث تكون كل نسخة مجاورة لجميع جيرانها $x$ في $ص$.
• ابحث عن الحد الأقصى للمطابقة في الرسم البياني الناتج.

تعقيد وقت التشغيل للرسم البياني مع $ن$ القمم و $م$ الحواف باستخدام خوارزمية Hopcroft-Karp $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.

أنا مهتم بالخوارزمية البديلة التالية:

• يكرر $ك$ مرات:

  • ابحث عن الحد الأقصى للمطابقة في $ج$.
  • قم بإزالة القمم المتطابقة لـ $ص$ من الرسم البياني.

تعقيد وقت التشغيل هو $O(k \cdot m\sqrt{n})$.

ولكن هل تجد هذه الخوارزمية دائمًا الحد الأقصى؟ $ك$-مطابقة؟

Answer 1

لا.هنا مثال مضاد: $X=\{a,b\}, Y=\{c,d,e,f\}, E=\{ac, ad, ae, be, bf\}, k=2$.يمكن أن تختار التكرار الأول للخوارزمية الخاصة بك $\{ae,bf\}$ (وخاصة الحافة $ae$)، مما يمنع العثور على حل على الرغم من وجوده: $\{ac, ad, be, bf\}$.