الرأس الأكبر درجة يغطي نفسه وجيرانًا كثيرين، لكنه قد يترك رؤوسًا تحتاج اختيارات متفرقة. في مثالنا A هو وحده صاحب أكبر درجة، ومع ذلك لا يوجد حل من رأسين يبقي A مختارًا. اختيار B وC يغطي الرؤوس السبعة برأسين. سنثبت الحواف، ونقارن الحلين دون تغيير الرسم.
الخلاصة السريعة
لا يضمن ذلك أقل عدد إذا أبقيت الرأس الأول في الحل. في مثالنا درجة A هي4، لكن أي مجموعة مسيطرة تضم A تحتاج ثلاثة رؤوس على الأقل؛ المجموعة {B,C} تكفي برأسين. يمكن لخوارزمية تسمح بإلغاء الاختيار الأول أن تتراجع عنه، فلا نحكم هنا على كل طريقة تبدأ به.
- المجموعة المسيطرة تضم رؤوسًا تجعل كل رأس مختارًا أو مجاورًا لرأس مختار. وأصغر مجموعة مسيطرة هي الأقل عددًا بين هذه المجموعات. [1] نعد الرؤوس، ولا نعطيها أوزانًا أو تكاليف.
- الحواف AB AC AD AE BD BF CE CG فقط، ودرجات A B C D E F G هي (4,3,3,2,2,1,1). A يغطي A B C D E، ويترك F وG؛ الوصول إليهما عبر حافتين لا يكفي للسيطرة العادية.
- إذا بقي A، فلا رأس إضافي واحد يغطي F وG معًا: F له الجار B فقط، وG له الجار C فقط. {A,F,G} تغطي الجميع، فيكون أقل عدد مع إبقاء A هو3.
- {B,C} تغطي الجميع: B يغطي A B D F، وC يغطي A C E G. لا رأس منفرد يغطي السبعة لأن أكبر درجة4، لذلك أقل عدد2. والفحص يثبت أن {B,C} هي الزوج الوحيد الذي ينجح.
- المجموعة المسيطرة الدنيا من حيث الاحتواء لا تضم مجموعة مسيطرة أصغر ضمنها؛ كل مجموعة ذات أقل عدد دنيا بهذا المعنى، ولا يلزم العكس. [2] سنفصل عدم إمكان الحذف عن أقل عدد بين جميع الاختيارات. في {A,F,G} يفقد حذف A الرؤوس A D E، وحذف F يترك F، وحذف G يترك G؛ مع ذلك ليست الأقل لأن {B,C} أصغر.
- في النجمة ذات المركز A وأربع أوراق، اختيار أعلى درجة ينجح برأس واحد. وفي ثلاثة رؤوس معزولة، يجب اختيار الثلاثة لأن كل رأس يغطي نفسه فقط. الشروط هنا للسيطرة العادية، دون اشتراط اتصال المختارين.
- فحصنا128 مجموعة في المثال، و32768 مجموعة على1024 رسمًا خماسيًا. عند كسر تعادل أكبر درجة بأسبق اسم، كان إبقاء الرأس المختار أغلى من الأمثل في20 مدخلًا؛675 مدخلًا لها مجموعة دنيا أكبر من الحد الأدنى. هذه أعداد الحصر المحدود، والبرهان على مثالنا منفصل.
الرأس المختار يغطي نفسه وجيرانه
المجموعة المسيطرة تضم رؤوسًا تجعل كل رأس مختارًا أو مجاورًا لرأس مختار. وأصغر مجموعة مسيطرة هي الأقل عددًا بين هذه المجموعات. [1] نعد الرؤوس، ولا نعطيها أوزانًا أو تكاليف.
نعمل على رسم منته غير فارغ، بسيط وغير موجه وبلا أوزان. الحافة تعني التجاور المباشر. إذا اخترنا رأسًا، فإنه يدخل الجزء المغطى بنفسه، وتدخل معه رؤوس جيرانه. نأخذ اتحاد هذه الأجزاء لجميع المختارين.
لا يشترط أن تكون الرؤوس المختارة متجاورة، ولا أن يكون الرسم الناتج عنها متصلًا. ولا نطلب جارًا مختارًا إضافيًا للرأس المختار كي يغطي نفسه. هذه هي السيطرة العادية التي نعتمدها، وليست مسألة تغطية كل حافة أو اختيار حواف منفصلة.
إذا كان رأس خارج المجموعة على بعد حافتين من مختار، فلا يكفي هذا الطريق لتغطيته. يجب أن يكون في المجموعة أو أن يجاور أحد عناصرها مباشرة. لهذا نثبت قائمة الجيران بدل النظر إلى قرب الدوائر في الصورة.
أكبر درجة تترك ورقتين مختلفتين
ثبت أسماء A B C D E F G والحواف AB AC AD AE BD BF CE CG. لا توجد حافة AF أوAG أوFG أوBC. درجات الأسماء بالترتيب (4,3,3,2,2,1,1)، ومجموعها16 يساوي ضعف الحواف الثماني.
A أعلى درجة وحده؛ جيرانه B C D E. اختيار A يغطي خمسة أسماء: A نفسه وجيرانه الأربعة. يبقى F وG خارج الجزء المغطى، لأن F متصل بـB وحده، وG متصل بـC وحده.
صحيح أن A يصل إلى F على الطريق A→B→F، وإلى G على A→C→G. لكن وجود الطريقين لا يحولهما إلى حافتين AF وAG. لا نضيف هذه الحواف أثناء الفحص، ولا نستعمل المسافة2 بدل التجاور.
لإكمال السيطرة مع الاحتفاظ بـA، يجب اختيار اسم من {B,F} لتغطية F، واسم من {C,G} لتغطية G. المجموعتان منفصلتان؛ لا رأس واحد يحقق الشرطين. لذلك نحتاج اسمين إضافيين على الأقل، أي ثلاثة مختارين في المجموع.
{A,F,G} تحقق هذا الحد: A يغطي A B C D E، وF يغطي F وB، وG يغطي G وC. الصورة الرئيسية ستقارنها بـ{B,C} على الحواف نفسها. اللون يحدد الاختيار، ولا يحذف رؤوس الرسم غير المختارة.
| الرأس | الدرجة | المغطى باختياره منفردًا |
|---|---|---|
| A | 4 | A B C D E |
| B | 3 | A B D F |
| C | 3 | A C E G |
| D | 2 | A B D |
| E | 2 | A C E |
| F | 1 | B F |
| G | 1 | C G |
رأسان آخران يحققان الحد الأدنى
اختيار B يغطي A B D F؛ واختيار C يغطي A C E G. اتحاد القائمتين هو A B C D E F G، فتكون {B,C} مجموعة مسيطرة ذات رأسين. وجود A في القائمتين لا يجعله مختارًا ثالثًا؛ هو رأس مغطى من جار مختار.
لا يوجد حل من رأس واحد في هذا الرسم. الرأس ذو الدرجة d يغطي d+1 أسماء على الأكثر، وأكبر درجة هنا4، فتبلغ أكبر تغطية منفردة5 فقط من سبعة. لذلك كل مجموعة مسيطرة تحتاج رأسين على الأقل.
حققنا حدًا أدنى2 بمثال صالح من رأسين، فيثبت أن أقل عدد هو2. أما اشتراط إبقاء A فغير المسألة المقيدة: لها حد أدنى3 حققناه بـ{A,F,G}. لا نخلط أفضل اختيار تحت شرط إضافي بأفضل اختيار بين جميع المجموعات.
يمكن أيضًا إثبات وحدانية الزوج الأمثل هنا. لتغطية F نختار B أوF، ولتغطية G نختار C أوG. لأي حل من رأسين، تستهلك هاتان الحاجتان الاسمين كليهما، فتكون الاحتمالات {B,C} أو{B,G} أو{F,C} أو{F,G}.
{B,G} تترك E، و{F,C} تترك D، و{F,G} تترك A وD وE. وحدها {B,C} تغطي الجميع. لا نقدم هذا الاختيار على أنه قاعدة عامة لاختيار جارين للرأس الأعلى درجة؛ الشهادة تعتمد على حواف هذا المدخل.
عدم إمكان الحذف لا يعيد اختيار البداية
المجموعة المسيطرة الدنيا من حيث الاحتواء لا تضم مجموعة مسيطرة أصغر ضمنها؛ كل مجموعة ذات أقل عدد دنيا بهذا المعنى، ولا يلزم العكس. [2] سنفصل عدم إمكان الحذف عن أقل عدد بين جميع الاختيارات.
اختبر {A,F,G}. بعد حذف A تبقى {F,G}: يغطي F نفسه وB، ويغطي G نفسه وC، فتكون A وD وE بلا تغطية. بعد حذف F تبقى {A,G} ويظل F وحده غير مغطى؛ وبعد حذف G تبقى {A,F} ويظل G وحده غير مغطى.
إذن كل حذف منفرد من هذه المجموعة يفشل. يكفي ذلك أيضًا لرفض أي مجموعة جزئية أصغر منها: المجموعة الجزئية تحذف اسمًا واحدًا على الأقل، وتكون محتواة في المجموعة التي فشلت بعد حذف ذلك الاسم. حذف المزيد لا يضيف رأسًا مغطى جديدًا.
هذا هو سبب كفاية شهادة الحذف للاحتواء، وليس شهادة للأقل عددًا. الوصول إلى {B,C} يحذف A وF وG ويضيف B وC. التغيير يقارن مجموعتين لا تحتوي إحداهما الأخرى، فيخفض العدد من3 إلى2 دون مخالفة نتيجة اختبارات الحذف.
الصورة الداخلية ستعرض اختيار A وحده والاسمين F وG اللذين لا يغطيهما، ثم اختيار {F,G} بعد إسقاط A من الثلاثية. يظل A وD وE غير مغطاة في الحالة الثانية؛ وجود خطوط بين رؤوس غير مختارة لا يعطي تغطية تلقائية.
لو بدأت طريقة بـA ثم سمحت لاحقًا بإلغائه، فقد تصل إلى {B,C}. مثالنا يرفض ضمان أمثلية الاختيار مع الاحتفاظ به، ولا يثبت أن كل برنامج يبدأ من أعلى درجة سيعجز عن تصحيح اختياراته.
| الاسم المحذوف من الثلاثية | المختاران الباقيان | الرؤوس غير المغطاة |
|---|---|---|
| A | F G | A D E |
| F | A G | F |
| G | A F | G |
نجمة ورؤوس معزولة تضبطان القاعدة
نأخذ نجمة بخمسة أسماء وحواف AB AC AD AE فقط. A درجته4، وكل ورقة درجتها1. اختيار A يغطي الخمسة، وأقل عدد1 لأن الرسم غير فارغ؛ هنا تنجح البداية ذات أكبر درجة حتى مع الإبقاء عليها.
هذا التحكم يبين أن فشل الاختيار في مثال السبعة ليس حكمًا على كل رسم. درجة الرأس تبين عدد من يغطيهم أولًا، لكنها لا تسجل كيف تتوزع احتياجات الرؤوس التي يتركها خارج تغطيته.
ولثلاثة أسماء X Y Z دون حواف، تكون الدرجات كلها0. كل مختار يغطي نفسه فقط، فلا بد من اختيار الثلاثة. حذف أي اسم يتركه غير مغطى. لا نختلق جارًا للرأس المعزول ولا نحذف اسمه من مجموعة المدخلات.
لا نشترط اتصال المختارين، ولا ننقل هذه النتيجة إلى صيغة تطلب جارًا مختارًا لكل رأس حتى لو كان مختارًا. إذا تغير هذا الشرط، فتلك مسألة أخرى تحتاج تعريفًا وفحصًا جديدين. أمثلتنا بلا تكاليف أو أوزان أو اتجاه للحواف.
قارن التغطية والعدد والشرط الإضافي
للمثال ذي سبعة أسماء128 مجموعة محتملة. فحصنا جميعها، وحسبنا الجزء المغطى بالاتحاد المباشر للجيران مع الرؤوس المختارة، ثم حسبناه مستقلًا بأقنعة ثنائية تمثل الأسماء المغطاة. تطابقت المجموعات المغطاة، لا مجرد أحجامها.
وسجلنا جميع المجموعات المسيطرة، وحددنا أقل عدد، ثم أقل عدد عند اشتراط أن تضم A. الأول2 والثاني3. وفحصنا الدنيا من حيث الاحتواء بطريقتين: رفض كل حذف منفرد، ورفض كل مجموعة جزئية مسيطرة أصغر؛ تطابقت النتيجتان.
للمراجعة الإضافية، أخذنا1024 رسمًا مسمى على خمسة أسماء. لكل مدخل32 مجموعة، فالمجموع32768 اختبارًا. تشمل المدخلات الرسوم غير المتصلة والمعزولة، ونراجع فيها السيطرة العادية بالتعريف نفسه.
في كل مدخل اخترنا الرأس الأكبر درجة، وعند التعادل أسبق اسم في ترتيب الأسماء المثبت. وجدنا20 مدخلًا يصبح أقل عدد مسيطر فيها أكبر إذا اشترطنا إبقاء ذلك الرأس. ووجدنا675 مدخلًا لها مجموعة دنيا من حيث الاحتواء أكبر من أقل عدد ممكن.
هذه أعداد الحصر على خمسة أسماء وفق قاعدة تعادل محددة، وليست نسبة لكل الرسوم أو اختبارًا لأداء برنامج. البرهان على مثالنا ذي السبعة يوضح الفشل دون الاعتماد على نتائج ذلك الحصر، ولم نشغل برنامجًا مرجعيًا أو نفحص بيانات شبكة حقيقية.
للمراجعة، اكتب المختارين ثم اتحادهم مع الجيران. افحص أسماء غير المغطين قبل النظر إلى العدد. بعد إثبات صلاحية المجموعة، قارن حجمها بحد أدنى؛ وإذا ألزمت نفسك باختيار أول، فصرح هل يمكن إلغاؤه. نجاح حذف الزوائد وحده لا يحسم المقارنة مع مجموعات جديدة.
اقرأ أيضًا: استرجاع الرسوم البيانية: نوع العلاقة واتجاهها
اقرأ أيضًا: أنواع الرسم البياني: اختر الشكل الذي يجيب عن السؤال
المراجع
أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.