مخططات أويلر

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

ما المُخطَّط الأويلري، وما شبه الأويلري؟

يُبيّن الشكل المجاور مُخطَّطًا للمسارات التي تسلكها سيارة البريد بين 9 مواقع تابعة لإحدى الشركات، ويُمثِّل العدد على كل حافة تكلفة الوقود (بالدينار) الذي تستهلكه السيارة بين كل موقعين. أُحدّد مسارًا يبدأ بالمنطقة ⁦A⁩، وينتهي بها، ويشمل كل حافة في المُخطَّط، بحيث تستهلك السيارة أقل كمية من الوقود إذا سلكت هذا المسار.

• دارة أويلر: ممرٌّ رأسُ بدايته هو نفسه رأسُ نهايته، ويشمل جميع حافات المُخطَّط من دون تكرار.

• في الشكلين الآتيين مثال على مُخطَّط أويلري، ومثال آخر على مُخطَّط شبه أويلري.

وكيف نعرف نوع المُخطَّط من دون تتبّع ممراته؟

كيف نعرف نوع المُخطَّط من درجات رؤوسه؟

• يصعب أحيانًا تمييز المُخطَّط الأويلري من غيره بالنظر إليه فقط؛ لذا يُستعان بالنظرية الآتية.

هل تحتوي دارة أويلر بالضرورة على جميع رؤوس المُخطَّط؟ أُبرِّر إجابتي.

أُحدِّد دارة أويلر من مُخطَّط المثال الأول.

أُحدِّد ممرًّا شبه أويلري من مُخطَّط المثال الثاني.

أَتأمَّل كل مُخطَّط ممَّا يأتي، ثمَّ أُحدِّد إذا كان أويلريًّا، أو شبه أويلري، أو غير ذلك.

• لا يجتمع النوعان: من المستحيل أن يكون المُخطَّط أويلريًّا وشبه أويلري في الوقت نفسه.

كيف نجد أقصر مسار يمرّ بكل حافة؟

• إذا كان المُخطَّط أويلريًّا: أقصر مسار أويلري فيه هو دارة أويلر، وهي مسار يتضمّن جميع حافات المُخطط.
• ومن ثَمَّ، فإنَّ طول أقصر مسار أويلري يساوي الوزن الكلي للمُخطط.
• إذا كان المُخطَّط شبه أويلري: يكون الطول هو الوزن الكلي للمُخطَّط، مضافًا إليه مجموع أطوال حافات أقصر طريق بين الرأسين اللذين درجتهما فردية.
• لماذا نضيف هذا الطريق؟ وذلك لضمان البدء بنفس الرأس والانتهاء به.

ماذا لو زادت الرؤوس الفردية عن رأسين؟

• تعلَّمتُ استعمال خوارزمية فحص المسار الأويلري لمُخطَّط أويلري أو شبه أويلري.
• والآن سأتعلَّم كيف يُمكِن إيجاد طول أقصر مسار أويلري في مُخطَّط غير أويلري ولا شبه أويلري.

تدريب: نوع المُخطَّط وطول أقصر مسار

أَتأمَّل كل مُخطَّط ممّا يأتي، ثمَّ أُحدّد إذا كان أويلريًّا، أو شبه أويلري، أو غير ذلك:

5. أجد طول أقصر مسار أويلري في المُخطط الموزون الآتي، يبدأ بالرأس ⁦A⁩، وينتهي به.

6. أجد طول أقصر مسار أويلري في المُخطط الموزون الآتي، يبدأ بالرأس ⁦B⁩، وينتهي به.

7. طرق: يُبيّن الشكل التالي مُخططًا للطرق الرئيسة بين مجموعة من المدن.

وفيه يُمثّل العدد على كل حافةٍ المسافة (بالكيلومتر) بين كل مدينتين.

أجد طول أقصر مسار أويلري يبدأ بالمدينة ⁦A⁩، وينتهي بها.

8. أنفاق: يُبيّن الشكل المجاور مُخططًا لأنفاق تصريف مياه الأمطار في إحدى المدن.

وفيه يُمثّل العدد على كل حافةٍ طول النفق بالكيلومتر.

إذا علمتُ أنَّ الفريق الهندسي المسؤول عن صيانة الأنفاق يرغب في فحصها قبل حلول فصل الشتاء للتحقق من عدم انسدادها، وأنَّه يتعيّن على الفريق المرور بكل نفق مرّةً واحدةً على الأقل، وأنَّه سيبدأ مهمته من الرأس ⁦A⁩، وينتهي به؛ فأجد طول أقصر مسار يُمكن أن يمرَّ به الفريق لإنجاز مهمته.

9. أحلُّ المسألة الواردة في بند (مسألة اليوم).

⁦a)⁩ أجد طول أقصر مسار أويلري في المُخطَّط الموزون المجاور، يبدأ بالرأس ⁦D⁩، وينتهي به، ويشمل كل حافة من حافاته.

وماذا لو لم يكن المُخطَّط أويلريًّا ولا شبه أويلري؟

طرق: يُبيّن الشكل المجاور مُخطَّطاً للطرق الرئيسة بين مجموعة من المناطق.

وفيه يُمثّل العدد على كل حافة المسافة (بالكيلومتر) بين كل منطقتين.

أجد طول أقصر مسار يبدأ بالمنطقة ⁦A⁩، وينتهي بها، ويشمل كل حافة في المُخطَّط.

مهارات التفكير العليا: خطأ، مصفوفة، وتحدٍّ

10. أكتشف الخطأ: قالت سلمى: "إنَّ أيَّ مُخطط كامل $K_n$، حيث $n > 2$، هو مُخطط أويلري". أكتشف الخطأ في قول سلمى، ثمَّ أُصحّحه.

• تبرير: أتأمل مصفوفة الجوار الآتية التي تُمثّل مُخططًا غير موزون، ثمَّ أُجيب عن السؤالين من دون رسم المُخطط.

$$ \begin{matrix} & A & B & C & D & E \\ A & 0 & 1 & 0 & 1 & 1 \\ B & 1 & 0 & 1 & 0 & 1 \\ C & 0 & 1 & 0 & 0 & 1 \\ D & 1 & 0 & 0 & 0 & 1 \\ E & 1 & 1 & 1 & 1 & 0 \end{matrix} $

11. هل المُخطط متصل؟ أُبرّر إجابتي.

12. هل المُخطط أويلري، أو شبه أويلري، أو غير ذلك؟ أُبرّر إجابتي.

إرشاد: أستعين بالمصفوفة لكتابة مجموعة درجات رؤوس المُخطط.

13. تحدّ: يُبيّن الشكل التالي مُخططًا موزونًا يُمثّل المسافات بين مجموعة من المناطق بالكيلومتر. إذا كان طول أقصر مسار في المُخطط باستعمال خوارزمية فحص المسار هو $100 \text{ km}$، فأجد قيمة الثابت الحقيقي $x$.