مبرهنة ديراك: فشل شرط الدرجة لا ينفي الدورة الهاملتونية

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

لأن شرط ديراك كافٍ للوجود، وليس مطلوبًا في كل رسم يملك دورة. دورة الرؤوس الستة A→B→C→D→E→F→A لها أقل درجة2، دون حد3، لكنها موجودة بالفعل. أما مثلثان يصل بينهما CD وحدها فأقل درجة فيهما2 أيضًا ولا دورة شاملة؛ فشل الشرط وحده لا يميز الحالتين.

• الدورة الهاملتونية تعود إلى البداية وتزور كل رأس مرة واحدة. [2] نكرر اسم البداية في كتابة الإغلاق فقط. نثبت ستة رؤوس A وB وC وD وE وF، ورسمًا بسيطًا غير موجه بلا حلقات ذاتية أو حواف مكررة.
• لأن n=6، يصبح حد ديراك3: يلزم أن تكون درجة كل رأس3 أو أكثر حتى نستخدم ضمان المبرهنة. [1] لا تكفي درجة رأس واحد ولا متوسط الدرجات؛ نفحص أقل درجة δ(G).
• في رسم الدورة ذات الحواف AB وBC وCD وDE وEF وAF، درجات الرؤوس كلها2، ومع ذلك المسار المغلق المكتوب يزور الستة. هذا شاهد على أن نجاح شرط الدرجة ليس لازمًا لوجود الدورة.
• المثلثان ABC وDEF متصلان عبر CD فقط، ودرجاتهما(2,2,3,3,2,2). أي دورة تزور الجهتين تحتاج عبورًا وعودة، لكن الوصلة الوحيدة لا تسمح بالعودة دون تكرار. لا توجد دورة هاملتونية رغم الاتصال وأقل درجة2.
• إضافة AF إلى المثلثين تتيح A→B→C→D→E→F→A. تبقى درجة B وE تساوي2، فيظل شرط ديراك غير متحقق. الإضافة أصلحت وجود الدورة قبل أن تحقق حد الدرجة في كل الرؤوس.
• بعد إضافة BE أيضًا تصير درجات الرؤوس الستة3، فينطبق ضمان ديراك. والدورة نفسها ما زالت صحيحة؛ لا تحتاج استعمال AC أوDF أوBE. وجود الدورة لا يعني أقصر رحلة موزونة أو المرور على كل حافة.

اقرأ عدد الرؤوس وأقل درجة

نعمل على ستة رؤوس مختلفة A وB وC وD وE وF. الحافة AB تصل A بـB دون اتجاه، ولذلك BA تعني الحافة نفسها. الأسماء لا تتغير بين رسوم المقارنة، لكن مجموعات الحواف ستتغير.

الدورة الهاملتونية دورة مغلقة تزور كل رأس في الرسم مرة واحدة. [2] في كتابة A→B→C→D→E→F→A، تظهر A في النهاية لإغلاق الدورة عند نقطة البداية؛ الأسماء الستة قبل الإغلاق مختلفة.

تعطي مبرهنة ديراك شرطًا كافيًا: في الرسم البسيط ذي n≥3 رؤوس، إذا كانت درجة كل رأس لا تقل عن n/2، وجدت دورة هاملتونية. [1] درجة الرأس هنا عدد حوافه، وليست رقمًا حسب موضعه في الرسم.

نكتب δ(G) لأقل درجة بين الرؤوس كلها. في أمثلتنا n=6، ومن ثم n/2=3. لكي نستخدم ضمان المبرهنة يجب أن يكون δ(G)≥3. عبارة «بعض الرؤوس درجتها3» أضعف من هذا المطلوب.

رسم يملك دورة رغم أقل درجة2

نبدأ بالحواف AB وBC وCD وDE وEF وAF فقط. لكل رأس جاران: A له B وF، وB له A وC، ثم نتابع على الحلقة حتى F الذي له E وA. درجات الستة هي(2,2,2,2,2,2).

الرسم نفسه يعرض الدورة A→B→C→D→E→F→A. كل انتقال حافة موجودة، وكل واحد من الرؤوس الستة يظهر مرة قبل العودة إلى A. لا نحتاج اختراع اتصال لإغلاقها؛ AF موجودة ضمن الحواف الست.

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

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

الرسم الآخر متصل لكن الوصلة الوحيدة تمنع الدورة

نبني مثلث ABC بالحواف AB وBC وAC، ومثلث DEF بالحواف DE وEF وDF، ثم نضيف CD بينهما. لدينا7 حواف، ويستطيع أي رأس الوصول إلى أي آخر عبر CD، لذلك الرسم متصل.

درجات A وB وC وD وE وF بالترتيب هي(2,2,3,3,2,2). أقل درجة2، تمامًا كما في رسم الدورة السابقة، رغم أن C وD صارت درجتاهما3. هذا مثال آخر يفشل فيه حد ديراك.

أي دورة تزور رؤوس المثلثين تحتاج أن تعبر من جهة ABC إلى جهة DEF، ثم تعود إلى الجهة الأولى لتغلق عند البداية. الحافة الوحيدة بين الجهتين هي CD، فلا توجد وصلة ثانية للعودة.

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

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

أضف AF: الدورة تظهر قبل نجاح حد الدرجة

نضيف AF إلى المثلثين المتصلين عبر CD، ونبقي الحواف السبع القديمة. أصبح لدينا وصلة ثانية بين الجهتين: CD وAF. ويمكن أن تعبر الدورة إلى المثلث الثاني عبر الأولى، ثم تعود عبر الثانية.

المسار A→B→C→D→E→F→A صحيح الآن. انتقالاته AB وBC وCD وDE وEF وAF كلها موجودة، وأسماؤه قبل الإغلاق تضم الرؤوس الستة دون تكرار. الصورة الداخلية تميز هذه الحواف الست بالذهب.

درجات الرسم المعدل هي(3,2,3,3,2,3). ارتفعت A وF فقط عند إضافة AF، وبقيت B وE بدرجة2. إذن δ(G)=2، وما زال شرط ديراك غير متحقق، مع أن الدورة أصبحت موجودة.

لا تستعمل الدورة المكتوبة لإثبات الوجود في الرسم السابق؛ AF لم تكن فيه. الإضافة تغير الرسم بالفعل، وليست إعادة ترتيب للأسماء على الحواف القديمة. أما الحافتان AC وDF فتظلان موجودتين دون دخولهما في الدورة المختارة.

أضف BE: كل رأس يبلغ الحد3

نضيف BE أيضًا، فيرتفع عدد الحواف من8 إلى9. كانت B وE وحدهما بدرجة2، فتزيد درجة كل منهما1، وتصبح درجات الرؤوس بالترتيب(3,3,3,3,3,3).

الآن n=6 وδ(G)=3، فيتحقق δ(G)≥n/2 وينطبق ضمان ديراك. لدينا في الوقت نفسه الدورة A→B→C→D→E→F→A التي بقيت حوافها كلها بعد الإضافة. الضمان والشاهد المباشر متفقان هنا.

المتوسط لا يحل محل أقل درجة. في الرسم الذي أضفنا إليه AF وحدها، مجموع الدرجات16، لكن وجود أربعة رؤوس بدرجة3 لا يعالج بقاء B وE بدرجة2. نراجع كل رأس قبل استعمال المبرهنة.

الجدول يقارن الرسوم الأربعة. أول ثلاثة لا تستوفي حد الدرجة؛ اثنان منها يملكان دورة، والثالث لا يملكها. الرسم الرابع يستوفي الحد ويملك دورة، كما تضمن المبرهنة.

ميز فشل الفرض من نفي النتيجة

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

في مثال المثلثين الأصلي، الوصلة الوحيدة CD تمنع الدورة الشاملة. وبعد إضافة AF زال هذا العائق وظهرت دورة، رغم بقاء أقل درجة2. هذا يوضح خطأ تحويل شرط كافٍ إلى اختبار يقبل كل الحلول الممكنة ويرفض كل البقية.

الدورة لا تطلب استعمال كل حافة في الرسم. بعد الإضافتين توجد9 حواف، لكن الدورة المكتوبة تستعمل6؛ تترك AC وDF وBE. السؤال عن زيارة كل رأس مرة واحدة يختلف عن سؤال اجتياز الحواف كلها مرة واحدة.

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

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