- صفر رؤوس فردية: دورة، من أي رأس وإليه
- رأسان فرديان: مسار من أحدهما إلى الآخر
- أربعة أو أكثر: مستحيل بخط واحد
باحث مسارات أويلر
هل تستطيع رسم بيت القديس نيكولاس دون أن ترفع القلم ودون أن تمرّ على خط مرتين؟ تستطيع، لكن بشرط أن تبدأ من إحدى الزاويتين السفليتين، ومن كل منهما 44 طريقة. والسبب هو درجة الرأس، أي عدد الخطوط الملتقية عنده: فكلما مرّ القلم برأس استهلك خطين من خطوطه. وجد ليونارد أويلر هذه القاعدة سنة 1736 مع جسور كونيغسبرغ السبعة. تتبّع شكلاً بنفسك، وانظر أين تتوقف ولماذا، واطلب تلميحاً، أو شاهد خوارزمية ترسمه. اختر شكلاً وارسمه متتبعاً خطوطه: انقر رأساً للبدء، ثم انقر الحواف أو الرؤوس التالية بالترتيب، أو اسحب من رأس إلى رأس. كل حافة تُستعمل مرة واحدة فقط. «رجوع» يتراجع خطوة، و«تلميح» يبيّن الحافة الآمنة التالية، و«حل» يعرض خوارزمية فلوري أو خوارزمية هيرهولتسر خطوة بخطوة. الرؤوس الفردية مملوءة، والشارة على كل رأس هي درجته. في وضع «ارسم»، النقر على مكان فارغ يضيف رأساً، والنقر على رأسين يصل بينهما، ونقرة أخرى تضيف حافة ثانية؛ اسحب الرأس لتحريكه. «امسح» يزيل الرؤوس والحواف. وإذا زاد عدد الرؤوس الفردية عن اثنين، يضيف زر «أضف» الحواف التي تجعل رسم الشكل ممكناً.
كيف يعمل
- اختر شكلاً، مثل جسور كونيغسبرغ السبعة أو بيت القديس نيكولاس أو نجمة، أو ارسم شكلك في وضع «ارسم»، بأي عدد تشاء من الحواف بين رأسين.
- انقر رأساً للبدء، ثم انقر الحواف أو الرؤوس بالترتيب، أو اسحب من رأس إلى رأس. وإذا توقفت بيّن سطر الحالة السبب؛ و«رجوع» يتراجع خطوة، و«تلميح» يبيّن حافة آمنة.
- اقرأ قاعدة الدرجات تحت الشكل، وأضف إلى الشكل المستحيل الحواف المقترحة، أو اضغط «حل» لترى خوارزمية فلوري أو هيرهولتسر ترسمه خطوة بخطوة.
لماذا الرؤوس الفردية هي الفيصل
الخط الذي يمرّ برأس يدخل من خط ويخرج من آخر، فهو يستهلك خطوط ذلك الرأس مثنى مثنى. ولا يمكن أن يبقى خط بلا قرين إلا حيث يبدأ الخط أو ينتهي. لذلك يجب أن يكون الرأس ذو العدد الفردي من الخطوط بداية أو نهاية. فإن لم يكن ثمة رأس فردي انتهى الخط حيث بدأ: وهذه دورة أويلر. وإن كان هناك رأسان سار من أحدهما إلى الآخر: وهذا مسار أويلر. وإن كانت أربعة أو أكثر فالأطراف أكثر من أن يحتملها خط واحد، وk رأساً فردياً تحتاج إلى k/2 من الخطوط. كان في كونيغسبرغ أربع قطع يابسة، عليها خمسة وثلاثة وثلاثة وثلاثة جسور: وكلها فردية، فلم تكن أي نزهة تستطيع عبور كل جسر مرة. ولو أُضيف جسر واحد بين اثنتين منها لأمكنت النزهة.
خوارزميتا فلوري وهيرهولتسر
معرفة أن الشكل قابل للرسم شيء ورسمه شيء آخر: فالخط المتسرّع قد يقطع نفسه عن الخطوط التي ما زال يحتاج إليها. تتجنّب خوارزمية فلوري سنة 1883 ذلك بقاعدة واحدة: لا تعبر جسراً أبداً، أي خطاً يؤدي حذفه إلى تقسيم الخطوط الباقية إلى جزأين، إلا إذا لم يكن ثمة خط آخر. أما خوارزمية هيرهولتسر، من بحث نُشر سنة 1873، فأسرع: امشِ حيث شئت حتى تتوقف، وهذا لا يحدث إلا عند نقطة البداية، ثم من رأس على الجولة ما زالت له خطوط حرة امشِ حلقة مغلقة أخرى وأدرجها في الجولة. وزمنها يكبر بنسبة عدد الحواف، وبهذه الطريقة تجد الحواسيب مسارات أويلر.
الأسئلة المتداولة
ما الفرق بين مسار أويلر ودورة أويلر؟
كلاهما يستعمل كل حافة في البيان مرة واحدة بالضبط. تنتهي دورة أويلر حيث بدأت، أما مسار أويلر فينتهي في موضع آخر. وللبيان المتصل دورة إذا كانت درجة كل رأس زوجية، ومسار إذا كان لرأسين بالضبط درجة فردية؛ ويسير المسار حينئذ من أحدهما إلى الآخر.
لماذا لا يمكن عبور جسور كونيغسبرغ السبعة مرة واحدة لكل جسر؟
ارسم كل قطعة يابسة رأساً وكل جسر حافة. كان في جزيرة كنايبهوف خمسة جسور وفي كل من القطع الثلاث الأخرى ثلاثة، فالرؤوس الأربعة كلها فردية. والنزهة لا تبدأ ولا تنتهي إلا عند رأس فردي، وأربعة كثيرة. وإضافة جسر واحد بين اثنين منها تُبقي رأسين فرديين، فتصبح النزهة ممكنة.
بكم طريقة يُرسم بيت القديس نيكولاس؟
بـ44 طريقة من كل زاوية من الزاويتين السفليتين، و88 في المجموع، إذا عُدّ الترتيب أو الاتجاه المختلف طريقة أخرى. ولا يُرسم من أي رأس آخر، لأن الزاويتين السفليتين هما الوحيدتان اللتان عدد خطوطهما فردي. وهكذا يحصي التطبيق طرق الأشكال الصغيرة.
ما الجسر في البيان؟
حافة يؤدي حذفها إلى تقسيم بيان متصل إلى جزأين. ولا تعبر خوارزمية فلوري جسراً من الحواف الباقية ما دام لها خيار آخر، لأن جزءاً من الشكل سيبقى خلفها. وفي هذا التطبيق يُقال للخط الذي توقف بعد عبور جسر مبكراً جداً في أي خطوة حدث ذلك.
هل يمكن أن توجد أكثر من حافة بين رأسين؟
نعم. البيان ذو الحواف المتوازية يسمى بياناً متعدداً، وكونيغسبرغ تحتاج إليه: فقد كان جسران يصلان كنايبهوف بكل ضفة. في وضع «ارسم» انقر الرأسين مرة أخرى لإضافة حافة بينهما، حتى أربع حواف. وتعمل قاعدة الدرجات كما هي، وتحسب كل حافة.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر