توجيه الرسم: هل يمنع الرأس الفاصل اتصالًا قويًا؟

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

لا؛ في مثالنا ندير كل مثلث حول X، فنستطيع الانتقال بين الجهتين عبره والرجوع أيضًا. حذف X يفصل الرسم، لكنه موجود أثناء السير. أما مثلثان لا يتصلان إلا بالحافة CD، فاختيار C→D يمنع العودة من جهة D إلى جهة C، وعكسها يمنع الذهاب.

• التوجيه يختار اتجاهًا واحدًا لكل حافة غير موجهة. [1] والاتصال القوي يعني إمكان الوصول من كل رأس إلى كل آخر باتباع اتجاه الأسهم. [2] لا نضيف سهمًا معاكسًا إلى كل حافة تلقائيًا.
• الرؤوس A وB وX وC وD، والحواف AX وAB وBX وXC وCD وXD. التوجيه X→A→B→X وX→C→D→X يصل بين كل رأسين؛ حذف X يترك AB وCD منفصلتين.
• في مثلثَي ABC وDEF المتصلين عبر CD وحدها، أقل درجة2 لكن لا توجيه قوي. حذف CD يفصل الجهتين، واتجاه واحد لها يتيح العبور في جهة واحدة فقط.
• إضافة AF تسمح بالشاهد A→B→C→A وC→D وD→E→F→D وF→A. يستطيع المرء الذهاب عبر C→D والرجوع عبر F→A؛ راجعنا30 زوجًا مرتبًا من رأسين مختلفين.
• الرسم الأول ذو X لا يملك دورة تزور الرؤوس الخمسة مرة واحدة، رغم توجيهه القوي. السير المغلق X→A→B→X→C→D→X يعيد زيارة X، فلا يمثل دورة هاملتونية.
• حصرنا توجيهات الرسوم الثلاثة:4 من64، ثم0 من128، ثم18 من256. وفحص1024 رسمًا على خمسة رؤوس ثابتة تحقق من253 رسمًا يقبل توجيهًا قويًا؛ هذا فحص محدود لا برهان عام.

اتجاه واحد لكل حافة، ووصول في الاتجاهين

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

التوجيه يعين اتجاهًا واحدًا لكل حافة في الرسم غير الموجه. [1] لذلك لا نحول AB إلى سهمين معًا؛ السماح باتجاهين كان سيغير المسألة، ويخفي العائق الذي سنراه عند الجسر.

الرسم الموجه قوي الاتصال إذا أمكن الوصول من أي رأس إلى أي رأس آخر باتباع الأسهم. [2] نحتاج مسارًا من A إلى B ومسارًا من B إلى A، وقد يستعملان حواف مختلفة أو يمران عبر رؤوس وسيطة.

في أمثلتنا نسأل عن أزواج الرؤوس المختلفة. خمسة رؤوس تعطي5×4=20 زوجًا مرتبًا، وستة تعطي6×5=30. ترتيب البداية والنهاية مهم؛ نجاح A→C لا يثبت وحده نجاح C→A.

المسار ليس مطلوبًا أن يزور بقية الرؤوس كلها. قد نختار مسارًا قصيرًا لزوج، وآخر أطول لزوج مختلف. نتحقق من إمكان الوصول، ولا نحسب زمن الرحلة أو وزن الحواف أو أقصر مسافة.

لا يملك الرسم توجيهًا قويًا إذا كان غير متصل أو فيه جسر. [1] سنشرح عائق الجسر مباشرة في رسم محدد، ونميز حذف حافة من حذف رأس؛ اختلاف الشيء المحذوف يغير السؤال.

الدوائر المسماة في الصور هي الرؤوس. مرور خطين أحدهما فوق الآخر لا ينشئ رأسًا جديدًا في القوائم. وتتبع رأس السهم ضروري؛ لا تعكس حافة لأن ذلك يجعل المسار الذي تبحث عنه أسهل.

رأس فاصل، ومع ذلك يصل كل رأس إلى كل آخر

نثبت A وB وX وC وD، والحواف الست AX وAB وBX وXC وCD وXD. المثلث الأول على X وA وB، والثاني على X وC وD؛ يشتركان في X وحده، ولا توجد حافة تصل A أوB مباشرةً بـC أوD.

نجعل اتجاهات المثلث الأول X→A وA→B وB→X. ونجعل اتجاهات الثاني X→C وC→D وD→X. يستطيع كل رأس داخل مثلثه الوصول إلى X، ويستطيع X الوصول إلى أي رأس في المثلث نفسه.

إذا اختلف المثلثان، نصل أولًا إلى X ثم نغادره إلى الهدف. من A إلى C مثلًا نتبع A→B→X→C، ومن C إلى A نتبع C→D→X→A. كل سهم في المسارين من القائمة المعلنة.

ينطبق هذا البناء على الرؤوس العشرين زوجًا مرتبًا: داخل المثلث نتبع اتجاه دورته، وبين المثلثين نمر عبر X. وجود طريق في اتجاه لا يغني عن الآخر، لكن توجيه الدورتين يوفر الاتجاهين بطريقة صريحة.

احذف X الآن مع حوافه المتصلة به AX وBX وXC وXD. يبقى A وB متصلين بالحافة AB، وC وD متصلين بالحافة CD. لا وصلة بين الجهتين؛ إذن X رأس فاصل في الرسم الأصلي.

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

كل حافة في هذا المثال تقع في مثلث، وحذف حافة واحدة لا يفصل الرسم. حصرنا الخيارات الثنائية للحواف الست:2^6=64 توجيهًا. أربعة فقط قوية؛ ندير كل مثلث في أي من اتجاهيه، فنحصل على2×2=4.

الجسر لا يسمح بالعبور والعودة

نبني مثلث ABC بالحواف AB وAC وBC، ومثلث DEF بالحواف DE وDF وEF، ثم نضيف CD وحدها بينهما. هذه سبع حواف على ستة رؤوس، والقائمة كاملة؛ لا توجد AF في هذا الرسم بعد.

الرسم غير الموجه متصل، وكل رأس درجته2 أو3. يمكن قبل اختيار الأسهم الانتقال من مثلث إلى الآخر عبر CD. لكن الاتصال غير الموجه يتجاهل جهة الحركة، بينما الاتصال القوي يطلب الوصول باتباع الأسهم.

حذف CD يفصل المثلثين؛ لذلك هي جسر. أي مسار يبدأ في ABC وينتهي في DEF يحتاج عبورها، لأن بقية الحواف داخل إحدى الجهتين. وهذا الحكم لا يعتمد على ترتيب رسم المثلثين على الصفحة.

اختر C→D. يستطيع مسار عبور هذه الحافة نحو DEF، لكن لا يستطيع أي مسار يبدأ في DEF العودة إلى ABC: يحتاج D→C، وهو ليس سهمًا موجودًا. تغيير اتجاهات الحواف داخل المثلثين لا يخلق وصلة ثانية.

واختر بدلًا منه D→C. تصبح العودة نحو ABC ممكنة عبر الجسر، لكن الانتقال من ABC إلى DEF يصطدم بالمشكلة نفسها في الاتجاه الآخر. كل اختيار لاتجاه CD يترك جهة عبور محظورة.

يمكن أن ندير كل مثلث ليكون قوي الاتصال داخليًا. مع ذلك لا يصبح الرسم كله قويًا؛ شرط الوصول داخل الجزء لا يثبت الوصول بين الأجزاء. اللوحة اليمنى تعرض C→D بالأحمر حتى يظهر هذا العائق.

حصرنا2^7=128 توجيهًا، ولم نجد توجيهًا قويًا. الحجة السابقة تفسر الاستحالة لكل هذه الاختيارات، بدل الاعتماد على فشل محاولة واحدة. كما يبين المثال أن أقل درجة2 لا تكفي لضمان النتيجة.

حافة ثانية تتيح اتجاهًا للعودة

نضيف AF إلى الرسم ذي المثلثين والجسر CD، ونحتفظ بالحواف السبع القديمة. صارت هناك وصلتان بين الجهتين، وبات عدد الحواف8. الإضافة تغيير حقيقي في الرسم، لا مجرد إعادة ترتيب للرؤوس في الصورة.

نختار A→B وB→C وC→A داخل المثلث الأول، وD→E وE→F وF→D داخل الثاني. نوجه الوصلتين C→D وF→A. هكذا ننتقل إلى جهة DEF عبر الأولى، ونعود إلى ABC عبر الثانية.

من B إلى E نستعمل B→C→D→E. ومن E إلى B نستعمل E→F→A→B. المساران يتبعان الأسهم كما هي، ولا يحتاجان استعمال CD في اتجاهين؛ حافة العودة الجديدة تحمل المهمة الأخرى.

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

درجات A وB وC وD وE وF الآن(3,2,3,3,2,3). بقيت B وE بدرجة2. زال عائق الجسر بإضافة وصلة للعودة، ولم تكن زيادة درجة كل رأس إلى3 مطلوبة لهذا الشاهد.

حصرنا2^8=256 توجيهًا للرسم المعدل، فكان18 منها قويًا. هذا العدد يخص الحواف الثماني المحددة، ولا يعني أن أي اتجاه نختاره بعد الإضافة ينجح. يعرض الشاهد المكتوب اختيارًا يمكن فحصه مباشرة.

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

الاتصال القوي لا يطلب دورة تزور كل رأس مرة واحدة

عد إلى الرسم ذي المثلثين المشتركين في X. يتيح توجيهنا القوي السير المغلق X→A→B→X→C→D→X. يزور هذا السير الرؤوس الخمسة، لكنه يعيد زيارة X قبل الوصول إلى نهاية الإغلاق.

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

أي دورة تحاول زيارة A وB وC وD يجب أن تنتقل بين المثلثين عبر X ثم تعود إلى الجهة الأولى لإغلاقها. لا يوجد رأس آخر أو حافة مباشرة تصل الجهتين؛ فتحتاج زيارة X أكثر من مرة في السير المغلق.

لذلك لا يملك الرسم غير الموجه أصلًا دورة تشمل رؤوسه الخمسة مرة واحدة. راجعنا أيضًا جميع24 ترتيبًا للرؤوس الأربعة الأخرى بعد تثبيت A بدايةً وإضافة A للإغلاق؛ لم يشكل أي ترتيب دورة صحيحة بالحواف الست.

غياب الدورة الشاملة لم يمنع المسار A→B→X→C ولا المسار C→D→X→A. كل واحد منهما يصل زوجًا محددًا، ولا يُطلب منه ضم جميع الرؤوس. وقد نستعمل X في مسارات مختلفة دون مخالفة شرط الاتصال القوي.

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

ميز بين ثلاثة أسئلة: هل يمكن الوصول باتجاه الأسهم؟ هل تبقى إمكانية الوصول بعد حذف رأس؟ وهل توجد دورة تزور كل رأس مرة واحدة؟ يقدم مثال X إجابات مختلفة، فلا نستبدل أحد هذه الاختبارات بالآخر.

افحص السهم والحافة، ثم حدّد نطاق النتيجة

الجدول يقارن مجموعات الحواف التي ثبتناها. لكل حافة خياران لاتجاهها، لذا تعد64 و128 و256 جميع التوجيهات الممكنة في الرسوم الثلاثة. أعداد4 و0 و18 هي التوجيهات القوية بينها، لا أعداد المسارات داخل توجيه واحد.

أجرينا فحصًا مستقلًا على خمسة رؤوس ثابتة A وB وC وD وE. الأزواج غير الموجهة الممكنة بينها10، واختيار وجود كل حافة أو غيابها يعطي2^10=1024 رسمًا مختلفًا على الأسماء نفسها.

ولحصر الرسوم مع اتجاهاتها، نعطي كل زوج حالة من ثلاث: غياب الحافة أو أحد اتجاهيها. ينتج3^10=59049 اختيارًا. فحصنا الوصول في كل اختيار، ثم جمعنا النتائج بحسب الرسم غير الموجه الذي جاء منه.

وجدنا253 رسمًا متصلًا بلا جسور، وكانت هي نفسها الرسوم التي تملك توجيهًا قويًا ضمن هذا الفحص. هذا تحقق شامل على خمسة رؤوس مسماة فقط؛ لا يحل محل برهان عام لكل عدد من الرؤوس.

مرجعنا الأول يذكر ضرورة الاتصال وغياب الجسر. [1] لا ننسب إلى هذه العبارة وحدها برهانًا للاتجاه العكسي في كل الرسوم. الأمثلة الموجبة هنا مثبتة بتوجيهاتها الصريحة، والأعداد الكبيرة بفحصها المنتهي المحدد.

ليس الاختبار عن أعطال حقيقية أو سعات أو تأخير أو حركة مرور واقعية. إنه سؤال رياضي عن الحواف المعلنة وإمكان السير. إضافة حافة مفقودة لتسهيل العودة تغير المدخل، كما فعلنا بوضوح مع AF.

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