ممر أويلر: الحواف مرة واحدة والرؤوس قد تتكرر

الخلاصة السريعة

في رسمنا يوجد ممر أويلر يبدأ من A وينتهي عند D: A→B→C→A→D→C→E→D. يمر بالحواف السبع مرة واحدة، رغم تكرار زيارة A و C و D. ولا توجد فيه دارة أويلر، لأن رأسي A و D فقط درجتاهما فرديتان.

• ممر أويلر يشمل كل حافة مرة واحدة. الدارة الأويلرية تعود إلى رأس البداية. هنا نعالج مخططًا غير موجه، بلا حلقات ذاتية أو حواف متوازية، وفيه حافة على الأقل. [1]
• بعد استبعاد الرؤوس المعزولة، يلزم اتصال الجزء ذي الحواف. إذا كانت درجاته كلها زوجية، توجد دارة؛ وإذا كان له رأسان فرديا الدرجة، يوجد ممر مفتوح. أكثر من رأسين فرديين يمنع الممر. [1]
• في مثالنا درجات A و B و C و D و E هي (3,2,4,3,2). الرأسان الفرديان A و D هما طرفا الممر، والجدول يبين درجات الرؤوس كلها.
• ترتيب المرور في الصورة يعطي الحواف A–B و B–C و C–A و A–D و D–C و C–E و E–D. الأرقام على الخطوط ترتيب المرور في المثال، وليست أوزانًا أو مسافات.
• تكرار الرأس لا يعيد الحافة تلقائيًا. في مثالنا زارت القائمة C مرتين، لكنها استعملت حوافه الأربع المختلفة. إذا رجعت من B إلى A مباشرة بعد A إلى B، فقد كررت الحافة نفسها.
• الصورة الداخلية تعرض مثلثين منفصلين، كل درجاتهما زوجية، لكن لا يوجد ممر واحد يشمل حوافهما كلها. لا تغفل شرط الاتصال، ولا تستعمل الاختبار نفسه لمخطط ذي أسهم. [1]

الحافة اتصال، والرأس نقطة التقاء

الحواف في نموذجنا غير موجهة، لذلك A–B و B–A اسمان للحافة نفسها، لا حافتان. يشترط الممر الأويلري استعمال كل حافة مرة واحدة؛ أما العودة إلى نقطة البداية فتجعل الممر دارة. [1]

حددنا خمسة رؤوس هي A و B و C و D و E، والحواف السبع موضحة في الرسم. لا توجد حافة من الرأس إلى نفسه، ولا نسختان من الاتصال نفسه، ولا سهم يلزمنا باتجاه واحد. أطوال الخطوط على الصفحة ليست بيانات لحساب مسافة.

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

عدّ الحواف عند كل رأس قبل اختيار الطرفين

في رسمنا يتصل A بـ B و C و D، فدرجته 3. ويتصل D بـ A و C و E، فدرجته 3 أيضًا. أما B فحافتاه إلى A و C، و E حافتاه إلى C و D؛ درجتا B و E تساويان 2. والرأس C يتصل بالأربعة A و B و D و E، فدرجته 4.

يعرض الجدول الدرجات نفسها. نجمع 3 + 2 + 4 + 3 + 2 = 14، ونقارنها بطرفين لكل واحدة من الحواف السبع:7 × 2 = 14. هذا فحص للعد؛ ونرى من الرسم أن الرؤوس الخمسة متصلة عبر حوافها.

في أي ممر يستخدم هذه الحواف كلها، يمكن إقران الدخول والخروج عند الرأس الداخلي. أما طرف البداية وطرف النهاية فيبقى عند كل منهما استعمال غير مقترن. في مثالنا لا بد أن يكون الطرفان A و D؛ يمكن السير بالعكس، لكن لا نبدأ من B وننتهي عند E ونزعم أننا استعملنا الخطوط كلها مرة واحدة.

افحص الحواف بين كل اسمين في القائمة

نختار الممر A→B→C→A→D→C→E→D. انتقالاته السبعة هي A–B، ثم B–C، ثم C–A، ثم A–D، ثم D–C، ثم C–E، ثم E–D. كل انتقال موجود في الرسم، ولا تظهر أي حافة مرة ثانية بعد اعتبارها اتصالًا غير موجه.

عدّ الخطوط السبعة في الصورة، ثم قارِنها بالقائمة. تحتوي القائمة ثمانية أسماء للرؤوس لأن سبعة انتقالات تصل بينها. هذه الأسماء ليست ثمانية رؤوس مختلفة؛ أصل الرسم خمسة فقط. زار الممر A مرتين و C مرتين و D مرتين، دون أن يكرر حافة.

والرجوع مباشرة A→B→A يفشل الشرط في مثالنا؛ يستخدم الاتصال A–B مرتين. لا ننقذ هذه العودة بالقول إن الاتجاه تغير، لأن الحافة غير موجهة. في الممر الصحيح عاد A عبر C–A بدل العودة على A–B.

درجات زوجية لا تكفي إذا كانت الحواف منفصلة

يشترط اختبار الدرجات أن تكون الرؤوس ذات الحواف في مكوّن متصل واحد؛ لا تغيّر الرؤوس المعزولة هذا الشرط على الحواف. [1]

أنشأنا في الصورة الداخلية مثلث A و B و C، ومثلثًا آخر D و E و F، بلا حافة بينهما. لكل رأس حافتان، فجميع الدرجات 2. تستطيع الدوران داخل الأول، وتستطيع الدوران داخل الثاني، لكن لا توجد خطوة تنقلك من أحدهما إلى الآخر.

إذن لا تستطيع كتابة ممر واحد يشمل الحواف الست كلها. القفز من C إلى D مثلًا يضيف اتصالًا غير موجود في النموذج، وإدراج اسمي الرأسين متجاورين في القائمة لا يجعله حافة. المثال يبين لماذا نقرأ الدرجات والاتصال معًا.

فرّق بين ممر مفتوح ودارة، وحدد نوع المخطط

لو حذفنا A–D من الرسم الرئيسي، لصارت درجتا A و D تساويان 2 وبقيت بقية الدرجات زوجية. نستطيع عندها كتابة A→B→C→D→E→C→A، وهي دارة تستخدم الحواف الست الباقية مرة واحدة وتعود إلى A. هذا رسم معدل، لا دارة في الرسم الأصلي ذي الحواف السبع.

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

للمراجعة، اكتب الحواف الموجودة، وحدد درجة كل رأس، ثم افحص اتصال الجزء ذي الحواف. بعد اقتراح الممر، طابق كل انتقال بحافة، وتأكد أن العدد يساوي عدد الحواف وأن كل حافة ظهرت مرة واحدة. افحص الطرفين أخيرًا: بداية مختلفة عن النهاية في مثالنا، وبداية مساوية للنهاية في الرسم المعدل.