ترتيب الحذف: هل الدرجة 2 تكفي؟

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

لا؛ الدرجة2 تخبرنا أن للرأس جارين، ولا تخبرنا هل يتصلان. في مثالنا A له B وC مع الحافة BC، فينجح أولًا. في الدورة الرباعية له B وD دون BD، فلا ينجح. نطلب زمرة من الجيران اللاحقين في كل خطوة، مع إبقاء الحواف الأصلية فقط.

• الرسم الوتري لا يحتوي دورة بلا وتر طولها4 أو أكثر؛ الوتر حافة بين رأسين غير متتابعين على الدورة. [1] وجود دورات أو مثلثات لا يناقض هذا الشرط.
• ترتيب الحذف المثالي يطلب أن يكون جيران كل رأس الذين يأتون بعده متجاورين زوجيًا، بحيث لا نحتاج إضافة حافة بينهم. [2] نفحص الجيران الباقين في الخطوة، لا عددهم وحده.
• المثال حوافه AB AC BC BD CD، ودرجات A B C D هي (2,3,3,2). A وD صالحان أولًا لأن جيرانهما B وC متصلان؛ B وC ليسا صالحين أولًا بسبب غياب AD.
• الترتيب A→D→B→C ينجح: جيران الخطوات اللاحقون BC ثم BC ثم C ثم لا أحد. بعد A يبقى مثلث BCD، ثم بعد D تبقى BC. المجموعة ذات صفر أو جار واحد تجتاز شرط الأزواج.
• الترتيب B→A→C→D يفشل من أول خطوة: جيران B هم A C D، وAD غائبة. الرسم نفسه وتري، لكن هذا الترتيب غير صالح. لا نضيف AD لإصلاح الفحص؛ هذا سيغير المدخل.
• في الدورة AB BC CD AD درجة كل رأس2، ولا رأس صالح أولًا لأن جاريه غير متصلين. وجود ترتيب صالح يمنع دورة مستحثة طولها4 أو أكثر: أسبق رأس عليها سيملك جارين لاحقين غير متصلين، وهو تناقض.
• فحصنا24 ترتيبًا لكل مدخل رباعي: للمثال12 صالحة، وللدورة0، وللكامل24، وللمسار8. وعلى1024 رسمًا خماسيًا راجعنا122880 ترتيبًا و27648 مرشح دورة؛822 مدخلًا وتريًا. هذا حصر محدود، وليس اختبار كل الأحجام أو سرعة خوارزمية.

عدد الجيران ليس قائمة حوافهم

الرسم الوتري لا يحتوي دورة بلا وتر طولها4 أو أكثر؛ الوتر حافة بين رأسين غير متتابعين على الدورة. [1] وجود دورات أو مثلثات لا يناقض هذا الشرط.

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

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

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

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

إزالة رأس تخرج حوافه، لكنها لا تنشئ حواف جديدة بين الناجين في فحصنا. بعض إجراءات ملء الرسوم تضيف حواف، وهو نموذج آخر. هنا إن غاب زوج مطلوب نسجل الفشل بدل إكماله بخط جديد في الصورة.

أربع رؤوس وخمس حواف معلنة

ثبت A B C D بالحواف AB AC BC BD CD. الحافة AD غير موجودة. A له B وC فقط، وD له B وC فقط؛ درجتاهما2. B له A C D، وC له A B D؛ درجتاهما3.

في أول خطوة، جيران A هم B وC، والحافة BC موجودة؛ إذن ينجح A أولًا. ينطبق الأمر على D أيضًا. أما جيران B الثلاثة، ففيهم AC وCD لكن AD غائبة، فلا يكونون زمرة. وعند C نحتاج AB وBD وAD، فيفشل بسبب AD نفسها.

في هذا الأصل المثلثان ABC وBCD؛ وحكمنا يستند إلى الأسماء والحواف. الدورة الرباعية A→B→D→C→A لها الوتر BC، فلا تقدم دورة مستحثة بلا وتر.

يمكن حصر دوراته الطويلة مباشرة: على أربع أسماء لا يوجد طول فوق4، وAD الغائبة تجبر الدورة الرباعية المعلنة في هذا المدخل. لها وتر BC؛ إذن الرسم وتري. لم نستخرج هذا الحكم من تساوي درجتين وحده.

الصورة الرئيسية تقارن A في هذا الأصل مع A في الدورة الرباعية AB BC CD AD. اللون الذهبي يحدد المرشح، والأزرق يحدد جيرانه. الذهب على BC يسارًا يعني أنها حافة موجودة بين الجارين؛ لا نرسم BD الغائبة يمينًا كأنها حافة.

ترتيب ينجح بعد تحديث الجيران

جرّب A→D→B→C. في خطوة A الأسماء اللاحقة D B C، لكن الجيران منهم B وC فقط. وجود D لاحقًا لا يجعله جارًا لـA. نراجع BC، فنجدها، ثم نخرج A وحافتي AB وAC.

تبقى B C D بالحواف BC BD CD، أي مثلث. يأتي D ثانيًا؛ جيرانه اللاحقون B وC، والحافة BC موجودة. نخرج D مع BD وCD، فلا يبقى سوى B وC وحافتهما.

يأتي B ثالثًا، وجاره اللاحق C وحده. لا يوجد زوج بين جارين نحتاج فحصه، فتنجح الخطوة. ثم يأتي C أخيرًا دون جيران لاحقين، فتنجح أيضًا. أربع خطوات ناجحة تعطي ترتيبًا كاملًا صالحًا.

لاحظ أن B لم يكن صالحًا أولًا، لكنه صالح بعد خروج A وD. الجيران الذين سببوا الزوج AD الغائب ليسوا في البقية الآن. استخدام قائمة الجيران الأصلية في خطوة B الثالثة سيختبر أسماء سبق إخراجها ويعطي رفضًا خاطئًا.

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

الرسم الوتري لا يجيز كل ترتيب

جرّب B→A→C→D في الأصل نفسه. قبل الحذف الأول، جيران B اللاحقون A C D. نفحص AC وCD وAD؛ الأولى والثانية موجودتان، والثالثة غائبة. هذا يكفي لرفض الترتيب من أول خطوة.

لو حذفنا B فعلًا لبقي A C D بالحافتين AC وCD، وAD غائبة. الصورة الداخلية اليمنى تظهر هذه البقية لتوضيح الزوج الذي لم يكن متصلًا بين جيران B. وجودها كصورة لا يعلن أن حذف B اجتاز الشرط.

لا نضيف AD ثم نقول إن الترتيب القديم نجح على الأصل. بإضافتها يصبح المدخل رسمًا كاملًا على أربعة أسماء، فتتغير قائمة الحواف من5 إلى6. في الكامل كل جيران لاحقين زمرة، فتنجح ترتيباته24 كلها.

في المثال ذي الحواف الخمس يوجد24 ترتيبًا ممكنًا. يجب أن يبدأ الصالح بـA أوD. حذف أي منهما يترك مثلثًا كاملًا، فتنجح كل ترتيبات الثلاثة الباقية، وعددها6 لكل بداية؛ لذلك المجموع12، لا24.

للمقارنة، المسار AB BC CD له8 ترتيبات صالحة: يبدأ من طرف، ثم يختار طرفًا من البقية حتى النهاية. لا يحتاج دورة أو وترًا ليمتلك ترتيبًا صالحًا؛ شرط الرسم الوتري على الدورات الطويلة يتحقق فيه لعدم وجودها.

لماذا تمنع الدورة الرباعية أول خطوة؟

في الدورة AB BC CD AD لا توجد AC أوBD. A له B وD، وهما غير متصلين؛ B له A وC دون AC؛ وينطبق الفشل نفسه على C وD. درجة كل رأس2، لكن لا اسم يجيز أول خطوة.

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

بوجه عام، افترض وجود ترتيب صالح، ووجود دورة مستحثة طولها4 أو أكثر. اختر أسبق رأس من أسماء الدورة في الترتيب. جاراه على الدورة يأتيان بعده، وهما مختلفان وغير متصلين لأن الدورة مستحثة بلا وتر وطولها ليس3.

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

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

راجع الأزواج في كل خطوة وحدد نطاق الحصر

راجعنا كل24 ترتيبًا في المثال والدورة الرباعية والكامل والمسار. النتائج12 و0 و24 و8 على الترتيب. سجلنا لكل خطوة الرأس وجيرانه اللاحقين والأزواج الغائبة؛ لم نكتف بقائمة درجات أو بوضع علامة نجاح على رأس البداية.

للفحص الإضافي أخذنا1024 رسمًا مسمى على خمسة أسماء. لكل مدخل120 ترتيبًا، فراجعنا1024×120=122880 ترتيبًا. في كل ترتيب فحصنا جميع الخطوات، وقررنا هل يوجد ترتيب صالح للمدخل.

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

على خمسة أسماء يوجد27 مرشح دورة بطول4 أو5 بعد حذف تكرار البداية والاتجاه، فالمجموع1024×27=27648 مرشحًا. وجدنا822 مدخلًا لا دورة مستحثة طويلة فيه، وتطابقت مع المدخلات التي لها ترتيب صالح ضمن هذا الحصر.

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

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