السيطرة المستقلة: هل أصغر مسيطر يحققها؟

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

لا في هذا المثال؛ B وC يغطيان الرؤوس الستة، لكن الحافة BC تمنع اختيارهما معًا في مجموعة مستقلة. أصغر مسيطر مستقل هو {B,E,F} أو {A,C,D} بحجم 3. مجموعة الأوراق {A,D,E,F} مستقلة ومسيطرة أيضًا بحجم 4، لكنها لا تحقق الأصغر.

• المجموعة المسيطرة المستقلة تحقق السيطرة والاستقلال معًا؛ وأصغر حجم لها هو عدد السيطرة المستقلة. وهي تكافئ مجموعة مستقلة لا تقبل إضافة رأس. [1] المجموعة المستقلة العظمى بالاحتواء لا تقبل إضافة رأس مع بقاء الاستقلال. أما الكبرى بالحجم فتضم أكبر عدد ممكن؛ كل كبرى عظمى، والعكس لا يلزم. [2]
• ثبت الحواف AB BD BC CE CF فقط. B وC متجاوران، ولكل منهما ورقتان. باختيارهما تغطى الرؤوس الستة؛ لا يكفي رأس واحد لأن أعلى درجة 3، فيغطي الرأس نفسه وثلاثة جيران على الأكثر.
• إذا اخترنا B مستقلاً، استُبعد C، فوجب اختيار E وF نفسيهما. وباختيار C بدلًا منه نحتاج A وD. إذا تركنا المركزين، نحتاج الأوراق الأربع. إذن أصغر سيطرة مستقلة 3، وليست السيطرة العادية 2.
• المجموعات المستقلة المسيطرة كلها هنا هي {B,E,F} و{A,C,D} و{A,D,E,F}، بأحجام 3 و3 و4. الأخيرة أكبر مستقلة، لكن الثلاثيتين لا تقبلان إضافة أيضًا؛ عدم إمكان الإضافة لا يساوي أكبر حجم.
• لمجموعة مستقلة، وجود رأس خارجها بلا جار مختار يعني أننا نستطيع إضافته. لذلك عدم إمكان أي إضافة يكافئ السيطرة. وحذف رأس مختار من مسيطر مستقل يترك ذلك الرأس بلا تغطية، لأن أي مختار آخر ليس جاره.
• في النجمة، المركز وحده والأوراق الأربع مسيطران مستقلان؛ الأصغر 1 والأكبر مستقلة 4. في مثلث يكفي رأس واحد، وفي ثلاثة رؤوس معزولة يجب اختيار الثلاثة. هذه ضوابط، ولا نفرض اتصال المختارين.
• فحصنا جميع المجموعات الـ64 للمثال، و32768 مجموعة في الرسوم الـ1024 على خمسة رؤوس مسماة. اتفق فحص الحواف والتغطية مع فحص بتات مستقل؛ التوافق محدود بالمدخلات، وحجة الإضافة منفصلة.

شرطان على مجموعة رؤوس واحدة

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

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

الشرطان يخصان الرؤوس المختارة نفسها. يجوز أن تتجاور رؤوس غير مختارة، أو أن يتصل مختاران بطريق يمر بغير المختارين؛ الممنوع هو حافة مباشرة بين مختارين. لا نختار حوافًا لتغطية حواف أخرى.

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

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

رأسان يكفيان للسيطرة العادية

ثبت أسماء A B C D E F والحواف AB BD BC CE CF. لا توجد أي حافة أخرى. B مجاور لـA وC وD؛ وC مجاور لـB وE وF. الرؤوس A وD وE وF أوراق، لكل منها جار واحد.

اختيار {B,C} يغطي الجميع: B يغطي نفسه وA وC وD، وC يغطي نفسه وB وE وF. اتحاد التغطيتين هو الرؤوس الستة. لا مشكلة في الحافة BC عند طلب السيطرة العادية وحدها.

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

لكن {B,C} ليست مستقلة؛ الحافة BC تصل مختارين. ظهور جميع الرؤوس مغطاة في الصورة لا يصلح دليلًا على الشرط الثاني. علينا فحص كل حافة بين المختارين بجانب فحص التغطية.

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

ثلاث حالات تحصر السيطرة المستقلة

ابدأ باختيار B مع الحفاظ على الاستقلال. لا نستطيع اختيار A أوC أوD بسبب AB وBC وBD. وما دام C غير مختار، لا تغطى E إلا باختيار E نفسها، ولا F إلا باختيار F نفسها؛ فكلتاهما لا تملك جارًا غير C.

إذن أي اختيار مستقل يضم B ويحقق السيطرة يجب أن يضم E وF. المجموعة {B,E,F} مستقلة، لأن BE وBF وEF ليست حواف، وتغطي الجميع. حجمها 3، ولا نستطيع اختصارها إلى رأسي B وورقة واحدة في هذا الفرع.

وبالتماثل في قائمة المدخل، إذا اخترنا C وجب استبعاد B وE وF، ثم اختيار A وD نفسيهما. المجموعة {A,C,D} مستقلة ومسيطرة بحجم 3. لم نستعمل هنا حجة درجة كبيرة أو إجراءً جشعًا؛ راجعنا الجار الوحيد لكل ورقة.

أما إذا لم نختر B ولا C، فيجب اختيار كل ورقة من A وD وE وF، لأن جارها غير مختار. الأوراق الأربع مستقلة وتغطي المركزين. اختيار المركزين معًا فرع ممنوع أصلًا بسبب BC.

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

والتقسيم نفسه يفسر لماذا {B,C} هي السيطرة العادية الوحيدة بحجم 2. إن اخترنا مركزًا واحدًا دون الآخر احتجنا الورقتين عند الآخر، فيصبح العدد 3 على الأقل؛ وإن تركنا المركزين احتجنا الأوراق الأربع.

لا تقبل إضافة، لكنها ليست الأكبر

المجموعة المستقلة العظمى بالاحتواء لا تقبل إضافة رأس مع بقاء الاستقلال. أما الكبرى بالحجم فتضم أكبر عدد ممكن؛ كل كبرى عظمى، والعكس لا يلزم. [2]

للمجموعة {B,E,F}، لا نستطيع إضافة A أوD لأنهما مجاوران لـB، ولا C لأنه مجاور لـB وE وF. إذن هذه الثلاثية عظمى بالاحتواء. ينطبق فحص مماثل على {A,C,D}.

ومع ذلك توجد مجموعة مستقلة أكبر، هي {A,D,E,F} بحجم 4. ليست توسعةً للثلاثية السابقة؛ إنها تغير أسماء المختارين، فتحذف المركز وتختار أوراق جانبه. عدم إمكان إضافة رأس إلى المجموعة الحالية لا يمنع وجود مجموعة أخرى أكبر.

ولا توجد مستقلة بحجم 5 في مثالنا. إن ضمت B، استبعدت A وC وD، فلم يبق معها إلا E وF؛ حجمها لا يتجاوز 3. وإن ضمت C، لم يبق معها إلا A وD. وإن تركت المركزين، لا تجد إلا الأوراق الأربع. لذلك أكبر حجم مستقل 4.

لماذا تكافئ العظمى بالاحتواء السيطرة مع الاستقلال؟ خذ مجموعة مستقلة S. إذا وجد رأس خارج S بلا جار داخلها، نستطيع إضافته ولا تنشأ حافة بين مختارين؛ إذن S ليست عظمى. وإذا كان لكل رأس خارجها جار فيها، منعت تلك الحافة إضافته؛ إذن لا تقبل إضافة.

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

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

ضوابط توضح معنى العدد الأصغر

للنجمة ذات المركز A والأوراق B C D E، المجموعة {A} مستقلة ومسيطرة، ولا يمكن إضافة ورقة إليها. كما أن {B,C,D,E} مستقلة ومسيطرة ولا يمكن إضافة المركز إليها. أقل سيطرة مستقلة 1، وأكبر مستقلة 4؛ كلتاهما عظمى بالاحتواء.

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

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

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

أما المسار ذو الحواف AB BC CD، فيحقق اختيار {A,C} السيطرة والاستقلال بحجم 2. لا رأس منفرد يغطي الأربعة، ولا يمكن جمع ثلاثة رؤوس مستقلة في هذا المسار؛ فتتفق الأحجام عند 2. اختلاف القيد لا يفرض زيادة في كل مدخل.

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

افحص التغطية وحواف المختارين منفصلتين

حصرنا جميع المجموعات الـ64 على رؤوس المثال الستة. لكل مجموعة سجلنا التغطية، ووجود حافة بين مختارين، وإمكان إضافة رأس خارجي مع بقاء الاستقلال. وجدنا السيطرة العادية الدنيا {B,C}، والمجموعات المستقلة المسيطرة الثلاث المذكورة.

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

كررنا الفحوص على جميع الرسوم البسيطة على خمسة رؤوس مسماة: توجد 10 حواف ممكنة، فيكون 2¹⁰=1024 رسمًا، ولكل رسم 2⁵=32 مجموعة؛ الإجمالي 32768. اتفقت مساواة «مستقلة ومسيطرة» مع «مستقلة ولا تقبل إضافة» في جميع هذه الحالات.

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

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

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