طول الدورات: هل أقصر دورة هي أطولها؟

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

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

• طول أقصر دورة يسمى girth. [1] سنقيس الدورة بعدد حوافها في رسم بسيط غير موجه وبلا أوزان، عندما توجد دورة.
• طول أطول دورة يسمى circumference. [2] نختار الأكبر بين أطوال الدورات، وليس طول خط مرسوم أو قطر الرسم المحسوب من أقصر الطرق.
• الدورة البسيطة تمر برؤوس مختلفة ثم تعود إلى أولها. A→B→A يستعمل الحافة نفسها مرتين؛ ليس دورة من طول2 في نطاقنا. وجود وتر بين رأسين لا يبطل الدورة البسيطة.
• الأصل الخماسي حوافه AB BC CD AD AE BE. الدورات A→B→E→A وA→B→C→D→A وA→E→B→C→D→A أطوالها3 و4 و5؛ القائمة تحتوي ثلاث دورات فقط بعد إزالة تكرار البداية والاتجاه.
• المثلث يحقق الحد الأدنى3، والدورة الخماسية تحقق الحد الأعلى5 لأن الأصل خمسة رؤوس. الوتر AB لا يمنع استعمال الدورة الخماسية، ولا نضيف حواف جديدة لبنائها.
• المكعب له ثمانية رؤوس و12 حافة. تقسيمه إلى A D F G وB C E H يمنع الدورات الفردية، فتثبت الدورة الرباعية الأقصر4؛ شاهد يمر بالأسماء الثمانية يثبت الأطول8.
• قارنّا طريقتين مستقلتين لحصر الدورات في1024 رسمًا مسمى على خمسة رؤوس:37888 مرشح دورة و59049 مجموعة حواف. الشجرة بلا دورة؛ نعرض غياب القيمة بدل جعله طولًا صفريًا، ولا نعتمد اصطلاحًا عدديًا للحالة الخالية.

قائمتان من الاختيار، على الرسم نفسه

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

طول أطول دورة يسمى circumference. [2] نختار الأكبر بين أطوال الدورات، وليس طول خط مرسوم أو قطر الرسم المحسوب من أقصر الطرق.

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

في سلسلة A→B→C→A توجد ثلاث حواف وثلاثة أسماء مختلفة. أما A→B→A فهي ذهاب وعودة على AB، وليست دورة مقبولة هنا. لا نمد هذه العودة مرات كثيرة ثم نستعمل عدد خطواتها كدليل على دورة أطول.

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

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

ست حواف تعطي أطوالًا مختلفة

نثبت خمسة أسماء A B C D E وست حواف AB BC CD AD AE BE. الأربع الأولى تصنع دورة A→B→C→D→A، والحافتان AE وBE مع AB تصنعان مثلث A→B→E→A. لا توجد AC أوBD أوCE أوDE.

الدورة الثالثة هي A→E→B→C→D→A. كل انتقال فيها حافة من الأصل: AE ثم BE ثم BC ثم CD ثم AD. تمر بخمسة أسماء مختلفة وتعود إلى A، فطولها5. AB موجودة أيضًا، لكنها ليست خطوة في هذه السلسلة.

الدورات الثلاث أطوالها3 و4 و5. كتابة E→B→A→E لا تضيف مثلثًا جديدًا؛ إنها الدورة الأولى باتجاه معاكس وبداية مختلفة. عند عد الدورات هنا نعامل البداية والاتجاه المختلفين للقائمة نفسها كتكرار.

الصورة الرئيسية ترسم الأصل نفسه مرتين: الذهب يسارًا حواف المثلث ABE، ويمينًا حواف الدورة AEBCDA. الرمادي حافة موجودة تركناها خارج الشاهد. الرؤوس والحواف لا تتغير بين اللوحتين، ويظل العدد خمسة وستة.

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

الشاهد يحتاج حدًا يثبت قيمته

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

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

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

المثلث يحتوي كل الحواف بين أسمائه الثلاثة. لكن الدورة الخماسية لها الوتر AB، وفي ترتيبها تكون A وB غير متتابعين. وجوده قد يعطي دورة أقصر، وهو بالفعل جزء من المثلث، لكنه لا يلغي الدورة الخماسية البسيطة.

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

في المكعب: شاهدان وحدان مختلفان

نثبت أسماء المكعب A B C D E F G H وقائمة AB AC AE BD BF CD CG DH EF EG FH GH. الدرجة3 عند كل رأس، وعدد الحواف12. الصورة الداخلية تعرض القائمة نفسها مع شاهد أقصر يسارًا وأطول يمينًا.

قسّم الأسماء إلى A D F G وB C E H. كل حافة في القائمة تصل بين المجموعتين؛ لا توجد حافة داخل أي منهما. السير يبدل المجموعة مع كل خطوة. للعودة إلى البداية نحتاج عددًا زوجيًا من الخطوات، ولذلك لا توجد دورة فردية.

بما أن الدورة المقبولة طولها3 على الأقل، و3 فردي وممنوع هنا، فإن طولها4 على الأقل. الشاهد A→B→D→C→A له أربع حواف موجودة وأربعة أسماء مختلفة، فيثبت أن أقصر دورة طولها4.

الشاهد A→B→D→C→G→H→F→E→A يستعمل AB BD CD CG GH FH EF AE. يمر بالأسماء الثمانية مرة واحدة قبل العودة. طوله8، ولا يمكن لدورة بسيطة على ثمانية رؤوس أن تزيد على8؛ لذلك هو أطول دورة.

لا نستخدم تساوي الدرجة3 وحده لاستنتاج القيمتين. الحد الأدنى جاء من تبديل المجموعتين مع شاهد4، والحد الأعلى من عدد الأسماء مع شاهد8. الرسم المكعبي بخطوطه المطبوعة ليس قياس أطوال هندسية، ولا يؤدي تقاطع خطين غير مسمى إلى رأس جديد.

مساواة القيم ممكنة، وغياب الدورة حالة أخرى

في دورة رباعية بالحواف AB BC CD AD فقط، لا يوجد مثلث، والدورة الوحيدة بعد إزالة تكرار الاتجاه والبداية طولها4. لذلك يتساوى طول الأقصر والأطول عند4. اختلاف القياسين في مثالنا الخماسي لا يعني اختلافهما في كل رسم.

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

في المسار AB BC CD لا توجد دورة: البدء من طرف والرجوع يجبرنا على إعادة حافة أو رأس. لا نكتب صفرًا على أنه أقصر دورة حقيقية. سجلنا في الحساب قيمة خالية، ونعرض للقارئ «لا دورة»؛ هذا تمثيل لغياب المثال لا اصطلاح رياضي عددي.

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

كيف حُصرت الدورات وما حدود المراجعة

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

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

راجعنا جميع1024 رسمًا مسمى على خمسة رؤوس، بما فيها المنفصلة والخالية من الدورات. توجد37 دورة ممكنة في الرسم الكامل على هذه الأسماء:10 مثلثات و15 رباعية و12 خماسية. عبر المدخلات فحصنا1024×37=37888 مرشحًا، و59049 مجموعة حواف في الطريقة الثانية.

في المكعب أحصت الطريقتان28 دورة:6 بطول4 و16 بطول6 و6 بطول8. وفي الأصل الخماسي ثلاث دورات أطوالها3 و4 و5. هذه نتائج للقوائم المعلنة؛ لا تحصي جميع الرسوم على ثمانية أسماء أو جميع الأحجام.

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

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