تغطية الرؤوس بالحواف: لماذا لا تكفي أكبر مطابقة؟

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

لأن أكبر مطابقة تمنع مشاركة رأس بين حافتين، وقد تترك رؤوسًا بلا حافة مختارة. غطاء الحواف يسمح بالمشاركة ويطلب الوصول إلى كل رأس. في النجمة A مع الأوراق B C D، أكبر مطابقة حافة واحدة، وأصغر غطاء هو AB AC AD بحجم 3.

• غطاء الحواف مجموعة حواف تجعل كل رأس طرفًا لحافة مختارة على الأقل؛ أصغر غطاء يحقق ذلك بأقل عدد من الحواف. يبنى من أكبر مطابقة ثم إضافة حواف للرؤوس الباقية. [1] نموذجنا محدود وغير فارغ وبسيط وغير موجه وبلا حلقات أو أوزان؛ الحافة تختار مرة واحدة.
• في النجمة ذات الحواف AB AC AD، جميع الحواف تشترك في A، فتكون أكبر مطابقة بحجم 1. كل ورقة تجبر حافتها، لذلك أصغر غطاء وحيد بحجم 3؛ اشتراكه في A مسموح.
• المطابقة تختار حواف بلا طرف مشترك. غطاء الرؤوس يختار رؤوسًا تمس كل حافة؛ وغطاء الحواف يختار حواف تمس كل رأس. دون رؤوس معزولة، حجم أصغر غطاء حواف يساوي n−ν، حيث ν حجم أكبر مطابقة. [2] المطابقة الكاملة غطاء أيضًا، لكن الغطاء لا يلزم أن يكون مطابقة، ولا يسمح بتطبيق العلاقة عند وجود معزول.
• نبدأ بأكبر مطابقة حجمها ν، فتترك n−2ν رأسًا. لا توجد حافة بين رأسين تركتهما، وإلا كبرت المطابقة. دون معزول نضيف حافة لكل رأس باقٍ، فنجمع n−ν حافة. لأي غطاء، اختيار حافة من كل مركبة يعطي مطابقة بعدد المركبات c≤ν، والاتصال يفرض |F|≥n−c≥n−ν؛ فيثبت الحد الأدنى. البدء بمطابقة لا تقبل إضافة حافة لا يكفي إن لم تكن الأكبر: BC وحدها في المسار AB BC CD تعطي غطاء 3، بينما AB CD يعطي الأدنى 2.
• المسار AB BC CD له غطاء أدنى وحيد AB CD بحجم 2 ومطابقة أكبر بالحجم نفسه. المثلث AB AC BC يحتاج حافتين للغطاء مقابل مطابقة 1، وله ثلاثة أغطية دنيا مختلفة. حجم الحل وحده لا يحدد وحدانيته.
• المثلث مع الرأس المعزول D لا يملك غطاء حواف؛ لا توجد حافة تصل إلى D. العدد 4−1=3 لا يصبح حلًا لهذه المسألة، وحذف D يغير الرسم المطلوب تغطيته.
• فحصنا 64 قائمة حواف على أربعة أسماء:729 مجموعة مرشحة و 249 غطاء صحيحًا؛41 مدخلًا بلا معزول و 23 معه. اتفقت العلاقة والطرق المستقلة في 41 مدخلًا، بإجمالي 52 غطاء أدنى؛ هذا حصر محدود مع برهان عام منفصل، وليس ادعاء سرعة خوارزمية.

اختر الحواف، ثم اسأل عن الرؤوس التي تصل إليها

غطاء الحواف مجموعة حواف تجعل كل رأس طرفًا لحافة مختارة على الأقل؛ أصغر غطاء يحقق ذلك بأقل عدد من الحواف. يبنى من أكبر مطابقة ثم إضافة حواف للرؤوس الباقية. [1]

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

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

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

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

أوراق النجمة تفرض الحواف الثلاث

المركز A والأوراق B وC وD. الحواف الموجودة وحدها AB وAC وAD. كل ورقة لها حافة واحدة، فلا توجد BC أوBD أوCD، ولا يجوز إضافتها لإصلاح الاختيار.

أي حافتين من الثلاث تشتركان في A. لذلك لا تستطيع المطابقة اختيار اثنتين، ويمكنها اختيار AB وحدها مثلًا؛ أكبر حجم هو 1. هذه المطابقة تغطي A وB، وتترك C وD بلا حافة مختارة.

لغطاء الحواف، يجب الوصول إلى B، وحافتها الوحيدة AB. ويجب الوصول إلى C، فتجبر AC، ثم إلى D فتجبر AD. إذن الحواف الثلاث كلها مفروضة. وهي تصل أيضًا إلى A، فتكون غطاء صحيحًا بحجم 3.

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

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

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

غطاء الحواف وغطاء الرؤوس يطلبان شيئًا مختلفًا

المطابقة تختار حواف بلا طرف مشترك. غطاء الرؤوس يختار رؤوسًا تمس كل حافة؛ وغطاء الحواف يختار حواف تمس كل رأس. دون رؤوس معزولة، حجم أصغر غطاء حواف يساوي n−ν، حيث ν حجم أكبر مطابقة. [2]

في النجمة نفسها، اختيار الرأس A وحده يمس الحواف الثلاث كلها، فيكون غطاء رؤوس بحجم 1. أما غطاء الحواف بحجم 3 فيختار AB AC AD ليصل إلى الأوراق أيضًا. قد يلتقي العدد 1 مع حجم أكبر مطابقة دون أن يكون الاختيار نفسه.

لا نقيس حجم غطاء الرؤوس بعدد خطوطه؛ عناصره رؤوس. ولا نقيس حجم غطاء الحواف بعدد أسماء الأطراف المختلفة؛ عناصره حواف. كتابة القائمة المختارة قبل الحجم تجعل الفرق ظاهرًا.

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

العلاقة n−ν تستخدم حجم أكبر مطابقة في الرسم نفسه. وهي تخص أصغر غطاء حواف عند عدم وجود معزول. ليست معادلة لحجم غطاء الرؤوس، ولا تستبدل شرط الوصول إلى كل رأس بشرط الوصول إلى كل حافة.

من أكبر مطابقة إلى غطاء بحجم n−ν

خذ أكبر مطابقة M حجمها ν. لأن حوافها لا تتشارك طرفًا، تغطي 2ν رأسًا مختلفًا من n. يبقى n−2ν رأسًا غير مغطى بهذه المطابقة؛ نسميها الرؤوس الباقية.

لا توجد حافة تصل رأسين باقيين معًا. لو وجدت حافة كهذه، لكان طرفاها غير مستعملين في M؛ نستطيع إضافتها دون مخالفة شرط المطابقة، فيصبح الحجم ν+1، وهو يناقض كونها الأكبر.

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

كل حافة مضافة مختلفة عن حواف M لأن أحد طرفيها كان باقيًا. والحواف المضافة مختلفة عن بعضها: تكرار الحافة لرأسين باقيين يعني أنها تصل بينهما، وقد استبعدنا ذلك. إذن أضفنا بالضبط n−2ν حافة جديدة.

أصبحت الرؤوس التي كانت في M مغطاة كما كانت، ووصلت حافة إلى كل رأس باقٍ. الحجم الكلي ν+(n−2ν)=n−ν. هذا يثبت وجود غطاء بهذا الحجم؛ نحتاج بعده حدًا يمنع غطاء أصغر.

في النجمة، ابدأ بـAB. الباقيان C وD يضيفان AC وAD. الناتج 3=4−1. وفي المثلث ابدأ بـAB، ثم اختر AC أوBC للرأس C؛ الناتج 2=3−1، مع اختلاف المجموعة الممكنة دون اختلاف الحجم.

يجب البدء بأكبر مطابقة للحصول على الحجم الأدنى. في المسار AB BC CD، المطابقة BC وحدها لا تقبل إضافة حافة دون مشاركة طرف، لكنها ليست الأكبر: AB CD من حافتين أكبر. توسيع BC إلى غطاء يضيف AB وCD ويعطي 3، بينما الغطاء الأدنى AB CD حجمه 2.

لماذا لا يوجد غطاء أقل من n−ν؟

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

اختر حافة واحدة من كل مركبة. هذه الحواف لا تشترك في رأس لأن المركبات منفصلة، فتكوّن مطابقة بحجم c داخل الرسم الأصلي أيضًا. وبما أن ν هو أكبر حجم مطابقة، فإن c≤ν.

المركبة المتصلة ذات v رأسًا تحتاج إلى v−1 حافة على الأقل: نبدأ برأس، وكل وصول إلى رأس جديد في شبكة متصلة يحتاج وصلة، ونستطيع اختيار هذه الوصلات لتصل إلى الرؤوس دون دورة. الحواف الإضافية لا تقلل العدد اللازم للاتصال.

نجمع على مركبات F: مجموع الرؤوس هو n، ومجموع الحدود v−1 هو n−c. إذن |F|≥n−c≥n−ν. هذا ينطبق على كل غطاء، حتى لو اختار حواف كثيرة أو احتوى دورات.

البناء السابق حقق n−ν، والحد الحالي يمنع أقل منه؛ لذا أصغر حجم هو n−ν عند عدم وجود معزول. هذا برهان عام داخل النموذج المعلن، منفصل عن تعداد الرسوم الصغيرة.

العدد لا يحدد قائمة حواف وحيدة. تستطيع اختيارات الجار في البناء أن تعطي مجموعات مختلفة، وقد تتكرر المجموعة نفسها من بدايات مختلفة. نزيل التكرار عند عد الأغطية، ولا نعد ترتيب اختيار الحواف حلولًا جديدة.

المسار والمثلث والمعزول يراجعون الشروط

في المسار A-B-C-D، الحواف AB BC CD فقط. الورقتان A وD تفرضان AB وCD لأي غطاء. هاتان الحافتان تصلان إلى الأربعة، فيكون الغطاء الأدنى وحيدًا بحجم 2. وهما أيضًا أكبر مطابقة من حافتين؛ هنا يتطابق الاختياران.

في المثلث A B C، أي حافة منفردة تترك رأسًا. أي حافتين مختلفتين تصلان إلى الثلاثة، فتكونان غطاء أدنى بحجم 2. القوائم هي AB AC، وAB BC، وAC BC؛ عددها 3، لا 6، لأن ترتيب الحافتين لا يخلق غطاء آخر.

أكبر مطابقة في المثلث حافة واحدة، لأن أي حافتين لهما طرف مشترك. لذلك n−ν=3−1=2، لكنه لا يشرح وحده عدد الأغطية الدنيا. الصورة الداخلية تعرض القوائم الثلاث على المثلث نفسه.

أضف الرأس D إلى قائمة رؤوس المثلث دون إضافة أي حافة تصل إليه. يبقى حجم أكبر مطابقة 1، لكن كل مجموعة حواف مختارة تقع أطرافها داخل A B C. يستحيل أن تصل إلى D، فلا يوجد غطاء حواف أصلًا.

الحساب 4−1=3 لا يزيل هذا العائق. اختيار حواف المثلث الثلاث يغطي الثلاثة فقط؛ ليس غطاء للرسم ذي أربعة رؤوس. حذف D ثم حساب غطاء للمثلث يحل مسألة أخرى بقائمة رؤوس أصغر.

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

الحصر يراجع الأغطية، والبرهان يحدد النطاق العام

على أربعة أسماء A B C D توجد ستة أزواج ممكنة. أخذنا كل واحدة من 2^6=64 قائمة حواف بسيطة غير موجهة. هذه رسوم مسماة؛ لا ندمج قائمتين لمجرد أنهما متشابهتان بعد تبديل الأسماء.

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

كان 41 مدخلًا بلا رأس معزول و 23 مع معزول. المدخلات ذات المعزول لم تعط أي غطاء، فحفظنا غياب الحل، لا عددًا مصطنعًا. وفي 41 مدخلًا الباقية اتفق أصغر حجم مع n−ν.

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

حسبنا المطابقات بطريقة مستقلة تترك رأسًا حرًا أو تقرنه بجار حر. ثم وسعنا كل مطابقة أكبر بكل اختيار ممكن لحواف الرؤوس الباقية. بعد إزالة التكرار، أعادت هذه الطريقة مجموعات الأغطية الدنيا نفسها في 41 مدخلًا؛ بلغ إجمالي الأغطية الدنيا 52.

الأعداد 729 و 249 و 52 مجاميع على المدخلات الأربعة والستين، وليست أعدادًا للنجمة وحدها. هذا فحص محدود، ولا نقدم الحصر على أنه خوارزمية سريعة للرسم الكبير. صحة العلاقة العامة في المقال تستند إلى البناء والحد المقابل.

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