مسارات ودوائر أويلر

القسم 2.4 مسارات ودوائر أويلر

الأهداف

بعد إتمام هذا القسم، ينبغي أن تكون قادرًا على ما يلي.

1. حدّد ما إذا كان رسم بياني (graph) أو رسم متعدّد (multigraph) يملك درب أويلر (Euler trail) أو دائرة أويلر (Euler circuit).
2. برّر لماذا يكون الشرط اللازم لوجود درب أويلر في رسم بياني شرطًا لازمًا.
3. ميّز بين دروب أويلر ومسارات هاميلتون (Hamilton paths)، وقرّر أيّهما أنسب لاستخدامه في مسألة معيّنة.

معاينة القسم

استكشف!

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

فإذا بدأنا من رأس (vertex) وتتبّعنا الحوافّ وصولًا إلى رؤوس أخرى، فإننا ننشئ ماشية (walk) عبر الرسم البياني. وأدقّ من ذلك، الماشية في الرسم البياني هي تتابع من الرؤوس بحيث يكون كل رأس في التتابع مجاورًا (adjacent) للرأسين السابق والتالي له في التتابع. فإذا سارت الماشية على امتداد كل حافة مرة واحدة بالضبط، فإنها تُسمّى درب أويلر (أو ماشية أويلر أو مسار أويلر). وإذا كان فوق ذلك رأس البداية هو رأس النهاية (أي أنك تتتبّع كل حافة مرة واحدة بالضبط فتصل حيث بدأت)، فإن الماشية تُسمّى دائرة أويلر (أو جولة أويلر). ولطبيعيّة الأمر، إذا لم يكن الرسم البياني مترابطًا (connected) فلا أمل في العثور على درب أو دائرة من هذا النوع. أمّا في بقية هذا القسم فنحن نفترض أن جميع الرسوم البيانية التي سنناقشها مترابطة.

إن مسألة جسور كونيغسبرغ (bridges of Königsberg) هي في حقيقتها سؤال عن وجود دروب أويلر. وستكون هناك طريقة تعبر كل جسر مرة واحدة بالضبط إذا وإلّا فقط كان الرسم المتعدّد أدناه يملك درب أويلر:

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

ورقة العمل: نشاط تمهيدي

أيّ من الرسوم البيانية أدناه تملك درب أويلر؟ وأيّ منها تملك دائرة أويلر؟

$$\begin{equation*} G_1 \end{equation*}$$

$$\begin{equation*} G_2 \end{equation*}$$ $$\begin{equation*} G_3 \end{equation*}$$

$$\begin{equation*} G_4 \end{equation*}$$

$$\begin{equation*} G_5 \end{equation*}$$ $$\begin{equation*} G_6 \end{equation*}$$

1.

$G_1$ يملك

• درب أويلر
• دائرة أويلر ودربًا
• لا هذا ولا ذلك

. $G_2$ يملك

• درب أويلر
• دائرة أويلر ودربًا
• لا هذا ولا ذلك

. $G_3$ يملك

• درب أويلر
• دائرة أويلر ودربًا
• لا هذا ولا ذلك

$G_4$ يملك

• درب أويلر
• دائرة أويلر ودربًا
• لا هذا ولا ذلك

. $G_5$ يملك

• درب أويلر
• دائرة أويلر ودربًا
• لا هذا ولا ذلك

. $G_6$ يملك

• درب أويلر
• دائرة أويلر ودربًا
• لا هذا ولا ذلك

2.

اكتب تتابع الدرجات (degree sequence) للرسوم البيانية أعلاه.

$G_1\text{:}$

$G_2\text{:}$

$G_3\text{:}$

$G_4\text{:}$

$G_5\text{:}$

$G_6\text{:}$

فما الصلة المحتملة بين تتابع الدرجات ووجود درب أويلر أو دائرة أويلر؟

3.

إحدى طرائق كتابة درب أويلر أو دائرة أويلر هي سرد الحوافّ بالترتيب. وستكون كل حافة زوجًا من الرؤوس، ولبيان الاتجاه الذي نسير فيه على امتداد تلك الحافة يمكننا كتابتها زوجًا مُرتَّبًا (ordered pair) بدل مجموعة. فمثلًا، لننظر في هذا الرسم البياني:

وهناك دربا أويلر يمكننا كتابتهما:

$$\begin{equation*} (a,b), (b,c), (c,d) \qquad \text{or} \qquad (d,c), (c,b), (b,a) \text{.} \end{equation*}$$

(a)

اكتب درب أويلر للرسم البياني أدناه.

ولكل رأس، اكتب درجته وعدد المرات التي يظهر فيها في قائمتك للحوافّ.

رأس	درجة	عدد مرات وروده
$a$
$b$
$c$
$d$
$e$
$f$

(b)

لنفترض أن لديك رسمًا بيانيًا تتابع درجاته $(4,2,2,2,2)$ ويملك درب أويلر. فكم مرة سيظهر اسم الرأس ذي الدرجة 4 في قائمتك للحوافّ؟

(c)

لنفترض أن لديك رسمًا بيانيًا درب أويلر فيه مكتوب على هيئة قائمة من الحوافّ. فما الذي يمكنك استنتاجه عن رأس يظهر 3 مرات بالضبط في القائمة؟ اختر كل الخيارات التي قد تكون صحيحة.

• يمكن أن يظهر الرأس في بداية درب أويلر ونهايته معًا.
• يمكن أن يظهر الرأس في بداية درب أويلر أو في نهايته، لكن ليس في الاثنين معًا.
• يمكن أن يظهر الرأس في وسط درب أويلر فقط.
• لا يمكن أن يظهر الرأس في درب أويلر إطلاقًا.
• لا بدّ من وجود رأس آخر ذي درجة فردية يظهر أيضًا في بداية درب أويلر أو نهايته.

قسم فرعي: شروط دروب أويلر

إحدى طرائق ضمان ألّا يملك رسم بياني دائرة أويلر هي إدراج «شوكة» (spike)، أي رأسٍ من الدرجة 1.

وللرأس $a$ درجة 1، فإذا حاولت إنشاء دائرة أويلر فسترى أنك ستعلق عند هذا الرأس. فهو نهاية مسدودة (dead end). ذلك، إلا إذا بدأت منه. لكن عندئذٍ لا سبيل إلى العودة، فلا أمل في العثور على دائرة أويلر. غير أن هناك درب أويلر. فهو يبدأ عند الرأس $a\text{,}$ ثم يلتفّ حول المثلّث. وستنتهي عند الرأس ذي الدرجة 3.

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

وهذا كله يعني أنه إذا كان لدى رسم بياني درب أويلر ورأسان من الدرجة الفردية، فلا بدّ أن يبدأ درب أويلر عند أحد الرأسين ذوي الدرجة الفردية وينتهي عند الآخر. وفي هذه الحالة، لا بدّ أن تكون درجة كل رأس آخر زوجية، إذ نحتاج إلى عدد من الحوافّ للوصول إلى تلك الرؤوس مساويًا لعدد الحوافّ التي نغادر بها منها. وكيف يمكننا أن تكون لدينا دائرة أويلر؟ لا يمكن أن يملك الرسم البياني أيّ رأسٍ من درجة فردية، لأن درب أويلر كان لا بدّ أن يبدأ عنده أو ينتهي عنده، لكن ليس في الاثنين معًا. ومن ثمّ، لكي يملك الرسم البياني دائرة أويلر، لا بدّ أن تكون درجة كلّ الرؤوس زوجية.

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

دروب أويلر ودوائره.

• يملك الرسم البياني دائرة أويلر إذا وفقط إذا كانت درجة كل رأسٍ زوجية.
• يملك الرسم البياني درب أويلر إذا وفقط إذا كان هناك رأسان على الأكثر من الدرجة الفردية.

ولأنّ رسم جسور كونيغسبرغ (bridges of Königsberg) رؤوسه الأربعة كلّها ذات درجات فردية، فلا يوجد درب أويلر عبر الرسم البياني. ومن ثمّ لا سبيل لأهل البلدة إلى عبور كل جسر مرة واحدة بالضبط.

قسم فرعي: مسارات هاميلتون

لنفترض أنّك أردت جولة في كونيغسبرغ بحيث تزور كلّ قطعة يابسة (الجزيرتين والضفتين) مرة واحدة بالضبط. ويمكن فعل ذلك. وبعبارات نظرية الرسوم البيانية، فأنت تسأل: هل هناك مسار يزور كل رأسٍ مرة واحدة بالضبط. ويُسمّى مثل هذا المسار مسار هاميلتون (Hamilton path) (أو مسارًا هاميلتونيًا). ويمكننا أيضًا أن نعتبر دورات هاميلتون (Hamilton cycles)، وهي مسارات هاميلتون تبدأ وتنتهي عند الرأس نفسه.

المثال 2.4.1.

حدّد ما إذا كانت الرسوم البيانية أدناه تملك مسار هاميلتون.

الحل. الرسم البياني على اليسار يملك مسار هاميلتون (والمسارات المختلفة كثيرة في الواقع)، كما هو مبيَّن هنا:

أمّا الرسم البياني على اليمين فلا يملك مسار هاميلتون. فأنت ستحتاج إلى زيارة كلّ واحد من الرؤوس «الخارجية»، لكن بمجرد أن تزور أحدها تعلق. ولاحظ أنّ هذا الرسم البياني لا يملك درب أويلر، رغم وجود رسوم بيانية تملك دروب أويلر لكن لا تملك مسارات هاميلتون.

ويبدو أنّ العثور على مسارات هاميلتون أسهل، لأنّ الرسوم البيانية تملك عادةً حوافّ أكثر من رؤوسها، فالمتطلّبات الواجب تحقّقها أقلّ. لكن لا أحد يعرف ما إذا كان هذا صحيحًا. فلا يوجد اختبارٌ بسيط معروف لمعرفة ما إذا كان الرسم البياني يملك مسار هاميلتون. وللرسوم البيانية الصغيرة ليست هذه مشكلة، لكن كلّما ازداد حجم الرسم البياني صعب أكثر فأكثر التحقّق ممّا إذا كان هناك مسار هاميلتون. وفي الحقيقة، هذا مثالٌ على سؤالٍ نعتقد أنه أصعب من أن يحلّه الحاسوب على وجه العموم، إذ هو مثالٌ على مسألةٍ مكتملة من نوع NP (NP-complete).

أسئلة القراءة

1.

هل يوجد رسم بياني يملك دائرة أويلر لكن لا يملك درب أويلر؟ اشرح إجابتك.

2.

هل يمكن أن تملك شجرة (tree) درب أويلر؟ وهل يمكن أن تملك دائرة أويلر؟ اشرح إجابتيك.

3.

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