المطابقة المستحثة: لماذا يفسد جسر بين زوجين؟

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

لأن المطابقة المستحثة تمنع الحواف الإضافية بين أطراف الحواف المختارة، حتى لو لم نختَر تلك الحواف الإضافية. في المسار AB BC CD، الاختيار AB CD مستقل، لكن BC تبقى بين أطرافه فتفسده. حذف BC من الرسم نفسه يجعل الزوجين مطابقة مستحثة بحجم 2؛ تركها غير مختارة لا يفعل ذلك.

• المطابقة المستحثة تختار حواف مستقلة الأطراف، ولا توجد بين أطرافها حواف أصلية أخرى غير المختارة؛ كل مطابقة مستحثة مطابقة عادية، والعكس ليس لازمًا. [1] نفترض رسمًا محدودًا وبسيطًا وغير موجه وبلا حلقات أو أوزان؛ قائمة الرؤوس غير فارغة، وقد تكون الحواف فارغة.
• الرسم المستحث على مجموعة رؤوس يحتفظ بهذه الرؤوس وبكل حافة أصلية يقع طرفاها فيها. [2] نأخذ مجموعة أطراف الحواف المختارة؛ الاستحثاث يختلف عن الرسم الذي يحفظ الحواف المختارة وحدها.
• في المسار AB BC CD، أكبر مطابقة عادية AB CD بحجم 2، لكنها غير مستحثة بسبب BC. أكبر حجم مستحث 1، وله ثلاثة اختيارات منفردة: AB أوBC أوCD. بعد حذف BC مع إبقاء الرؤوس الأربعة، تصبح AB CD مستحثة كاملة وحيدة بحجم 2.
• في أي مطابقة عادية، كل حافة إضافية بين الأطراف تصل طرفين من زوجين مختلفين. لذلك فحص الرسم المستحث وفحص الحواف بين كل زوجين يكافئان بعضهما في نموذجنا. الأكبر المستحث لا يتجاوز الأكبر العادي؛ تشديد الشرط قد يصغر الحجم.
• في الدورة C4 بحواف AB AD BC CD، كل مطابقة عادية من حافتين تترك حافتين إضافيتين بين الأطراف؛ الأكبر المستحث 1 بأربعة اختيارات. أما AB BC فتفشل شرط المطابقة نفسه لأن B مشترك. في C6، AB DE مستحثة بحجم 2، مقابل أكبر عادي 3؛ لا تصلح أي مطابقة من 3 لأن أطرافها جميع الرؤوس فتحتفظ الدورة بحوافها الست. للمستحث الأكبر ثلاثة اختيارات.
• المثلث والمثلث مع معزول D لهما أكبر مستحث 1 وثلاثة اختيارات؛ المعزول لا يدخل أطراف حافة مختارة. الرسم ذو أربعة رؤوس بلا حواف له مطابقة مستحثة فارغة وحيدة بحجم 0. ولا يلزم لمس كل رأس أو الهيمنة على كل حافة: AB وحدها في المسار مستحثة، لكنها لا تلامس CD.
• راجعنا 64 قائمة حواف على أربعة أسماء:729 مرشحًا و 304 مطابقات عادية، منها 259 مستحثة، بإجمالي 190 مجموعة تحقق الأكبر المستحث في مدخلاتها. ظهر فرق الحجمين في 34 مدخلًا؛ اتفق فحص الحواف بين الزوجين مع الاستحثاث في 304 مطابقة، والحصر المستقل في 64 مدخلًا. هذه أعداد محدودة، لا صيغة عامة أو ادعاء سرعة خوارزمية.

استقلال الأطراف شرط أول، والاستحثاث شرط إضافي

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

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

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

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

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

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

الحافة الوسطى تفسد اختيار الزوجين في المسار

المسار A-B-C-D له الحواف AB وBC وCD فقط. اختر AB وCD. الأطراف الأربعة A وB وC وD مختلفة، والحافتان مستقلتان؛ هما أكبر مطابقة عادية بحجم 2، لأن ثلاثة أزواج مستقلة كانت تحتاج ستة رؤوس.

لكن مجموعة الأطراف هي الرؤوس الأربعة كلها. لذلك نجد داخلها AB وBC وCD، لا AB وCD وحدهما. الحافة BC تصل B من الزوج الأول إلى C من الثاني؛ هي الحافة الإضافية التي تمنع الاستحثاث.

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

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

الصورة الرئيسية تعرض AB CD على المسار كاملًا، مع BC باللون الأحمر لأنها متروكة في الاختيار لكنها باقية في الأصل وبين الأطراف. لا تساوي «متروكة» هنا «محذوفة»، ولا نخفي الخط لإعطاء شهادة استحثاث خاطئة.

احذف الآن BC من قائمة الأصل فعلًا، مع إبقاء A B C D والحافتين AB وCD. صار الرسم مكوّنًا من زوجين منفصلين. اختيار AB CD يبقي على الأطراف الحافتين نفسيهما فقط، فيكون مستحثًا بحجم 2.

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

احتفظ بكل ما بين الأطراف، لا بما اخترته فقط

الرسم المستحث على مجموعة رؤوس يحتفظ بهذه الرؤوس وبكل حافة أصلية يقع طرفاها فيها. [2]

إذا اخترنا حواف M، فلنسم مجموعة أطرافها U. نحفظ كل حافة في الأصل يكون طرفاها في U، ثم نقارن المجموعة الناتجة بـM. المطابقة المستحثة تتطلب أن تكون المجموعتان متساويتين، بعد التأكد من استقلال أطراف M.

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

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

من هنا يكافئ الاختبار فحص كل زوج من الحواف المختارة: بعد التأكد من عدم وجود طرف مشترك، هل توجد حافة أصلية تصل طرفًا من الأولى بطرف من الثانية؟ وجود واحدة يكفي للرفض، وغيابها لكل الأزواج يعني عدم وجود أي حافة إضافية.

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

إذا احتفظنا بالحواف المختارة وحدها، فسيمر AB CD في المسار لأننا أسقطنا BC مقدمًا. ذلك يختبر قائمة مختارة، ولا يختبر الرسم المستحث على الأطراف. يجب الرجوع إلى حواف الأصل كاملة قبل إصدار الحكم.

الدورة الرباعية تترك رابطين بين الزوجين

خذ الدورة A-B-C-D-A بحواف AB وAD وBC وCD. أكبر مطابقة عادية حجمها 2، ولها اختياران: AB CD، أوAD BC. كل اختيار يصل إلى الرؤوس الأربعة دون طرف مشترك.

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

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

كل حافة منفردة مستحثة على طرفيها، فتبلغ أكبر حجم مستحث 1. الاختيارات الأربعة هي AB وAD وBC وCD. لا نخلط عدد هذه المجموعات مع حجم كل مجموعة؛ الحجم 1 وعدد الاختيارات 4.

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

وفي الدورة نفسها، اختيار AB BC يفشل قبل سؤال الاستحثاث، لأنه يشترك في B. تحقق من المطابقة أولًا، ثم من الحواف الإضافية؛ لا يستبدل الاختبار الثاني شرط الاستقلال الأول.

الدورة السداسية تقبل زوجين مستحثين

نأخذ C6 كاملة بحواف AB AF BC CD DE EF. اختر AB وDE. الأطراف المختارة A وB وD وE، ولا تشترك الحافتان في رأس.

بين هذه الأطراف لا توجد إلا AB وDE. الحافة AF طرفها F خارج المجموعة، وBC طرفها C خارجها، وكذلك CD وEF. تبقى هذه الحواف في الرسم الأصلي، لكنها لا تقع بكامل طرفيها داخل المجموعة U.

إذن AB DE مطابقة مستحثة بحجم 2. اللوحة الداخلية تبقي الرؤوس الست والحواف الست، وتميز C وF بلون محايد لأنهما ليسا طرفين للمختار. لا نحذفهما من الأصل ولا ندعي الوصول إليهما.

توجد مطابقة عادية من ثلاث حواف مثل AB CD EF، فيكون الأكبر العادي 3؛ أكثر من 3 كان يحتاج أكثر من ستة رؤوس. لكن أي مطابقة من 3 على الستة تستعمل الرؤوس الست كلها، فيحتفظ الرسم المستحث بالحواف الست بدل المختارة الثلاث.

إذن لا توجد مطابقة مستحثة من 3. ومع شاهد AB DE بحجم 2، ثبت أن الأكبر المستحث 2. وله ثلاثة اختيارات: AB DE، وAF CD، وBC EF؛ كل واحد زوج من حافتين متقابلتين في هذه الدورة.

وجود رؤوس خارج الأطراف لا يفسد الاستحثاث. وليس كل مستحث مهيمنًا على كل حافة: AB وحدها في المسار مستحثة على A وB، لكنها لا تلامس CD. في الدورة السداسية يحقق AB DE الشرطين معًا، لكن هذا الاتفاق في اختيار محدد لا يجعل الشرطين متطابقين.

المعزول لا يدخل الأطراف، والفارغة تظل اختيارًا

في المثلث A B C وحوافه AB AC BC، أكبر مطابقة عادية حافة واحدة. كل واحدة مستحثة على طرفيها في الرسم البسيط، فيكون الأكبر المستحث 1 أيضًا بثلاثة اختيارات.

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

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

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

في كل الضوابط، نقيس الحجم بعدد الحواف المختارة، وعدد الحلول بعدد المجموعات المختلفة. ترتيب AB ثمCD لا يعطي حلًا آخر عن CD ثمAB. ولهذا نذكر اختيارًا فارغًا واحدًا، لا صفر اختيارات في الرسم بلا حواف.

اختباران يراجعان الحواف الإضافية بدقة

على أربعة أسماء A B C D توجد ستة أزواج ممكنة؛ أخذنا كل واحدة من 2^6=64 قائمة حواف بسيطة غير موجهة. لكل قائمة حصرنا كل مجموعة جزئية واختبرنا استقلال الأطراف قبل شرط الاستحثاث.

بلغ مجموع المرشحات 729، ومجموع المطابقات العادية 304. حسبنا مجموعة أطراف كل مطابقة، واحتفظنا بكل حافة أصلية يقع طرفاها فيها؛ اجتازت المساواة مع المختار 259 مطابقة مستحثة عبر المدخلات كلها.

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

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

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

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

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