إكليل الرسم: لماذا تفرض الأوراق مطابقة كاملة وحيدة؟

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

لأن كل ورقة جديدة لها جار واحد فقط؛ تغطيتها في مطابقة كاملة تجبر حافتها الخاصة. الحواف Aa وBb وCc وDd منفصلة الأطراف وتغطي الرؤوس الثمانية، فتوجد مطابقة كاملة واحدة بحجم 4. هذه النتيجة تخص الإضافة المحددة، وقد تفشل وحدانيتها بعد وصل ورقتين.

• إكليل G مع K1 يحتفظ بالرسم الأصلي، ويضيف لكل رأس نسخة خاصة من رأس واحد، ثم يصل الرأس الأصلي بنسخته فقط. كل رأس جديد ورقة درجتها 1. [1] [2]
• المطابقة الكاملة مجموعة حواف تجعل كل رأس طرفًا في حافة مختارة واحدة بالضبط. لا تسمح باستعمال الرأس نفسه في حافتين. [3] في مثال المسار ذي الحواف AB وBC وCD، نضيف Aa وBb وCc وDd فقط: ثمانية رؤوس وسبع حواف.
• إذا كان الأصل يضم n رأسًا وm حافة، صار الإكليل مع K1 ذا 2n رأسًا وm+n حافة. تزيد درجة كل رأس قديم بواحد، ودرجة كل رأس جديد 1. [1]
• كل ورقة تجبر حافتها الخاصة، وهذه الحواف تغطي الرؤوس القديمة أيضًا. لذلك وجود المطابقة ووحدانيتها ثابتان لأي أصل محدود غير فارغ، بسيط وغير موجه وبلا حلقات أو أوزان، حتى لو كان غير متصل أو احتوى مثلثًا؛ لا نحتاج شرط الثنائية.
• المطابقة maximal لا تقبل إضافة حافة وحدها مع إبقاء الاختيار؛ أما maximum فهي الأكبر عددًا بين جميع المطابقات. هذان شرطان مختلفان. [4]
• في الرسم الأصلي الجديد، AB وCD اختيار maximal من حافتين، لا أكبر مطابقة ذات 4. إذا أضفنا ab، صارت هناك مطابقتان كاملتان: Aa Bb Cc Dd وAB ab Cc Dd. حذف Aa بدلًا من ذلك يعزل a ويمنع أي مطابقة كاملة؛ أكبر حجم يصبح 3.
• راجعنا جميع 64 رسمًا أصليًا على أربعة أسماء ثابتة: اتفقت طريقتا الحصر على 1840 مطابقة صالحة، بعد اختبار 11664 مجموعة حواف و 6720 تقسيمًا كاملًا للأطراف إلى أزواج. ظهرت مطابقة كاملة وحيدة في كل إكليل، وراجعنا 512 درجة. هذه أعداد فحوص محدودة، وليست عدد الحلول في مثال المسار وحده. مثال المسار وحده يملك 29 مطابقة بكل الأحجام، منها واحدة كاملة.

ورقة خاصة بكل رأس، لا رأس واحد مشترك

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

K1 يعني رسمًا من رأس واحد بلا حافة، ونأخذ نسخة مختلفة منه لكل رأس في الأصل. نسمي نسخة A بالرأس a، ونسخة B بالرأس b، وهكذا. اختلاف حالة الحرف هنا يميز اسمين: A وa ليسا الرأس نفسه.

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

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

نسمي العملية هنا إكليل الرسم مع K1 لتحديد المقصود من Graph Corona Product. كلمة الإكليل وحدها لا تعني أن نضع الرؤوس على دائرة، ولا تفرض أطوالًا على حوافها؛ قائمة الاتصالات هي التي تحدد الرسم.

المسار يعطي ثمانية رؤوس وسبع حواف

نثبت الأصل على الرؤوس A وB وC وD، وحوافه الثلاث AB وBC وCD. بعد الإضافة تصبح قائمة الرؤوس A B C D a b c d؛ وقائمة الحواف AB BC CD Aa Bb Cc Dd، ولا حافة أخرى.

إذا كان الأصل يضم n رأسًا وm حافة، صار الإكليل مع K1 ذا 2n رأسًا وm+n حافة. تزيد درجة كل رأس قديم بواحد، ودرجة كل رأس جديد 1. [1]

في المثال n=4 وm=3، فعدد الرؤوس 8 وعدد الحواف 7. درجات الرؤوس القديمة بالترتيب A B C D هي 2 و 3 و 3 و 2، بعد أن كانت 1 و 2 و 2 و 1. درجات a وb وc وd كلها 1.

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

اختيار Aa وBb وCc وDd يستخدم كل اسم مرة واحدة. أما إضافة AB إلى هذا الاختيار فتكرر A وB، ولذلك لا تكون المجموعة الناتجة مطابقة. لون الحافة المختارة في الصورة إشارة للاختيار فقط، لا وزنًا أو اتجاهًا.

الورقة تثبت الوجود والوحدانية معًا

المطابقة الكاملة مجموعة حواف تجعل كل رأس طرفًا في حافة مختارة واحدة بالضبط. لا تسمح باستعمال الرأس نفسه في حافتين. [3]

ابدأ بالورقة a. كي تدخل في حافة من مطابقة كاملة، لا بد أن تختار Aa، لأنها الحافة الوحيدة المتصلة بها. وبالسبب نفسه تفرض b الحافة Bb، وc الحافة Cc، وd الحافة Dd.

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

والحواف نفسها تثبت الوحدانية: أي مطابقة كاملة مفترضة يجب أن تحتوي الأربع، ولم يبق رأس حر لحافة أخرى. لذلك لا يمكن استبدال Aa وBb بالحافة AB؛ سيكون a وb بلا شريك في الرسم ذي الحواف السبع.

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

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

اختيار لا يقبل إضافة حافة قد يبقى أصغر

المطابقة maximal لا تقبل إضافة حافة وحدها مع إبقاء الاختيار؛ أما maximum فهي الأكبر عددًا بين جميع المطابقات. هذان شرطان مختلفان. [4]

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

لكن هذا الاختيار حجمه 2، ولدينا بالفعل Aa Bb Cc Dd بحجم 4. عدم إمكان الإضافة مباشرة لا يجعله كاملًا أو أكبر عددًا. الوصول إلى الأربع يحتاج تغيير الاختيار، لا إلحاق حافة بالاثنتين مع الاحتفاظ بهما.

هذا الفرق تمهيد لقراءة النتيجة فقط: وحدانية المطابقة الكاملة لا تعني أن كل اختيار متوقف عن الإضافة يساويها. فقد وجد الحصر في إكليل المسار مطابقات maximal بأحجام 2 و 3 و 4، بينما الأكبر والكامل بحجم 4 وحده.

حافة بين ورقتين تفتح اختيارًا ثانيًا

أضف الحافة ab وحدها إلى الحواف السبع السابقة، وأبق جميع الرؤوس. صار عدد الحواف 8، ودرجتا a وb تساويان 2. لم تعودا ورقتين في هذا الرسم المعدل، ولذلك لا ينطبق عليه شرط الإضافة الأصلية كما كان.

المطابقة Aa Bb Cc Dd لا تزال صحيحة؛ لم نحذف حوافها. لكن نستطيع الآن اختيار AB وab وCc وDd. الحافتان AB وab تغطيان أربعة أسماء مختلفة A وB وa وb، وتكمل الحافتان الأخريان بقية الأسماء.

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

ولإثبات أن العدد هنا اثنتان بالضبط، لاحظ أن c وd ما زالتا درجتهما 1، فتجبران Cc وDd. يبقى A وB وa وb، وحوافها AB وAa وBb وab. إما أن نختار Aa ومعها Bb، أو AB ومعها ab؛ لا يوجد اختيار ثالث يغطي الأربعة.

الصورة الداخلية تميز الاختيارين على الرسم المعدل نفسه. لا نعرض حواف المطابقتين وكأنها مطابقة واحدة؛ اتحادهما يكرر أطراف A وB وa وb. كل لوحة تعرض اختيارًا مستقلًا كاملًا.

حذف حافة ورقة يزيل الوجود، وعزل الأصل لا يزيله

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

لدينا Bb وCc وDd مطابقة بحجم 3. ولا يمكن أن يصبح الحجم 4، لأنه كان سيغطي الأسماء الثمانية بما فيها a المعزول. إذن الحجم الأكبر بعد هذا الحذف 3. حذف حافة لا يساوي حذف طرفيها؛ عدد الرؤوس هنا ما زال 8.

وفي المقابل، خذ أربعة رؤوس أصلية A B C D بلا أي حافة بينها، ثم أضف ورقة خاصة بكل واحد بالطريقة الصحيحة. تحصل على الحواف الأربع Aa Bb Cc Dd، وعلى أربعة مكونات، لكل منها رأس قديم وورقته.

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

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

ما الذي أثبته الحصر وما الذي أثبته البرهان؟

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

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

بلغ مجموع مجموعات الحواف المختبرة 11664 عبر الإكليلات 64، وكان مجموع المطابقات الصالحة 1840. هذه أعداد مجمعة لرسوم مختلفة؛ مثال المسار وحده يملك 29 مطابقة بكل الأحجام، منها مطابقة كاملة واحدة.

وللمطابقات الكاملة أجرينا فحصًا آخر: لكل رسم ثمانية رؤوس، توجد 105 طرق لتقسيم الأسماء إلى أربعة أزواج إذا تجاهلنا الحواف أولًا. فحصنا 64×105=6720 تقسيمًا، واحتفظنا فقط بما تكون أزواجه حواف موجودة. النتيجة الوحيدة في كل رسم هي حواف الأوراق الأربع.

راجعنا أيضًا 512 درجة، أي 64×8، وعد الحواف، وأمثلة إضافة ab وحذف Aa. الحصر يخص الأسماء والأحجام المحددة، ولا يثبت وحده النتيجة لكل n أو يقيس سرعة خوارزمية عامة. البرهان الذي يبدأ بجار كل ورقة يثبت النتيجة العامة.

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