اتصال الرؤوس: هل يصمد إذا صمدت الحواف؟

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

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

• اتصال الرؤوس أقل حجم لقطع رؤوس. [1] نختار هنا رسومًا بسيطة غير موجهة وغير كاملة، ذات ثلاثة رؤوس على الأقل، ونطلب فصلًا حقيقيًا يبقي رأسين أو أكثر؛ اصطلاحات النتيجة ذات الرأس الوحيد خارج أمثلتنا.
• قطع الرؤوس في الرسم المتصل يحذف الأسماء المختارة وحوافها المتصلة بها؛ وإذا كفى رأس واحد كان رأس مفصل. [2] حذف حافة وحدها يبقي طرفيها، فلا نساوي وحدتي العد.
• نأخذ K4 على ABCD وآخر على AEFG، مع A مشترك فقط: سبعة رؤوس واثنتا عشرة حافة. حذف A يترك المثلثين BCD وEFG، لذلك κ=1؛ لكن أصغر حذف حواف3، لا1.
• للمكعب AB AC AE BD BF CD CG DH EF EG FH GH، حذف A وحده يبقي السبعة متصلين. ويمكن نقل أي زوج محذوف إلى AB أوAD أوAH بتبديل ثنائي يحفظ الحواف؛ الباقي في الحالات الثلاث متصل بشواهد معلنة.
• إذن حذف أقل من ثلاثة رؤوس لا يفصل المكعب. حذف B وC وE يعزل A، ويترك D وF وG متصلة عبر H؛ خمسة رؤوس وثلاث حواف ومكونان، فيصبح κ=3.
• لا نبقي A المحذوف كرأس معزول في مثال القطعتين. بالمقابل A في ناتج حذف جيرانه من المكعب لم يُحذف، فيدخل كمكون منفرد. ولا نستنتج صمود الرؤوس من أعلى درجة أو من موضع الرأس في الصورة.
• راجعنا1023 مدخلًا غير كامل على خمسة رؤوس عبر26598 مجموعة حذف تبقي رأسين أو أكثر. وللمثالين الرئيسيين367 مجموعة، مع28 خريطة لأزواج المكعب؛ هذا نطاق محدود، دون تشغيل أدوات المرجع أو قياس أداء.

احسب الرؤوس المحذوفة، واحذف حوافها أيضًا

اتصال الرؤوس أقل حجم لقطع رؤوس. [1] سنرمز إليه بـκ، وإلى اتصال الحواف بـλ. لا يعني اختلاف الحرفين مجرد اسمين للعدد نفسه؛ عملية الحذف مختلفة.

قطع الرؤوس في الرسم المتصل يحذف الأسماء المختارة وحوافها المتصلة بها؛ وإذا كفى رأس واحد كان رأس مفصل. [2] بعد حذف A لا نحتفظ بدائرته أو بحافة كانت تنتهي عنده. أما حذف AB وحدها فلا يخرج A أوB من قائمة الرؤوس.

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

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

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

رأس مشترك يجمع قطعتين كاملتين

نثبت ABCD بالحواف AB AC AD BC BD CD، ونثبت AEFG بالحواف AE AF AG EF EG FG. الرأس A هو الاسم نفسه في القطعتين، لا رأسان وصلنا بينهما. بقية الأسماء مختلفة، ولا توجد حافة بين BCD وEFG.

المجموع سبعة رؤوس واثنتا عشرة حافة. درجة A تساوي6، لأن له B وC وD وE وF وG جيرانًا؛ وكل اسم آخر درجته3. الأصل متصل، إذ تصل طرق بين القطعتين عبر A.

احذف A. تخرج الحواف AB AC AD AE AF AG، وتبقى BC BD CD EF EG FG. الرؤوس الباقية B C D E F G، والمكونان مثلث BCD ومثلث EFG. لا نضيف A إلى الجدول كرأس معزول: لقد حذفناه.

حذف رأس واحد نجح، فلدينا κ≤1. وحذف صفر رؤوس يترك الأصل المتصل كما هو، فلا ينجح؛ إذن κ≥1، والنتيجة κ=1. كثرة جيران A لا تمنع كونه موضع الفصل؛ جميع الطرق بين القطعتين تمر به.

إذا حذفنا B بدلًا من A، بقي المثلث ACD متصلًا بقطعة AEFG عبر A، فلا يحصل الفصل. لا يكفي القول إن أي رأس بدرجة3 سيعطي النتيجة نفسها؛ الاسم وموقعه في قائمة الاتصال مهمان.

لماذا يحتاج حذف الحواف إلى ثلاث في الأصل نفسه؟

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

في قطعة K4 المنقسمة، إذا كان جانب منها يضم r رؤوس، فالحواف العابرة r(4−r). القيم عند r=1 أو2 أو3 هي3 و4 و3. إذن القطعة المنقسمة وحدها تفرض ثلاث حواف عابرة على الأقل.

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

لحصول فصل بثلاث، احذف AB وBC وBD، وهي حواف B كلها. يبقى B معزولًا، لكن الرؤوس السبعة باقية لأننا حذفنا الحواف فقط. إذن λ≤3، ومع الحد السفلي نحصل على λ=3.

قارن العمليتين: حذف A هو رأس واحد وست حواف معه، بينما عزل B بالحواف هو ثلاث حواف دون حذف رأس. لا يصح قسمة العدد6 على درجة معينة لاستنتاج κ؛ الحد الأدنى يُقاس بمجموعات الأسماء التي تفصل البقية.

المكعب يبقى متصلًا بعد حذف رأس أو زوج

نستعمل مكعب الأسماء A B C D E F G H بالحواف AB AC AE BD BF CD CG DH EF EG FH GH. ثلاثياتها بالترتيب000 و001 و010 و011 و100 و101 و110 و111؛ كل حافة تصل ثلاثيتين تختلفان في خانة واحدة.

بعد حذف A، تقدم الحواف BD BF CG EF FH GH شجرة تصل الأسماء السبعة الباقية. هي ست حواف أصلية لا تمس A، وشاهد اتصال يكفي: لا ندعي أنها كل حواف الناتج أو نحذف الحواف الأخرى لأجل تعريف العملية.

لأي زوج u وv، طبّق XOR بقناع u على جميع الأسماء الثنائية. يرسل u إلى000، ويرسل v إلى u⊕v، ويحفظ اختلاف خانة واحدة؛ والخريطة تقابل لأنها تنعكس بالقناع نفسه.

ثم بدّل ترتيب الخانات لتجعل خانات الاختلاف في أول المواضع المختارة. إذا اختلف الزوج في خانة أو اثنتين أو ثلاث، صار الزوج المحذوف000 مع001 أو011 أو111: أي A مع B أوD أوH. تبديل الخانات يحفظ التجاور أيضًا.

للحالات الثلاث نقدم شواهد الباقي: بعد AB الحواف CD CG EG FH GH؛ بعد AD الحواف BF CG EF FH GH؛ وبعد AH الحواف BD BF CG EF EG. كل قائمة من خمس حواف تصل الأسماء الستة الباقية، كما يتحقق الجدول.

الاتصال في الشواهد ينقل إلى أي زوج أصلي لأن الخريطة تحفظ الحواف والأسماء الباقية. كذلك ينقل حذف رأس واحد إلى حذف A بالقناع المناسب. ومع اتصال الأصل، لا يفصل المكعب حذف صفر أو رأس أو رأسين؛ لذلك κ≥3.

ثلاثة جيران محذوفون يقدمون الحد العلوي

احذف B وC وE من المكعب، وهي أسماء جيران A الثلاثة. A نفسه باقٍ، لكن حوافه AB وAC وAE اختفت لأن الطرف الآخر في كل منها محذوف. صار A معزولًا، لا رأسًا خرج من القائمة.

الأسماء الباقية A D F G H. الحواف الباقية DH وFH وGH فقط؛ تصل D وF وG بالرأس H في مكون من أربعة أسماء. مع A المنفرد يصبح عدد المكونات اثنين، وعدد الحواف3.

قدمنا قطعًا من ثلاثة رؤوس، فيكون κ≤3. ومع استبعاد كل حذف أصغر في القسم السابق نحصل على κ=3. الصورة تعرض النتيجة بأسماء خمسة، ولا ترسم B وC وE دوائر معزولة لأن هذه الأسماء محذوفة.

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

الجدول يجمع عدد الأسماء والحواف والمكونات بعد العمليتين المعلنتين. حذف A من القطعتين يعطي6 رؤوس و6 حواف ومكونين؛ حذف BCE من المكعب يعطي5 رؤوس و3 حواف ومكونين. نحدد العملية قبل مقارنة الأعداد.

ما فحصناه وما خرج من النطاق

على خمسة أسماء توجد1024 قائمة حواف، واستبعدنا الرسم الكامل الوحيد، فبقي1023 مدخلًا. لكل مدخل راجعنا26 مجموعة حذف تبقي رأسين أو أكثر: جميع32 مجموعة، سوى حذف الكل أو ترك رأس واحد في خمس حالات.

المجموع1023×26=26598. حسبنا مكونات الباقي باتباع الجيران وبطريقة مستقلة تجمع أطراف الحواف، واتفق التقسيمان. أخذنا أصغر حجم حذف يعطي أكثر من مكون؛ إذا كان المدخل منفصلًا أصلًا، فالحد الأدنى0، دون وصف الفارغة بأنها تزيد عدد المكونات.

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

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

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

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