مسار أويلر ودورة أويلر: الفرق والشروط وطريقة إيجادهما بالخطوات

إذا وصلت إلى هنا وأنت تحاول التمييز بين مسار أويلر (Eulerian path) ودورة أويلر (Euler cycle)، فالإجابة المباشرة بسيطة: كلاهما مسار يمرّ بكل حافة (edge) في الرسم البياني مرة واحدة بالضبط دون تكرار، والفرق الوحيد الجوهري هو نقطة النهاية. المسار قد يبدأ من عقدة وينتهي عند عقدة أخرى مختلفة، أمّا الدورة (وتُسمى أيضاً دائرة أويلر أو Eulerian circuit) فتعود لتنتهي عند نفس العقدة التي بدأت منها. أي إنّ كل دورة أويلر هي مسار أويلر مغلق، لكن ليس كل مسار أويلر يشكّل دورة.

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

الفرق بين مسار أويلر ودورة أويلر باختصار

العنصر	مسار أويلر (Path)	دورة أويلر (Cycle / Circuit)
يمرّ بكل حافة مرة واحدة	نعم	نعم
نقطة البداية والنهاية	عقدتان مختلفتان	نفس العقدة
شرط الرسم غير الموجَّه	صفر أو عقدتان بدرجة فردية	كل العقد بدرجة زوجية
مثال بديهي	رسم حرف بقلم واحد وتنتهي في مكان مختلف	جولة بريد تعود لنقطة الانطلاق

شروط وجود كل منهما

الشرط المشترك أولاً: يجب أن يكون الرسم متصلاً بالنسبة للعقد التي تملك حوافاً (العقد المعزولة بلا حواف لا تؤثر). بعد ذلك تختلف الشروط حسب نوع الرسم.

في الرسم غير الموجَّه (Undirected):

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

في الرسم الموجَّه (Directed): هنا نتحدث عن درجة الدخول (in-degree) ودرجة الخروج (out-degree):

• دورة أويلر توجد إذا كانت درجة الدخول تساوي درجة الخروج لكل عقدة.
• مسار أويلر يوجد إذا كانت عقدة واحدة درجة خروجها أكبر بواحد (نقطة البداية)، وعقدة واحدة درجة دخولها أكبر بواحد (نقطة النهاية)، وبقية العقد متوازنة.

كيف تتحقق وتُوجد المسار عملياً

للتحقق السريع من الوجود، اتبع هذه الخطوات:

1. تأكد أن كل العقد ذات الحواف متصلة في مكوّن واحد (باستخدام BFS أو DFS).
2. احسب درجة كل عقدة.
3. طبّق شرط الدرجات الموضّح أعلاه لتحدد: لا شيء، أم مسار، أم دورة.

أما لاستخراج المسار نفسه فعلياً، فالأداة القياسية هي خوارزمية هيرهولزر (Hierholzer's Algorithm)، وهي أسرع من الطريقة الكلاسيكية القديمة لـ Fleury وتعمل بزمن خطي O(E) حيث E عدد الحواف:

1. ابدأ من عقدة مناسبة (أي عقدة في الدورة، أو إحدى العقدتين الفرديتين في المسار).
2. سِر عبر الحواف غير المستخدمة مكوّناً دورة فرعية حتى تعود إلى نقطة البداية.
3. إذا بقيت حواف غير مستخدمة عند عقدة تقع على مسارك، انطلق منها لبناء دورة فرعية جديدة وادمجها.
4. كرّر حتى تُستهلك كل الحواف، ثم اقرأ التسلسل النهائي.

نصيحة عملية من التطبيق: لا تُخزّن الحواف المستخدمة في قائمة تبحث فيها خطياً، لأن ذلك يجعل الخوارزمية بطيئة O(E²). استخدم مؤشراً (pointer/iterator) لكل عقدة يتقدّم على قائمة جيرانها، أو علامة "مستخدمة" على كل حافة، لتبقى ضمن O(E).

خطأ شائع: أويلر ليس هاملتون

أكثر التباس يقع فيه المبتدئون هو الخلط بين مسار أويلر ومسار هاملتون (Hamiltonian path). الفرق حاسم:

• مسار أويلر يمرّ بكل حافة مرة واحدة (وقد يزور العقدة مرات عديدة).
• مسار هاملتون يمرّ بكل عقدة مرة واحدة (وقد يتجاهل حوافاً كثيرة).

والفرق ليس شكلياً فقط: التحقق من وجود مسار أويلر سهل وسريع (فحص درجات)، بينما إيجاد مسار هاملتون مسألة NP-صعبة لا تُحلّ بكفاءة معروفة في الحالة العامة. لذا فخلط أحدهما بالآخر قد يقودك إلى تصميم خوارزمية خاطئة تماماً.

تطبيقات عملية

المفهوم ليس نظرياً بحتاً، بل يظهر في:

• مسائل التوجيه مثل جولة ساعي البريد الصيني (Chinese Postman) وجدولة مركبات جمع القمامة أو كسح الشوارع، حيث الهدف تغطية كل "الطرق/الحواف".
• علم الوراثة والمعلوماتية الحيوية: تجميع تسلسلات الحمض النووي عبر رسوم دي بروين (de Bruijn graphs) يعتمد مباشرة على إيجاد مسار أويلر.
• رسم الأشكال بقلم واحد دون رفعه أو تكرار خط، وهي الصيغة الترفيهية لنفس المسألة.

تاريخياً، وُلد المفهوم كله من مسألة جسور كونيغسبرغ عام 1736، حين أثبت الرياضي ليونهارد أويلر استحالة عبور جسورها السبعة مرة واحدة والعودة إلى نقطة البدء، لأن كل قطع اليابسة كانت بدرجة فردية. من تلك المسألة وُلد علم نظرية الرسوم البيانية (Graph Theory) بأكمله.

الأسئلة الشائعة

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

ماذا لو كان عدد العقد الفردية أكثر من اثنتين؟ عندها لا يوجد لا مسار ولا دورة أويلر إطلاقاً. عدد العقد الفردية في أي رسم يكون دائماً زوجياً (0، 2، 4...)، ووجود 4 فأكثر يعني الاستحالة.

هل تنطبق هذه الشروط على الرسوم الموجَّهة؟ لا، الشروط تختلف. في الرسم الموجَّه نوازن بين درجة الدخول ودرجة الخروج لكل عقدة كما وضّحنا، لا مجرد فردية الدرجة.

ما أسرع طريقة لإيجاد المسار برمجياً؟ خوارزمية هيرهولزر بزمن O(E)، مع الانتباه إلى استخدام مؤشر لكل عقدة بدل البحث الخطي عن الحواف المتبقية حتى لا يتدهور الأداء.