العثور على أقصى قدر من المطابقة التي تشبع مجموعة معينة من القمم

Question

في الرسم البياني في Bipartite غير مرجح $ g= (x + y، e) $ ، نود العثور على أقصى قدر من المطابقة، ولكن من بين كل هذه التطابقات القصوى، نود العثور على واحدة تشبع مجموعة فرعية معينة $ x_0 \ subseteq x $ .

شرط ضروري لوجود مثل هذه المطابقة هو أن $ x_0 $ تلبية حالة زواج القاعة، أي لكل $ x '\ subseteq x_0 $ ، عدد الجيران من $ x' $ هو الأقل $ | X '| $ . إذا كانت هذه الحالة راضية، فيمكننا العثور على مطابقة $ m $ تشبع جميع رؤوس $ x_0 $ ، ولكن $ m $ ليس بالضرورة الحد الأقصى للمطابقة في $ g $ .

هل من الممكن دائما تمديد $ m $ في أقصى مطابقة؟ بدلا من ذلك، هل هناك طريقة مختلفة للعثور على أقصى مطابقة تشبع $ x_0 $ عندما تكون الشرط الضروري راضيا؟

Answer 1

بعد بعض الأبحاث، اكتشفت أن سؤالي هو حالة خاصة لمشكلة مطابقة الأولوية .في هذه الحالة، هناك فصول أولوية، $ x_0 $ و $ x_1:= v \ setminus x_0 $ وبعدالهدف هو إيجاد مطابقة يزيد عدد القمم المشبعة في $ X_0 $ ، وتخضع لذلك، عدد القمم المشبعة في $ x_1 $ .هناك خوارزميات فعالة تحل هذه المشكلة لأي عدد من الفئات ذات الأولوية.من المعروف أن أي مطابقة أولوية هي أيضا مطابقة أقصى كرادة.