تقسيم الرسم أحادي الدورة: لماذا تبقى مطابقتان كاملتان؟

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

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

• الرسم أحادي الدورة متصل ويحتوي دورة واحدة بالضبط؛ يتساوى فيه عدد الحواف وعدد الرؤوس. [1] نفترض رسمًا محدودًا غير فارغ، بسيطًا وغير موجه وبلا حلقات أو أوزان؛ وجود دورة واحدة في الرسم كله يختلف عن وجود واحدة في كل مكون.
• تقسيم الحافة يستبدلها بحافتين عبر رأس جديد يصل طرفيها. [2] نقسم كل حافة أصلية مرة واحدة، وبوسيط مختلف لكل حافة. تزال الحافة القديمة، ولا نضيف غير الوصلتين الجديدتين. الناتج له n+m رؤوس و 2m حافة، وكل حافة فيه بين رأس قديم ووسيط جديد. درجات القدامى محفوظة، ودرجة كل وسيط 2.
• المطابقة الكاملة تختار حواف تجعل كل رأس طرفًا في حافة مختارة واحدة بالضبط. لا يجوز اختيار حافتين تشتركان في رأس. [3] في أصل حوافه AB وAC وBC وAD، نحصل على 8 رؤوس و 8 حواف. الورقة D تجبر D-sAD؛ ثم تبقى دورة سداسية. درجات A B C D هي 3 و 2 و 2 و 1.
• الحلان هما A-sAB B-sBC C-sAC D-sAD، أو A-sAC B-sAB C-sBC D-sAD. كل حل أربع حواف مستقلة يغطي الأسماء الثمانية؛ الحافة المفروضة وحدها لا تجعل الحل كاملًا أو وحيدًا.
• في كل مكون، عدد القدامى يجب أن يساوي عدد الوسطاء، أي n_i=m_i. للمكون المتصل هذه المساواة تعني دورة واحدة، ويعطي نزع الفروع ثم تناوب الدورة حلين. مكونان أصليان من مثلثين منفصلين يعطيان 4 حلول، كل منها 6 حواف. عدد الرؤوس 12 والحواف 12 في هذا الضبط.
• تقسيم K4 يعطي 10 رؤوس، لكن جهتي القديم والجديد حجمهما 4 و 6، فلا حل كامل؛ أكبر حجم 4. وحتى n=m في المجموع لا يكفي: مسار من 3 رؤوس مع رسم رباعي ذي 5 حواف يعطي 14 رأسًا بعد التقسيم، لكن المكونين غير متوازنين؛ أكبر حجم 6، ولا حل كامل. عدد حواف الناتج 12 في K4 و 14 في الضبط المنفصل؛ جهتا مكونيه 3/2 و 4/5.
• راجعنا 64 قائمة أصلية على أربعة أسماء:15625 مجموعة حواف مرشحة، و 1912 مطابقة صالحة، و 448 درجة، و 729 اختيارًا لطرف من كل حافة قديمة. اتفقت طرق الحصر؛15 أصلًا يملك حلًا، ومجموع حلولها الكاملة 30. هذا فحص محدود، لا بديل عن البرهان العام. للمثلث والورقة وحدهما 44 مطابقة بكل الأحجام، منها الحلّان الكاملان.

دورة واحدة في مكون متصل، لا دورة واحدة في المجموع

الرسم أحادي الدورة متصل ويحتوي دورة واحدة بالضبط؛ يتساوى فيه عدد الحواف وعدد الرؤوس. [1]

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

لدينا أربعة رؤوس وأربع حواف، ومكون واحد. المثلث هو الدورة الوحيدة، لأن D لا يملك إلا الجار A؛ لا يستطيع دخول دورة بسيطة يعود فيها دون إعادة استعمال الحافة نفسها.

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

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

وسيط مختلف لكل حافة، مع حذف الأصلية

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

نسمي وسيط AB بالاسم sAB، ووسيط AC بالاسم sAC، ووسيط AD بالاسم sAD، ووسيط BC بالاسم sBC. الرمز sAB اسم رأس واحد؛ لا يعني حافة إضافية تربط وسيطين ولا عملية ضرب بين الحروف.

نستبدل AB بالحافتين A-sAB وB-sAB. وبالمثل نعطي AC الوصلتين A-sAC وC-sAC، وAD الوصلتين A-sAD وD-sAD، وBC الوصلتين B-sBC وC-sBC. لا تبقى أي حافة قديمة بجانب الوصلتين.

قائمة الرؤوس الجديدة الكاملة هي A B C D sAB sAC sAD sBC. درجات القدامى 3 و 2 و 2 و 1 بالترتيب، وكل وسيط درجته 2. لدينا ثمانية رؤوس وثماني حواف، ومجموع الدرجات 16 يراجع طرفي كل حافة.

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

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

الورقة تجبر حافة، والدورة تمنح اختيارين

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

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

احذف D وsAD من مهمة التغطية بعد اختيار حافتهما، فتتبقى دورة A-sAB-B-sBC-C-sAC-A. فيها ستة أسماء وست حواف. يمكن تغطيتها باختيار A-sAB وB-sBC وC-sAC، أو A-sAC وB-sAB وC-sBC.

في الاختيار الأول، يستخدم A الوسيط sAB، فيجب أن يستخدم B وسيطه الآخر sBC، ويستخدم C ما بقي وهو sAC. وإذا بدأ A بالوسيط sAC انعكس التناوب، فاختار C الوسيط sBC، وB الوسيط sAB.

لا يوجد اختيار ثالث: جارا A في الدورة هما sAB وsAC فقط، وكل اختيار منهما يحدد البقية. نضيف D-sAD إلى كل حالة، فتحصل على المطابقتين الكاملتين المعلنتين في الصورة الرئيسية.

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

المطابقة الكاملة تحتاج توازنًا داخل كل مكون

في المكون الأصلي رقم i، يوجد n_i رأس قديم وm_i حافة. بعد تقسيمه يصبح الوسيط لكل حافة رأسًا جديدًا، فحجما جهتيه هما n_i وm_i. كل حافة مختارة تغطي قديمًا واحدًا وجديدًا واحدًا.

إذا غطت المطابقة جميع رؤوس المكون، يجب أن تتساوى الجهتان: n_i=m_i. ليس مجرد كون المجموع n_i+m_i زوجيًا شرطًا كافيًا؛ فقد يكون 4+6 زوجيًا مع بقاء رأسين في الجهة الأكبر دون شريك.

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

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

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

نزع الفروع يترك تناوب الدورة وحده

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

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

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

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

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

في c مكونات منفصلة من هذا النوع، نختار أحد الحلين في كل مكون على نحو مستقل، فيكون العدد 2×2×…×2=2^c. اتحاد الخيارات صالح لأن المكونات لا تتشارك رأسًا أو حافة؛ وإذا فشل مكون واحد، فلا حل كامل للرسم كله.

الأعداد الكلية لا تعوض توازن المكونات

خذ K4، أي جميع الحواف الست بين A وB وC وD. بعد تقسيمها يصبح القديم أربعة رؤوس والجديد ستة، فيكون المجموع 10 رؤوس و 12 حافة. كل حافة مطابقة تستعمل رأسًا قديمًا مختلفًا، فلا يمكن أن يزيد الحجم على 4.

نحقق الأربع باختيار A-sAB وB-sBC وC-sCD وD-sAD. هذه مطابقة تغطي القدامى كلهم، لكن sAC وsBD يبقيان حرين. لذلك أكبر حجم 4، ولا توجد مطابقة كاملة تحتاج خمس حواف. كون الرسم الناتج ثنائيًا ومتصلًا لا يلغي تفاوت الجهتين.

وللمقارنة، خذ مثلثين منفصلين ABC وDEF. كل مكون أصلي أحادي الدورة، فتتحول كل دورة إلى سداسية ذات حلين. عدد الاختيارات الكلية 2×2=4، وكل حل منها ست حواف على 12 رأسًا. عدم الاتصال لا يمنع الحل هنا.

الضبط الأخير يجمع مسار A-B-C مع مكون على D E F G حوافه DE وDF وDG وEF وEG. في الأول 3 رؤوس و 2 حافة، وفي الثاني 4 رؤوس و 5 حواف؛ المجموع 7 رؤوس و 7 حواف قديمة.

بعد التقسيم يصبح المجموع 14 رأسًا و 14 حافة، وجهتا القديم والجديد متساويتين في الرسم كله. لكن المكون الأول حجمهما 3 و 2، والثاني 4 و 5. لا توجد حافة بين المكونين لتنقل شريكًا من الجهة الزائدة في أحدهما إلى الآخر.

أكبر حجم في المسار المقسم 2، وفي المكون الرباعي المقسم 4، فيكون الأكبر 6 للرسم المنفصل. يحتاج الحل الكامل على 14 رأسًا سبع حواف، فلا يوجد. مثالنا يبين الفرق بين n=m في المجموع وn_i=m_i في كل مكون، لا فشل شرط صحيح للمكونات.

الصورة الداخلية تعرض المكونين المقسمين بقائمتي حوافهما الكاملة، وتبرز أكبر مطابقة في كل منهما. يسارًا A-sAB وC-sBC تحققان 2، ويمينًا D-sDE وE-sEF وF-sDF وG-sDG تحقق 4. لا تزيد المطابقة على عدد الجهة الأصغر في كل مكون. النتيجة العامة هنا تخص تقسيم الحواف بالنموذج المعلن؛ تساوي الجهتين في رسم ثنائي آخر لا يقدم وحده هذا البرهان.

الحساب يراجع نماذج محددة والبرهان يحدد الشرط

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

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

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

بلغ مجموع اختيارات الأطراف 729، وراجعنا 448 درجة في النواتج. ظهرت مطابقة كاملة في 15 أصلًا من 64، وجميع هذه الأصول الرباعية متصلة وأحادية الدورة؛ لكل منها حلان، فالمجموع 30. المثال ذو المثلث والورقة وحده له 44 مطابقة بكل الأحجام، منها حلان كاملان.

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

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

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