المُخطَّط الأويلري، والمُخطَّط شبه الأويلري
تعرَّفْتُ سابقًا أنَّ دارة أويلر ممرٌّ رأسُ بدايته هو نفسه رأس نهايته، وأنَّه يشمل جميع حافات المُخطَّط من دون تكرار. وفي حال كان المُخطَّط المتصل يحتوي على دارة أويلر، فإنَّه يُسمّى مُخطَّطًا أويلريًّا.
أمّا المُخطَّط المتصل الذي يحوي ممرًّا يشمل جميع حافاته من دون تكرار، ورأس بدايته مختلف عن رأس نهايته، فيُسمّى مُخطَّطًا شبه أويلري
في ما يأتي مثال على مُخطَّط أويلري، ومثال آخر على مُخطَّط شبه أويلري.
يصعب أحيانًا تمييز المُخطَّط الأويلري من غيره عن طريق النظر إليه فقط. وفي هذه الحالة، يُمكِن الاستعانة بالنظرية الآتية:
نظرية: المُخطَّط الأويلري
· إذا كان عدد الرؤوس ذات الدرجة الفردية في المُخطَّط أكثر من رأسين، فإنَّ المُخطَّط لا يكون أويلريًّا، ولا شبه أويلري.
· إذا لم يكن المُخطَّط متصلًًا، فإنَّه لا يكون أويلريًّا، ولا شبه أويلري.
إيجاد طول أقصر مسار في مُخطَّط أويلري أو مُخطَّط شبه أويلري
المسار الأويلري هو مسار في المُخطَّط يشمل كل حافة في المُخطَّط مَرَّة واحدة على الأقل، ويبدأ بالرأس نفسه الذي ينتهي به. يُمكِن استعمال خوارزمية فحص المسار الأويلري لإيجاد طول أقصر مسار أويلري في مُخطَّط متصل موزون. أمّا إذا كان المُخطَّط أويلريًّا، فإنَّ أقصر مسار أويلري فيه يكون دارة أويلر، وهو مسار يتضمَّن جميع حافات المُخطَّط، ويبدأ بالرأس نفسه الذي ينتهي به. ومن ثَمَّ، فإنَّ طول أقصر مسار أويلري يساوي الوزن الكلي للمُخطَّط.
وأمّا إذا كان المُخطَّط شبه أويلري، فإنَّ طول أقصر مسار أويلري فيه يكون الوزن الكلي للمُخطَّط، مضافًا إليه مجموع أطوال حافات أقصر طريق بين الرأسين اللذينِ درجتهما فردية؛ وذلك لضمان البَدْء بنفس الرأس والانتهاء به.
إيجاد طول أقصر مسار أويلري في مُخطَّط متصل غير أويلري ولا شبه أويلري
تعلَّمْتُ في المثال السابق استعمال خوارزمية فحص المسار الأويلري لإيجاد طول أقصر مسار أويلري في مُخطَّط أويلري أو مُخطَّط شبه أويلري. والآن سأتعلَّم كيف يُمكِن إيجاد طول أقصر مسار أويلري في مُخطَّط غير أويلري ولا شبه أويلري.
خوارزمية: خوارزمية فحص المسار الأويلري للمُخطَّطات غير الأويلرية ولا شبه الأويلرية
يُمكِن إيجاد طول أقصر مسار أويلري في مُخطَّط متصل غير أويلري ولا شبه أويلري باستعمال خوارزمية فحص المسار، وذلك باتِّباع الخطوات الآتية:
1 تحديد الرؤوس ذات الدرجات الفردية في المُخطَّط.
2 تحديد الطرائق المختلفة لإضافة حافات بين الرؤوس ذات الدرجات الفردية حتّى تصبح درجات جميع الرؤوس زوجية(، ثمَّ إيجاد مجموع أوزان الحافات المضافة في كل طريقة.
3 اختيار الطريقة التي أُضيفت فيها حافات إلى المُخطَّط وزنها أقل ما يُمكِن، ثمَّ إضافة هذه الحافات إلى المُخطَّط.
4 إيجاد الوزن الكلي للمُخطَّط الناتج الذي يساوي طول أقصر مسار أويلري في المُخطَّط.
