مبرهنة كونيغ: كيف تثبت مطابقة وتغطية الاختيار الأمثل؟

الخلاصة السريعة

لأن كل تغطية تحتاج رأسًا مختلفًا لكل حافة من مطابقة ذات أطراف منفصلة. في مثالنا، المطابقة M={A2,B1,D3} والتغطية K={D,1,2} حجمهما3؛ لا توجد مطابقة أكبر ولا تغطية أصغر. المساواة في العدد، لا في نوع العناصر أو أسمائها.

• المطابقة مجموعة حواف لا تشترك حافتان منها في رأس. [3] والتغطية مجموعة رؤوس تلمس كل حافة في طرف واحد على الأقل. [2] نثبت L={A,B,C,D} وR={1,2,3}؛ الحواف A1 وA2 وB1 وC2 وD3 تعبر بين المجموعتين.
• الحواف A2 وB1 وD3 مطابقة من ثلاث حواف، لأن أطرافها الستة مختلفة. C غير مستخدم في هذه المطابقة، ولا يمكن إضافة حافة رابعة؛ كل حافة في المثال تحتاج رأسًا من ثلاثة رؤوس في R.
• الرؤوس D و1 و2 تغطي الحواف الخمس:1 يغطي A1 وB1، و2 يغطي A2 وC2، وD يغطي D3. اختيار الرؤوس اليسرى للمطابقة، أي A وB وD، لا يغطي C2.
• كل مطابقة وتغطية صالحتين تحققان |M|≤|K|: الحواف المنفصلة تحتاج أطرافًا مختلفة في التغطية. وجود اختيارين بحجم3 يثبت الحدين معًا. ويمكن اختيار R كلها كتغطية أخرى من ثلاثة رؤوس؛ لا ندعي وحدانية الحل.
• L كلها تغطية من أربعة رؤوس، ولا يبقى الغطاء صحيحًا إذا حذفت أي رأس منها وحده. مع ذلك ليست الأقل؛ نستبدل A وB وC بالرأسين1 و2 ونبقي D، فنحصل على التغطية ذات الحجم3.
• المساواة العامة بين أكبر مطابقة وأصغر تغطية تخص الرسوم الثنائية. [1] في المثلث، أكبر مطابقة حافة واحدة وأصغر تغطية رأسان؛ الحد1≤2 يبقى صحيحًا، لكن المساواة تفشل. ليست المسألة تغطية كل رأس أو إيجاد أقل كلفة موزونة.

ميز الحواف المختارة من الرؤوس المختارة

المطابقة تختار حواف لا تتلاقى في رأس مشترك؛ أكبر مطابقة هي ذات أكبر عدد من الحواف. [3] أما تغطية الرؤوس فتختار رؤوسًا تجعل كل حافة متصلة برأس مختار واحد على الأقل؛ أصغر تغطية هي الأقل عددًا. [2]

نثبت مجموعة يسار L={A,B,C,D} ومجموعة يمين R={1,2,3}. حواف مثالنا الخمس فقط هي A1 وA2 وB1 وC2 وD3. لا حافة داخل L أو داخل R، ولذلك الرسم ثنائي بهذا التقسيم.

الحروف والأرقام أسماء رؤوس مختلفة، وليست أوزانًا أو درجات. الحافة A2 تصل A بالرأس2؛ اسمها لا يعني حافتين. الرسم غير موجه وبلا حلقات ذاتية أو حواف مكررة، والخطوط لا تمثل مسافات مقاسة.

راجع المطابقة حافة حافة

نختار M={A2,B1,D3}. الحافة A2 تستخدم الرأسين A و2؛ والحافة B1 تستخدم B و1؛ والحافة D3 تستخدم D و3. الأطراف الستة مختلفة، إذن لا تتنافس حافتان من هذه الثلاث على رأس واحد.

الرأس C لم يدخل المطابقة. ذلك لا يجعل الاختيار ناقصًا تلقائيًا: لدينا أربعة رؤوس يسارًا وثلاثة يمينًا، وكل حافة مختارة تحتاج رأسًا يمينيًا مختلفًا. لا يمكن أن تضم أي مطابقة في هذا المثال أكثر من ثلاث حواف.

المطابقة لا تحتاج أن تضم كل حافة في الرسم. ترك A1 وC2 خارج M مقصود؛ لو أضفنا A1 لتكرر A و1، ولو أضفنا C2 لتكرر2. لسنا بصدد ممر يزور الحواف كلها، ولا قائمة بدرجات مطلوبة.

في اللوحة اليسرى من الصورة الرئيسية، الذهب للحواف الثلاث المختارة والرمادي للباقي. تقاطع خطين على الصفحة لا يضيف رأسًا جديدًا؛ الرؤوس هي الدوائر المسماة فقط.

افحص التغطية على الحواف الخمس كلها

نختار K={D,1,2}. يكفي أن تلمس كل حافة رأسًا واحدًا من هذه المجموعة. الحافتان A1 وB1 تلمسان1، والحافتان A2 وC2 تلمسان2، والحافة D3 تلمس D. لذلك لا تبقى حافة دون تغطية.

الجدول يسجل شاهدًا واحدًا لكل حافة. لا نطالب بأن يكون طرفا الحافة كلاهما مختارين، ولا بأن تدخل كل رؤوس الرسم في K. الرأس3 خارج التغطية، ومع ذلك حافته D3 مغطاة من طرف D.

لو أخذنا الرؤوس اليسرى للحواف المختارة في M، لحصلنا على K′={A,B,D}. هذه مجموعة من ثلاثة رؤوس أيضًا، لكنها ليست تغطية: طرفا C2 هما C و2، وكلاهما خارج K′.

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

الاختياران يثبتان الحدين معًا

خذ أي مطابقة وأي تغطية صالحتين في رسمنا. لكل حافة من المطابقة طرف مختار في التغطية، لأن التغطية تلمس جميع الحواف. ولا يستطيع الرأس نفسه أداء هذا الدور لحافتين من المطابقة؛ حوافها لا تشترك في رأس.

لذلك عدد حواف المطابقة لا يزيد على عدد رؤوس التغطية: |M|≤|K|. البرهان يعد أطرافًا مختلفة، ولا يحتاج أن تكون الحواف متساوية الطول أو مرسومة دون تقاطع. وهو يعمل أيضًا في الرسم غير الثنائي.

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

تقرر مبرهنة كونيغ أن أكبر حجم مطابقة يساوي أصغر حجم تغطية في رسم ثنائي. [1] مثالنا يوضح المساواة بشاهدين صريحين؛ لا يقدم وحده برهان المبرهنة لكل رسم ثنائي.

يمكن أيضًا أخذ K₂={1,2,3}؛ كل حافة تلمس رأسًا يمينيًا، وهذه تغطية ثانية من الحجم3. وكذلك M₂={A1,C2,D3} مطابقة ثانية من الحجم3. الأمثلية لا تعني أن الأسماء المختارة وحيدة.

عدم إمكان الحذف لا يثبت أقل عدد

المجموعة L={A,B,C,D} تغطي الحواف الخمس كلها، لأن كل حافة تبدأ من أحد رؤوسها. حجمها4. إذا حذفنا A وحده، فقدنا تغطية A1 وA2؛ وإذا حذفنا B فقدنا B1، وإذا حذفنا C فقدنا C2، وإذا حذفنا D فقدنا D3.

إذن لا نستطيع تقليص هذه التغطية بحذف رأس منها وحده مع الاحتفاظ ببقيتها. بل أي مجموعة جزئية أصغر منها تفقد حافة عند أول رأس تحذفه. هذا يصف عدم إمكان التقليص بالحذف، لا أقل عدد بين كل التغطيات.

لدينا بالفعل K={D,1,2} بحجم3. الوصول إليها يغير نوع الاختيار: نحذف A وB وC من L، ثم نضيف1 و2، ونبقي D. التغيير الكلي يقلل العدد من4 إلى3، رغم أن أي حذف منفرد من L يفشل.

الصورة الداخلية تقارن التغطيتين على الحواف نفسها؛ لا نغير الرسم لإنجاح المجموعة الأصغر. لذلك عبارة «لم أجد رأسًا يمكن حذفه» أضعف من «أثبتُّ أنه لا توجد تغطية أصغر».

المثلث يبين لماذا نثبت شرط الثنائية

نأخذ مثالًا آخر، هو مثلث رؤوسه X وY وZ وحوافه XY وYZ وXZ. كل حافتين تشتركان في رأس، فلا توجد مطابقة من حافتين؛ أكبر حجم مطابقة1.

رأس واحد لا يغطي المثلث؛ إذا اخترنا X بقيت YZ بلا طرف مختار، وينطبق الأمر على اختيار Y أو Z. أما أي رأسين فيغطيان الحواف الثلاث، فأصغر حجم تغطية2.

إذن1≤2 صحيح، لكن1=2 خطأ. المثلث لا يقبل تقسيم رؤوسه إلى مجموعتين بحيث تعبر كل حافة بينهما: إذا فصلنا X عن Y، ثم فصلنا Y عن Z، صار X وZ في المجموعة نفسها مع وجود XZ.

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