إلحاق مسار بكل رأس: هل يضمن مطابقة كاملة؟

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

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

• في الضرب الجذري، نأخذ نسخة من رسم ذي رأس محدد لكل رأس من الأصل؛ تقابل الجذور الرؤوس القديمة، وتصل حواف الأصل بين هذه الجذور. [1] نحدد النسخة هنا بالمسار v-x-y، وجذره v عند الطرف؛ x وy رأسان جديدان مختلفان لكل رأس قديم. نفترض أصلًا محدودًا غير فارغ وبسيطًا وغير موجه وبلا حلقات أو أوزان، ولا نضيف وصلات أخرى.
• المطابقة الكاملة مجموعة حواف تجعل كل رأس طرفًا في حافة مختارة واحدة بالضبط. لا يجوز اختيار حافتين تشتركان في رأس. [2] في الأصل ذي n رؤوس وm حافة، نضيف رأسين وحافتين لكل رأس: الناتج له 3n رؤوس وm+2n حافة.
• كل y له جار واحد هو x، فتجبر المطابقة الكاملة جميع حواف x-y. بعد اختيارها يبقى الرؤوس القديمة وحدها؛ اختيار حافة v-x يترك y بلا شريك.
• الدورة ذات الحواف AB وBC وCD وAD لها مطابقتان كاملتان: AB CD أو AD BC. كل واحدة تمتد بإضافة a1a2 وb1b2 وc1c2 وd1d2 إلى مطابقة من 6 حواف على 12 رأسًا.
• إذا كان الجذر في وسط المسار، يصبح لكل رأس قديم ورقتان لا تملكان جارًا سواه. تغطيتهما تحتاج حافتين تشتركان في ذلك الرأس، وهذا ممنوع؛ عدد الرؤوس الزوجي لا يعالج التعارض. في الدورة ذات الجذر الأوسط، أكبر حجم 4: نختار حافة ورقة واحدة لكل رأس قديم.
• أكبر حجم مطابقة بعد الإلحاق الطرفي هو n+ν(G)، حيث ν(G) أكبر حجم في الأصل. للمسار P4 نحصل على 6 وحل كامل وحيد؛ وللنجمة ذات أربع رؤوس نحصل على 5 دون حل كامل.
• راجعنا 64 قائمة حواف أصلية على أربعة أسماء ثابتة، باستخدام حصر المطابقات بطريقتين وبناء مستقل لتحديد الجذر. شملت 186624 مجموعة حواف مرشحة و 12864 مطابقة صالحة و 768 درجة؛ الفحص محدود بهذا النطاق، والبرهان العام يعتمد على حواف الأوراق. امتدت 48 مطابقة كاملة قديمة إلى 48 جديدة، و 37 أصلًا من 64 يملك حلًا على الأقل.

ثبت موضع الجذر قبل أن تنسخ المسار

في الضرب الجذري، نأخذ نسخة من رسم ذي رأس محدد لكل رأس من الأصل؛ تقابل الجذور الرؤوس القديمة، وتصل حواف الأصل بين هذه الجذور. [1]

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

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

سنكتب الإضافة عند A بالمسار A-a1-a2، وعند B بالمسار B-b1-b2، وكذلك C وD. الأسماء a1 وa2 رأسان مختلفان، وليسا وزنًا للحافة أو نسخهما الحرفية داخل الرسم القديم.

إذا اخترنا وسط المسار جذرًا، يصبح الإنشاء x-v-y، لا v-x-y. هذا تغيير في الاتصال رغم أن كل نسخة تضيف رأسين وحافتين. تحديد رسم النسخة وحده لا يحدد النتيجة؛ نحتاج رأسه الجذري أيضًا.

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

دورة صغيرة تعطي مطابقتين كاملتين

الأصل دورة بأسماء A وB وC وD وحواف AB وBC وCD وAD. كل رأس قديم درجته 2. بعد الإلحاق الطرفي نضيف A-a1 وa1-a2، وB-b1 وb1-b2، وC-c1 وc1-c2، وD-d1 وd1-d2.

هذه قائمة كاملة: أربع حواف قديمة وثماني حواف جديدة، أي 12 حافة على 12 رأسًا. درجة كل رأس قديم 3، ودرجة كل اسم ينتهي بالرقم 1 تساوي 2، ودرجة كل اسم ينتهي بالرقم 2 تساوي 1.

مجموع الدرجات 4×3+4×2+4×1=24، وهو ضعف الحواف 12. عدد الحواف الكلي مختلف عن عدد حواف المطابقة الكاملة؛ الأخيرة تحتاج ست حواف مستقلة لتغطي الرؤوس الاثني عشر مرة لكل رأس.

في الدورة القديمة يمكن اختيار AB وCD، أو AD وBC. لإثبات أن هذين هما كل الحلول الكاملة، افحص شريك A: إما B فتتبقى CD، وإما D فتتبقى BC. لا توجد AC كي تقدم اختيارًا ثالثًا.

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

الحافة الإجبارية تترك الرأس القديم بلا شريك

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

الرأس a2 درجته 1 وجاره a1 فقط. كي يغطيه حل كامل يجب اختيار a1-a2. وبالسبب نفسه تجبر الأوراق b2 وc2 وd2 الحواف b1-b2 وc1-c2 وd1-d2.

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

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

بعد فرض الحواف الجديدة-الجديدة، تكون كل وصلة بين رأس قديم ورأس جديد غير متاحة. لا تبقى لتغطية الرؤوس القديمة إلا حواف الأصل نفسه. في الدورة نحتاج مطابقة كاملة من الحافتين AB CD أو AD BC.

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

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

خذ أي مطابقة كاملة في الرسم بعد الإلحاق الطرفي. كل ورقة نهائية y تفرض x-y، فتحتوي المطابقة جميع الحواف n من هذا النوع. حذفها من الاختيار يترك حواف قديمة تغطي جميع الرؤوس القديمة دون تكرار؛ أي مطابقة كاملة في الأصل.

وبالعكس، خذ أي مطابقة كاملة في الأصل. أضف إليها الحافة x-y من كل نسخة. أطراف الحواف المضافة جديدة، ومختلفة بين النسخ، ولا تشترك مع أطراف حواف الأصل؛ فتغطي المجموعة الناتجة جميع الرؤوس 3n مرة واحدة.

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

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

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

الجذر الأوسط يجبر حافتين متعارضتين

نرجع إلى الدورة نفسها ونغير موضع الجذر داخل كل نسخة من المسار. عند A نضيف A-a1 وA-a2، وعند B نضيف B-b1 وB-b2، وهكذا. لا توجد حافة a1-a2 في هذا الإنشاء.

الرأسان a1 وa2 الآن ورقتان، ولكل منهما الجار A وحده. تغطية a1 تجبر A-a1، وتغطية a2 تجبر A-a2. لكن الحافتين تشتركان في A، فلا يمكن أن تنتميا معًا إلى مطابقة.

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

ما زال لدينا 12 رأسًا و 12 حافة في مثال الدورة. لكن درجات الرؤوس القديمة صارت 4 بدل 3، ودرجات الرؤوس الجديدة كلها 1 بدل التناوب 2 و 1. تساوي العددين لا يجعل الرسمين متماثلين ولا يحفظ حلول المطابقة.

أكبر حجم في مثال الدورة ذات الجذر الأوسط 4. كل حافة في الرسم تلمس رأسًا قديمًا واحدًا على الأقل، والحواف المختارة لا تتشارك رأسًا، فلا يمكن أن يزيد عددها على الرؤوس القديمة الأربعة. ونحقق الأربع باختيار A-a1 وB-b1 وC-c1 وD-d1، مع ترك الورقة الثانية عند كل رأس حرة.

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

الحجم الأكبر يساوي n زائد أكبر حجم في الأصل

لنرمز إلى أكبر عدد حواف في مطابقة الأصل بالرمز ν(G). في أي مطابقة بالناتج، لا يمكن اختيار الحافتين v-x وx-y من النسخة نفسها، لأنهما تشتركان في x. إذن مساهمة جميع الإضافات لا تزيد على n حواف.

الحواف القديمة المختارة أيضًا مطابقة في G، فلا يزيد عددها على ν(G). بجمع الحدين نحصل على أن حجم أي مطابقة بالناتج لا يزيد على n+ν(G). هذا الحد لا يفترض أن المطابقة كاملة.

نحقق الحد باختيار جميع حواف x-y، وإضافة أكبر مطابقة في G. المجموعتان لا تتشاركان أي رأس، فتحصل على مطابقة صحيحة حجمهاn+ν(G). اجتماع حد أعلى واختيار يبلغه يثبت القيمة، لا وحدانية المطابقة الأكبر.

إذا كان الأصل مسار A-B-C-D، فأكبر حجم فيه 2، ومطابقته الكاملة الوحيدة AB CD. بعد الإلحاق نحصل على 4+2=6، وعلى حل كامل وحيد. عدد الحواف هنا 11، لأن الأصل له ثلاث حواف بدل أربع حواف الدورة.

إذا كان الأصل نجمة حوافها AB وAC وAD، فإن كل حافتين قديمتين تشتركان في A، فأكبر حجم فيه 1. بعد الإلحاق يصبح الأكبر 4+1=5؛ توجد 12 رأسًا لكن المطابقة الأكبر تغطي عشرة فقط.

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

الحصر المحدود يراجع الأمثلة ولا يحل محل البرهان

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

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

بلغ مجموع مجموعات الحواف المرشحة 186624، ومجموع المطابقات الصالحة 12864 عبر الرسوم الأربعة والستين. راجعنا 768 قيمة درجة، أي 64×12، وتحقق حد الحجمn+ν(G) لكل أصل.

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

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

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

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