مشطور الرسوم البيانية مع مين الأوزان

Question

لدي كامل الرسم البياني الثنائي مع عقدة مجموعات $A=\{a_1,a_2,\ldots,a_n\}$ و $B=\{b_1 ، b_2,\ldots,b_n\}$.كل عقدة لديه الوزن ، $v_i$ بالنسبة $a_i$ و $w_i$ بالنسبة $b_i$.كل عقدة $a_i$ متصل بالضبط عقدة واحدة $B$, ، ويقول $b_j$, عبر الحافة $e_i$, الذين الوزن $\مين(v_i,w_j)$.الآن أريد أن العثور على واحد-إلى-واحد من الخرائط $A$ إلى $B$, الذين مبلغ من حافة أوزان صغيرة قدر الإمكان.

فكرتي هي أن نوع $v_i$s على نحو متزايد ، $w_i$s بتناقص ومن ثم العثور على مجموع كل $\مين(v_i,w_i)$ بعد الفرز.هل هو صحيح ؟ يمكنك ان تعطي دليل/والنقض?

يجب تشغيل الكمبيوتر محاكاة $n=5,6,\ldots,10$ مع عشوائية قمة الأوزان وجدت أي بالدليل.

Answer 1

فمن الجميل أن يكون لديك فحص فكرتك على بعض عينات عشوائية.

---

أن نرى لماذا فكرتك العمل ، دعونا العثور على أبسط ولكن غير تافهة الحالة ثم نلقي نظرة على ذلك.البساطة و WLOG وزن عقدة سيتم استخدامها للدلالة على أن العقدة.على سبيل المثال ، إذا $A$ يحتوي على عقدة مع الوزن $42$, تلك العقدة سوف يشار إليها باسم عقدة 42.

حالة $n=1$ هو تافهة.

السماح $n=2$.إذا كنا يحدث أن ننظر إلى $A=\{1, 2\}$ و $B=\{3,4\}$, ثم ومع ذلك نختار رسم الخرائط ، وسوف يكون المبلغ $1+2=3$.هذا النموذج هو على ما يبدو ليس المنير.

ماذا عن $A=\{1, 3\}$ و $B=\{2,4\}$?

• إذا ربطنا 1 مع 2 و 3 مع 4 ، المجموع $\مين(1,2) + \مين(3,4)=1+3=4$.
• إذا ربطنا 1 مع 4 و 3 مع 2 من المبلغ $\مين(1,4) + \مين(3,2)=1+2=3$.

لذلك هذا هو غير تافهة سبيل المثال.الآن علينا أن نسأل السؤال الأساسي لماذا هل الخيار الثاني تنتج أصغر المبلغ ؟

للإجابة على السؤال يجب أن نلاحظ كيف أن هؤلاء مبالغ تصل.لاحظ أن 1 يظهر في كل المبالغ.هل هذا صدفة ؟ أعتقد للحظة و سوف تعرف أنه ليس كذلك.1 هو العدد الأدنى من جميع الأرقام.لذلك كل ما هو متصل ، وسوف يكون اختيار الوزن الاتصال.

يعني مهما كان رقم 1 متصل ، وهو 3 في هذه الحالة ، هذا العدد سوف يكون في عداد المفقودين في وقت لاحق من الحسابات, أي أنه سيكون "يضيع".أكبر "النفايات" هو أقل الأرقام المتبقية سيتم وبالتالي أقل وزنا المتبقية اتصال سوف تنتج منذ وظيفة $\مين(\cdot, \cdot)$ يتناقص مع الاحترام إلى كل من المتغيرات.حتى 1 يجب أن تكون متصلا إلى عدد كبير قدر الإمكان.هذا هو لماذا 1 متصل إلى 4 بدلا من 3 حتى تنتج الحد الأدنى من المبلغ الإجمالي.

في حالة $n=2$, هناك اثنين فقط من الخيارات لرسم الخرائط.إما أصغر عدد في $A$ يتم تعيينها إلى أصغر عدد في $B$, التي اطلق عليها اسم "إلى الأمام رسم الخرائط" ، أو إلى أكبر عدد في $B$, التي اطلق عليها اسم "عكس رسم الخرائط".لجعل الخرائط تنتج أصغر الوزن الكلي, ينبغي دائما اختيار "عكس رسم الخرائط" ، حتى أن عدد كبير سوف يضيع (أو ما هو نفسه ، عدد أصغر سيتم الاحتفاظ بها لاستخدامها.)

---

لإثبات فكرة هو الصحيح, علينا أولا أن أي تعيين من $A$ إلى $B$, هناك رسم خرائط $\min(A)$ إلى $\ماكس(ب)$ مع عدم وجود مزيد من الوزن الكلي.لنفترض خريطة $f$ خرائط $\min(A)$ بعض $b_j$ و عدد $a_i$ إلى $\ماكس(ب)$.ثم يمكننا أن نجعل آخر خريطة $f'$, الذي هو نفس $f$ باستثناء هذه 4 العدد ، $f'$ خرائط $\min(A)$ إلى $\ماكس(ب)$ و $a_i$ إلى $b_j$.لأنه كما بينا أعلاه ، لمدة أربعة أرقام $\مين(أ) ، a_i$ و $b_j$, $\ماكس(ب)$, لدينا $$ \مين(\مين(أ) \ماكس(ب)) + \مين(a_i, b_j)\لو \مين(\مين(أ) ، b_j) + \مين(a_i, \ماكس(ب))$$ الوزن الكلي $f'$ ليست أكبر من $f$.

حتى نعلم ،

• الحد الأدنى من الوزن الإجمالي يأتي من تعيينات خرائط $\min(A)$ إلى $\ماكس(ب)$.
• جميع التعيينات التي خريطة $\min(A)$ إلى $\ماكس(ب)$, الحد الأدنى الوزن الإجمالي يأتي من قبل نفس الحجة ، رسم خرائط الحد الأدنى من الأرقام المتبقية في $A$ (أيثاني أقل عدد في $A$) إلى الحد الأقصى من الأرقام المتبقية في $B$ (أي الثانية الحد الأدنى في $B$).
• جميع التعيينات التي خريطة $\min(A)$ إلى $\ماكس(ب)$ والثاني الحد الأدنى في $A$ الثانية أقصى عدد في $B$, الحد الأدنى الوزن الإجمالي يأتي من رسم خرائط الثالث العدد الأدنى في $A$ إلى ثالث أكبر عدد ممكن في $B$.
• و هكذا حتى آخر أقل عدد في $A$ يتم تعيينها إلى مشاركة أكبر عدد ممكن في $B$, أي أكبر عدد ممكن في $A$ يتم تعيين إلى الحد الأدنى في $B$. $\علامة$

أكثر دليل رسمي يمكن أن تعطى.ومع ذلك ، فإن المنطق أعلاه قد يكون أسهل للفهم.وينبغي أن أعتقد إقناع الإنسان العادي.

---

هنا هو آخر طريقة مباشرة إثبات فكرتك.

الأولى تحمل جميع الأرقام المميزة.دعونا نثبت من خلال reductio ad absurdum.لنفترض الحد الأدنى من الوزن الكلي يمكن الوصول إليها عن طريق رسم الخرائط $g$ وغيرها من الخرائط الموضحة في فكرتك.ثم $g$ يجب أن يحتوي على sub-الخرائط التي هي "إلى الأمام رسم الخرائط" ، أي يجب أن يكون هناك رقمين $\alpha_1\lt \alpha_2$ في $A$ و رقمين $\beta_1\lt \beta_2$ في $B$ مثل أن $g(\alpha_1)=\beta_1$ و $g(\alpha_2)=\beta_2$.

الآن يمكننا أن نجعل آخر الخرائط $g'$ الذي هو نفس $g$ في كل مكان آخر إلا أن sub-خرائط $g'$ على $\alpha_1$ و $\alpha_2$ هو "عكس رسم الخرائط" ، أي ، $g'(\alpha_1)=\beta_2$ و $g'(\alpha_2)=\beta_1$.يمكننا الآن كما كان من قبل ، تحقق من أن الوزن الكلي $g'$ هو أصغر من أن $g$, الذي يتناقض مع افتراضنا.

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

---

كنت قد تكون مهتمة في مشكلة مماثلة ، كيفية إثبات الجشع خوارزمية أن الحد الأقصى للمبلغ من الاقتران.

Answer 2

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