اتصال الحواف: هل تكفي الدرجة الدنيا 3؟

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

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

• اتصال الحواف أقل عدد من الحواف يؤدي حذفها إلى فصل الرسم؛ وللرسم المنفصل القيمة0، وللمتصل ذي حافة جسر القيمة1. [1] نعمل برسم بسيط غير موجه وبلا أوزان، مع بقاء جميع الرؤوس عند الحذف.
• نصل K4 على ABCD وآخر على EFGH بحافة DE فقط: ثمانية رؤوس وثلاث عشرة حافة، والدرجات3 سوى D وE بدرجة4. حذف DE يترك مكونين، فلا تضمن الدرجة الدنيا3 اتصالًا مقداره3.
• نقسم الرؤوس إلى جانبين غير فارغين، ونعد الحواف العابرة بينهما. أصغر هذا العد يساوي أقل عدد حذف يفصل الرسم؛ أما عزل رأس بأقل درجة فيثبت الحد λ≤δ، ولا يثبت المساواة.
• المكعب ذو ثمانية رؤوس واثنتي عشرة حافة ودرجة3 عند كل رأس. للجانب الأصغر k من1 إلى4 رؤوس؛ عد درجاته يعطي حواف عابرة3k−2i، وبنيته الثنائية تفرض الحدود3 و4 و5 و4، فلا يكفي حذف حافتين.
• حذف AB وAC وAE في المكعب يعزل A ويبقي الرؤوس الثمانية، فيثبت الحد العلوي3؛ مع الحد السفلي تصبح λ=3. تغير مواضع الرسم أو تقاطعاته لا يغير مجموعة الحذف.
• حذف الجسر ليس حذف أحد طرفيه أو دمجهما. المسار الرباعي له اتصال حواف1، والدورة الرباعية2، وK4 ثلاثة؛ ورسمان K4 منفصلان لهما درجة دنيا3 لكن الاتصال0.
• راجعنا1024 مدخلًا مسمى على خمسة رؤوس عبر15360 تقسيمًا و59049 مجموعة حذف حواف. وفي المثالين الرئيسيين راجعنا254 تقسيمًا و12288 مجموعة حذف؛ هذه حدود فحص معلنة، لا جميع الأحجام أو قياس أداء.

نحذف حواف ونحتفظ بالرؤوس

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

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

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

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

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

ثلاثة جيران لا تمنع وجود وصلة وحيدة بين قطعتين

نأخذ ABCD ونصل كل زوج فيها: AB وAC وAD وBC وBD وCD. ونأخذ EFGH بالحواف EF وEG وEH وFG وFH وGH. لكل قطعة أربعة رؤوس وست حواف، ودرجة كل رأس داخلها3.

نضيف DE وحدها بين القطعتين. تصبح القائمة ذات13 حافة على ثمانية رؤوس. ترتفع درجة D وE إلى4، وتبقى درجات A وB وC وF وG وH تساوي3. لذلك δ=3، ولا نقول إن الرسم كله منتظم.

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

بعد حذف DE تبقى القطعتان كاملتين ومنفصلتين. قدمنا مجموعة حذف من حافة واحدة، فيكون λ≤1. ولأن الأصل متصل، لا يفصله حذف صفر حواف؛ إذن λ≥1، والجواب λ=1.

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

الأحمر في الصورة الرئيسية يحدد DE كمجموعة حذف، لا حافة محذوفة بالفعل في اللوحة الأصلية. الصورة الداخلية تعرض الناتج دونها؛ جميع الأسماء الثمانية باقية، ودرجة كل رأس في الناتج3 مع أن الرسم منفصل.

القطع يعد الحواف بين مجموعتين

اختر مجموعة S غير فارغة وغير شاملة لجميع الرؤوس. الجانب الآخر هو بقية الأسماء. الحافة عابرة إذا كان طرف واحد في S والآخر خارجها؛ لا نعد حافة داخل S أو داخل الجانب الآخر.

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

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

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

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

في مثال القطعتين، S=ABCD تعطي الحافة DE فقط، بينما عزل A يحتاج AB وAC وAD، أي3 حواف. مجموعة الرأس الواحد تقدم حدًا صحيحًا، لكنها لا تحقق الأصغر هنا. عند مقارنة التقسيمات لا نبدل شرط السؤال إلى عزل رأس معين.

لماذا يحتاج المكعب إلى ثلاث حواف على الأقل؟

نثبت حواف المكعب AB AC AE BD BF CD CG DH EF EG FH GH. لكل رأس ثلاثة جيران، والرسم متصل. يمكن أيضًا تسميته بالثلاثيات من000 إلى111، مع اختلاف خانة واحدة عند كل حافة، لكننا لا نحتاج حصر تماثلاته هنا.

للمكعب مجموعتان A D F G وB C E H، وكل حافة في القائمة تصل مجموعتين مختلفتين. خذ أي تقسيم غير فارغ، واختر الجانب الأصغر S؛ عدد رؤوسه k لا يتجاوز4 لأن عدد الرؤوس الكلي8.

لتكن i عدد الحواف داخل S. مجموع درجات رؤوس S هو3k؛ كل حافة داخلية تظهر عند طرفين فتسهم باثنين، وكل حافة عابرة تظهر عند طرف واحد. لذلك عدد العابرة يساوي3k−2i.

إذا كان داخل S عدد a من المجموعة الثنائية الأولى وعدد b من الثانية، فعدد الحواف الداخلية لا يتجاوز ab، حتى لو وصلنا كل زوج مختلف المجموعة. ومع a+b=k، يكون أكبر هذا العدد0 و1 و2 و4 حين k=1 و2 و3 و4 على الترتيب.

نعوض الحدود في3k−2i، فنحصل على حواف عابرة لا تقل عن3 و4 و5 و4 على الترتيب. كل تقسيم يحتاج ثلاثًا على الأقل، فيثبت λ≥3. عدّ الجيران وحده لم يثبت هذا؛ استعملنا درجات الجانب وبنية حوافه الداخلية.

ولإثبات إمكان الفصل بثلاث، احذف AB وAC وAE، وهي حواف A كلها. يصبح A معزولًا، وتبقى الرؤوس السبعة الأخرى في مكون متصل كما راجعنا من القائمة. إذن λ≤3، ومع الحد السفلي نحصل على λ=3.

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

ميّز أصغر حذف من عملية أخرى

في المسار AB BC CD، حذف BC يفصل AB عن CD، والأصل متصل؛ اتصال الحواف1. في الدورة AB BC CD AD، حذف حافة واحدة يترك مسارًا متصلًا، وحذف AB وAD يعزل A؛ اتصال الحواف2.

في K4، جانب أصغر من رأس واحد يملك3 حواف عابرة، وجانب من رأسين يملك4؛ لذا λ=3. وإذا أخذنا قطعتين K4 بلا DE أصلًا، كان الرسم منفصلًا قبل أي حذف، فالقيمة0 رغم δ=3.

الجدول يقارن عدد الحواف الأصلي والدرجة الدنيا واتصال الحواف وعدد المكونات قبل الحذف. اتصال0 في المدخل المنفصل لا يعني عدم وجود حواف: فيه12 حافة، لكن لا طريق بين القطعتين. لا نضيف وصلة خفية لتعويض الانفصال.

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

لا نقدم خوارزمية أسرع ولا نطبق حكم المكعب على كل رسم منتظم من الدرجة3. رسم القطعتين ليس منتظمًا، والمقارنة المقصودة هي تساوي الدرجة الدنيا. لتحديد λ في مدخل آخر، يلزم فحص القطع أو حجة أخرى تحدد الحدين.

المجموعات التي راجعناها وحدود العد

لكل رسم على خمسة أسماء، توجد15 طريقة لتقسيم الرؤوس إلى جانبين غير فارغين دون تكرار تبديل الجانبين. ثبتنا الاسم الأول في جانب واحد واستبعدنا الجانب الكامل:2^4−1=15. عبر1024 مدخلًا كان العدد15360 تقسيمًا.

راجعنا أيضًا جميع مجموعات الحذف لكل مدخل، وأعدنا حساب المكونات باتباع الجيران. المدخل الذي له m حافة يملك2^m مجموعات حذف، بما فيها الفارغة والكاملة. المجموع عبر المدخلات الخمسة59049، وليس1024 مضروبًا في عدد ثابت لكل مدخل.

اتفق أقل عدد حواف عابرة مع أقل حجم حذف يترك أكثر من مكون، بما في ذلك المدخلات المنفصلة وقيمة0. وراجعنا الحد λ≤δ. في المثالين ذوي الثمانية، توجد127 طريقة تقسيم لكل منهما، أي254 إجمالًا.

لرسم القطعتين مع DE ثلاث عشرة حافة، فمجموعات الحذف8192؛ وللمكعب اثنتا عشرة، فالمجموع4096. راجعناها كلها، أي12288، وراجعنا الضوابط الأخرى كذلك. لا تعني254 عدد مجموعات الحذف، ولا12288 عدد رسوم مختلفة.

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

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