شرح مسارات أويلر ودوراته
بعض الأشكال تُرسم بخط واحد، دون رفع القلم ودون المرور على خط مرتين، وبعضها لا يُرسم مهما طالت المحاولة. ولا حاجة إلى المحاولة: عُدّ الخطوط عند كل زاوية. فإن كان عدد الخطوط فردياً في زاويتين على الأكثر أمكن رسم الشكل، وعند هاتين الزاويتين يجب أن يبدأ الخط وينتهي. وجد ليونارد أويلر هذه القاعدة سنة 1736، وأسّس بها نظرية البيانات.
جسور كونيغسبرغ السبعة
كانت مدينة كونيغسبرغ البروسية، وهي كالينينغراد اليوم، تمتد على ضفتي نهر بريغل وعلى جزيرتين فيه هما كنايبهوف ولومزه. وكانت سبعة جسور تصل الأجزاء الأربعة: جسران من كنايبهوف إلى كل ضفة، وجسر بين الجزيرتين، وجسر من لومزه إلى كل ضفة. وتساءل أهل المدينة هل تستطيع نزهة أن تعبر كل جسر مرة واحدة بالضبط. فأجاب أويلر في بحث قدّمه إلى أكاديمية سانت بطرسبرغ سنة 1735 وطُبع سنة 1741: لا تستطيع. وكانت خطوته الحاسمة أن طرح كل شيء إلا أجزاء المدينة والجسور بينها، وهذا هو عمل البيان: رأس لكل قطعة يابسة وحافة لكل جسر، وحافتان حيث يصل جسران المكانين نفسيهما.
قاعدة الدرجات
درجة الرأس هي عدد الحواف عنده. والخط الذي يمرّ برأس يدخل من حافة ويخرج من أخرى، فهو يستهلك حواف ذلك الرأس أزواجاً. ولا يستطيع الاحتفاظ بحافة بلا قرين إلا رأس الخط الأول ورأسه الأخير. لذلك يجب أن يكون الرأس ذو الدرجة الفردية بداية الخط أو نهايته. كان في كنايبهوف خمسة جسور وفي كل من الأجزاء الثلاثة الأخرى ثلاثة: أربعة رؤوس فردية، أي اثنان زائدان. وعموماً، للبيان المتصل دورة أويلر، أي خط ينتهي حيث بدأ، إذا كانت كل الدرجات زوجية، ومسار أويلر إذا كانت درجتان بالضبط فرديتين، من إحداهما إلى الأخرى. وعدد الرؤوس الفردية ليس واحداً أبداً ولا أي عدد فردي آخر: فكل حافة تضيف 2 إلى مجموع الدرجات، فالمجموع زوجي. وقد لاحظ أويلر هذا أيضاً، ويُسمى اليوم مبرهنة المصافحة.
لماذا تكفي هذه القاعدة
بيّن أويلر أن الشكل الذي فيه أكثر من رأسين فرديين لا يمكن رسمه، وقال دون برهان إن كل شكل متصل آخر يمكن رسمه. وجاء البرهان من كارل هيرهولتسر، الرياضي الألماني الذي مات شاباً سنة 1871؛ وظهر بحثه سنة 1873. ابدأ من رأس فردي إن وُجد، وإلا فمن أي مكان، وامشِ على حواف لم تُستعمل ما دمت تستطيع. ولأن كل رأس آخر درجته زوجية فلا يمكن أن تتوقف إلا عند الرأس الأخير. فإن بقيت حواف لمس بعضها الطريق الذي سلكته، لأن الشكل متصل. فامشِ من رأس كهذا مرة أخرى حتى تتوقف، وهو ما يحدث الآن بعودتك إليه، وأدرج الحلقة في الطريق عنده. وكرّر حتى لا تبقى حافة. والبرهان نفسه هو أسرع خوارزمية: إذ يُنظر إلى كل حافة عدداً ثابتاً من المرات.
خوارزمية فلوري: لا تحرق جسورك
قد يفشل الخط حتى في شكل يمكن رسمه. خذ مثلثين يصل بينهما حافة واحدة، وابدأ من زاوية في المثلث الأول: فإن عبرت إلى المثلث الثاني قبل إتمام الأول لن تعود أبداً. فالحافة الواصلة جسر: حذفها يقسم الشكل قسمين. وتعطي خوارزمية فلوري سنة 1883 قاعدة واحدة: عند كل رأس خذ حافة ليست جسراً للحواف الباقية، إلا إذا لم تكن هناك حافة أخرى. ومن اتبعها أتمّ الرسم دائماً. واختبار الجسر يستغرق وقتاً، فخوارزمية فلوري أبطأ من خوارزمية هيرهولتسر، لكنها التي يمكن اتباعها بالقلم، والتلميح في التطبيق يستعملها.
إصلاح شكل
الشكل الذي فيه k رأساً فردياً يحتاج إلى k/2 من الخطوط. ولرسمه بخط واحد أضف حوافّ تصل الرؤوس الفردية أزواجاً: فكل حافة جديدة تجعل رأسين فرديين زوجيين. وبإضافة k/2 − 1 حافة يبقى رأسان فرديان فينتج مسار؛ وبإضافة k/2 لا يبقى أي رأس فردي فتنتج دورة. ولو كان في كونيغسبرغ جسر آخر بين أي اثنين من الأجزاء الأربعة لأمكنت النزهة، ولو كان جسران لأمكنت جولة كاملة. وقد فعل التاريخ شيئاً شبيهاً: فُقد جسران في الحرب العالمية الثانية واستُبدل بجسرين طريق حديث، والجسور الخمسة القائمة اليوم في المواضع القديمة يمكن عبورها مرة لكل جسر، من جزيرة إلى أخرى.
إحصاء الطرق
بيت القديس نيكولاس، وهو مربع برسم قطريه وسقف فوقه، هو صيغة الأحجية عند الأطفال الألمان: ففي «Das ist das Haus vom Ni-ko-laus» ثمانية مقاطع صوتية، مقطع لكل خط. وزاويتاه السفليتان هما الرأسان الفرديان الوحيدان، ومن كل منهما 44 طريقة بالضبط لرسمه، و88 في المجموع. وللبيانات الموجّهة صيغة تعطي عدد دورات أويلر، هي مبرهنة BEST، نسبة إلى دي بروين وفان أردنه-إرنفست وسميث وتات. أما البيانات العادية فلا تُعرف لها صيغة كهذه، ويُعدّ الإحصاء صعباً عموماً، لذلك يحصي التطبيق الأشكال الصغيرة بتجربة كل طريقة، متجاوزاً الخطوات التي تقسم الشكل قسمين.
أين تُستعمل مسارات أويلر
جرّافة الثلج وكنّاسة الشوارع وساعي البريد يريدون المرور بكل شارع مرة والعودة. فإن كان عدد الشوارع عند كل تقاطع زوجياً كفت دورة أويلر؛ وإلا وجب المرور ببعض الشوارع مرتين، واختيار أقلها كلفة هو مسألة ساعي البريد الصيني التي طرحها مايغو غوان سنة 1962. وراسمة الأقلام أو آلة القطع بالليزر توفّر الوقت برسم أكبر عدد ممكن من الخطوط دون رفع الأداة. وفي تسلسل الجينوم تُجمّع ملايين القطع القصيرة من الحمض النووي بإيجاد مسار أويلر في بيان دي بروين، حيث كل قطعة حافة. والقاعدة نفسها تدلّك على أي رسوم كتاب الألغاز تستحق المحاولة.
جرّبه بنفسك
افتح باحث مسارات أويلر لتتبّع اثني عشر شكلاً بنفسك، من كونيغسبرغ سنة 1736 واليوم إلى النجوم والمربعات المتداخلة والمكعب، أو ارسم أشكالك بحواف متوازية. الرؤوس الفردية مملوءة، وكل رأس يُظهر درجته، وقاعدة الدرجات تحت الشكل تبيّن ما هو ممكن وأي الحواف تصلح الشكل. وإذا توقفت قال لك التطبيق هل بدأت من الرأس الخطأ أم عبرت جسراً مبكراً جداً، وفي أي خطوة. و«تلميح» يعطي حافة آمنة، و«حل» يرسم الشكل بخوارزمية فلوري مع إظهار اختبار الجسر، أو بخوارزمية هيرهولتسر مع إظهار كل إدراج.
الأسئلة المتداولة
هل مسار أويلر هو نفسه مسار هاميلتون؟
لا. مسار أويلر يستعمل كل حافة مرة وقد يمرّ برأس مرات كثيرة؛ ومسار هاميلتون يمرّ بكل رأس مرة ولا يلزمه استعمال كل حافة. ومعرفة هل في البيان مسار أويلر تأتي فوراً بعدّ الرؤوس الفردية، أما مسارات هاميلتون فلا يُعرف لها اختبار سريع، وإيجاد واحد منها من المسائل الصعبة الكلاسيكية في علم الحاسوب.
هل تصحّ قاعدة الدرجات حين يصل بين رأسين أكثر من حافة؟
نعم. كل حافة تُحسب في درجة طرفيها، سواء وصلت حافة أخرى الرأسين نفسيهما أم لا. وكونيغسبرغ بيان متعدد من هذا النوع، فيه جسران من كنايبهوف إلى كل ضفة. والحافة من رأس إلى نفسه، أي العروة، تضيف 2 إلى درجته ولا تغيّر أبداً كونها فردية.
وماذا عن الشوارع ذات الاتجاه الواحد؟
في البيان الموجّه لكل حافة اتجاه، وتقارن القاعدة الحواف الداخلة إلى كل رأس بالخارجة منه. فتوجد دورة أويلر إذا كان لكل رأس من الحواف الداخلة مثل ما له من الخارجة وكانت الحواف متماسكة، ويوجد مسار أويلر إذا كان لرأس حافة خارجة زائدة ولآخر حافة داخلة زائدة وكانت البقية متوازنة. ويسير المسار حينئذ من الأول إلى الثاني.
هل يمكن أن يوجد شكل فيه رأس فردي واحد بالضبط؟
لا. مجموع درجات كل الرؤوس يساوي ضعف عدد الحواف، لأن لكل حافة طرفين. وهذا المجموع زوجي، فعدد الدرجات الفردية فيه يجب أن يكون زوجياً أيضاً: 0 و2 و4 وهكذا، ولا يكون 1 أو 3 أبداً.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
افتح باحث مسارات أويلر