هيمنة الحواف: لماذا تكفي مطابقة أصغر؟

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

لأن هيمنة الحواف تطلب أن تلامس كل حافة حافةً مختارة، ولا تطلب أكبر عدد من الأزواج المستقلة أو لمس كل رأس. في الدورة A-B-C-D-E-F-A، الاختيار AB DE يهيمن على الحواف الست بحافتين؛ وهو مطابقة لا تقبل الإضافة، بينما أكبر مطابقة حجمها 3.

• مجموعة هيمنة الحواف تختار حواف تجعل كل حافة متروكة تشترك في طرف مع حافة مختارة. [1] نفترض رسمًا محدودًا وغير فارغ وبسيطًا وغير موجه وبلا حلقات أو أوزان؛ الحافة المختارة محسوبة مهيمنًا عليها أيضًا لأنها تلمس نفسها.
• المطابقة تمنع اشتراك حافتين في رأس؛ أكبر مطابقة تملك أكبر عدد ممكن، أما المطابقة القصوى فلا تقبل تكبيرها بإضافة حافة واحدة، وقد تكون أصغر من الأكبر. [2] نستخدم «لا تقبل الإضافة» لتوضيح معنى القصوى، ونفصل هذا من تقليل حجم المجموعة المهيمنة.
• في الدورة C6 بحواف AB AF BC CD DE EF، تهيمن AB على AB BC AF، وDE على DE CD EF. الاختيار AB DE مطابقة بحجم 2؛ لا يمكن إضافة حافة، لكنه أصغر من المطابقة AB CD EF بحجم 3.
• حافة منفردة في C6 تلمس ثلاث حواف فقط، فلا تكفي للست. AB DE يثبت أن الحد الأدنى للهيمنة 2. ولأي مطابقة، غياب حافة يمكن إضافتها يكافئ أن كل حافة تلامس المختار؛ هذه حجة عامة، ولا تجعل كل مجموعة مهيمنة مطابقة.
• المسار AB BC CD له هيمنة دنيا وحيدة BC بحجم 1، مقابل أكبر مطابقة AB CD بحجم 2. في C4 بحواف AB AD BC CD، الاختيار AB BC يهيمن على الأربعة لكنه ليس مطابقة، لأن طرف B مشترك.
• يمكن بقاء C وF بلا حافة مختارة في C6. إضافة رأس معزول D إلى المثلث لا تغير هيمنة الحواف؛ كل حافة واحدة من الثلاث تكفي. وإذا خلت قائمة الحواف على أربعة رؤوس، فالمجموعة الفارغة تكفي للهيمنة، ولا ندعي أنها تصل إلى الرؤوس.
• حصرنا 64 قائمة على أربعة أسماء:729 مجموعة مرشحة، و 570 مهيمنة، و 304 مطابقات منها 145 لا تقبل الإضافة، و 133 مجموعة هيمنة دنيا. راجعنا التكافؤ 304 مرات والاتحاد المستقل 64 مرة؛ ظهرت 30 فجوة بين الأكبر والأصغر الذي لا يقبل الإضافة. اتفاق حجمي الهيمنة الدنيا وأصغر مطابقة قصوى في 64 مدخلًا ملاحظة محدودة، لا مبرهنة عامة أو ادعاء سرعة.

الشرط على كل حافة، والاختيار مجموعة حواف

مجموعة هيمنة الحواف تختار حواف تجعل كل حافة متروكة تشترك في طرف مع حافة مختارة. [1]

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

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

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

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

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

حافتان تلمسان الحواف الست في الدورة

نأخذ دورة كاملة A-B-C-D-E-F-A، وحوافها AB وBC وCD وDE وEF وAF. لا توجد أقطار مثل CF أوAD. اختر AB وDE فقط؛ أطراف الأولى A وB، وأطراف الثانية D وE، فلا تشتركان في رأس.

الحافة AB تهيمن على نفسها، وعلى BC عبر B، وعلى AF عبر A. والحافة DE تهيمن على نفسها، وعلى CD عبر D، وعلى EF عبر E. هذه القوائم تجمع الحواف الست كلها دون أن نختار الأربع المتروكة.

إذن AB DE مجموعة مهيمنة بحجم 2، وهي مطابقة أيضًا. لكن الرأس C لا يظهر طرفًا لحافة مختارة، وكذلك F. الوصول إلى الحافتين BC وCD عبر طرفيهما الآخرين يكفي للهيمنة، دون اختيار حافة تنتهي في C.

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

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

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

لماذا لا تكفي حافة واحدة في هذه الدورة؟

كل رأس في C6 له حافتان. إذا اخترنا حافة واحدة مثل AB، فهي تلمس AB نفسها وحافة أخرى عند A وهي AF وحافة أخرى عند B وهي BC؛ ثلاثة فقط. تبقى CD وDE وEF لا تلامس AB.

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

إذن الحجم 1 مستحيل للهيمنة، والمجموعة الفارغة مستحيلة أيضًا ما دامت هناك حواف. الاختيار AB DE يحقق الحجم 2، فيثبت أن 2 هو الحد الأدنى. هذه حجة تمنع الأقل مع شاهد يبلغ الحد، وليست مجرد عرض مجموعة صالحة.

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

تغيير الهدف إلى أكبر مطابقة يعطي 3 بدل 2. وتغيير الشرط إلى الوصول لكل رأس يستبعد AB DE أصلًا لأنه يترك C وF. اكتب الشرط والهدف قبل المقارنة العددية؛ الحجم 2 قد يكون أمثلًا لسؤال وغير صالح لسؤال آخر.

للمطابقة: عدم قبول الإضافة يكافئ هيمنة الحواف

المطابقة تمنع اشتراك حافتين في رأس؛ أكبر مطابقة تملك أكبر عدد ممكن، أما المطابقة القصوى فلا تقبل تكبيرها بإضافة حافة واحدة، وقد تكون أصغر من الأكبر. [2]

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

إذا كانت M لا تقبل الإضافة، فلا توجد حافة متروكة بعيدة عن جميع أطرافها. إذن كل حافة متروكة تشترك في طرف مع حافة من M، فتكون M مجموعة هيمنة حواف.

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

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

كل مطابقة أكبر لا تقبل الإضافة، لأن إضافة حافة كانت ستعطي مطابقة أكبر منها. لكن العكس يفشل في C6، حيث AB DE لا يقبل الإضافة مع وجود AB CD EF الأكبر. الوصول إلى اختيار لا يقبل الإضافة ليس شهادة بأن حجمه هو الأكبر أو الأصغر.

المسار يصغر أكثر، والحواف المتجاورة قد تهيمن

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

الحافة AB وحدها لا تهيمن على CD، وCD وحدها لا تهيمن على AB. لذلك BC هي مجموعة الهيمنة الدنيا الوحيدة بحجم 1. ومع ذلك، أكبر مطابقة هي AB CD بحجم 2؛ عدم قبول الإضافة لم يساوِ الأكبر.

خذ الآن الدورة الرباعية A-B-C-D-A، بحواف AB AD BC CD. اختر AB وBC. الأولى تهيمن على AD عند A، والثانية على CD عند C، والحافتان المختارتان محسوبتان أيضًا. إذن المجموعة تهيمن على الحواف الأربع.

لكن AB BC ليست مطابقة لأنها تشترك في B. الحافة المنفردة في الدورة الرباعية تترك الحافة المقابلة بلا هيمنة، لذا الحجم الأدنى للهيمنة 2. المجموعة المتجاورة مثال صالح أدنى مع أنه غير مستقل.

يمكن أيضًا اختيار AB CD أوAD BC في الدورة الرباعية للحصول على مطابقة مهيمنة بحجم 2. اتفاق الحجم لا يجعل كل مجموعة دنيا مطابقة، ولا يجعل عدد المجموعات المستقلة مساويًا لعدد المجموعات المهيمنة.

الصورة الداخلية تعرض المسار مع BC وحدها، والدورة الرباعية مع AB BC المتجاورتين. قوائم الحواف كاملة؛ لا نخفي حافة متروكة حتى تبدو مجموعة غير كافية صالحة.

الرأس المعزول لا يضيف حافة تحتاج إلى الهيمنة

في المثلث A B C، الحواف AB AC BC. كل حافة واحدة تلامس الحافتين الأخريين، فتكون مهيمنة. المجموعة الفارغة لا تكفي، لذلك الحد الأدنى 1، وله ثلاثة اختيارات بحسب الحافة المفردة.

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

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

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

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

حصر الملامسة يراجع المجموعات نفسها

ثبتنا أربعة أسماء A B C D وستة أزواج محتملة، وراجعنا 2^6=64 قائمة حواف. لكل قائمة فحصنا كل مجموعة جزئية من الحواف، ثم اختبرنا أن كل حافة في الرسم تتقاطع في طرف مع واحدة من المختار.

بلغ مجموع المرشحات 729، ومجموع المجموعات المهيمنة 570، وإجمالي مجموعات الهيمنة الدنيا 133. هذه مجاميع على المدخلات الأربعة والستين، لا أعدادًا للدورة السداسية؛ الأخيرة ضبط مستقل من ستة رؤوس.

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

حصرنا المطابقات بطريقة تترك رأسًا حرًا أو تقرنه بجار حر. بلغ مجموعها 304، منها 145 لا تقبل إضافة حافة. قارنّا شرط الإضافة بعضوية المطابقة في مجموعات الهيمنة؛ اتفق الحكمان في المطابقات 304 كلها.

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

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

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