متانة الرسم: هل يكفي أصغر قطع رؤوس؟

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

لا؛ القطع الذي يصغر عدد المحذوف وحده قد يفوت النسبة الأصغر. في رسمنا، A هو القطع الوحيد من رأس واحد ونسبته1/2، بينما AB من رأسين ونسبته1/3. نثبت أن أي قطع آخر لا يخفضها، فتكون المتانة1/3. المقام عدد كل المكونات الباقية، بما فيها الرؤوس المعزولة التي لم تُحذف، مع إخراج الأسماء المحذوفة نفسها.

• متانة الرسم المتصل غير الكامل هي أصغر نسبة بين عدد الرؤوس المحذوفة وعدد المكونات الباقية، عبر جميع قطع الرؤوس التي تفصل الرسم. لا نقتصر على القطع الأصغر حجمًا. [1] هنا نحسب النسبة فقط عندما يبقى أكثر من مكون.
• قطع الرؤوس يحذف الأسماء المختارة وكل الحواف التي تمسها، فيفصل الرسم المتصل إلى عدة مكونات. [2] لا نبقي اسمًا محذوفًا كدائرة معزولة، ولا نحذف رأسًا باقياً لمجرد أنه بلا جيران.
• نصل A وB بكل من C D E F G، ونضيف AB، ثم قطعة K4 على A H I J. A يتصل بكل اسم آخر، والأصل عشرة رؤوس و17 حافة؛ C إلى G مستقلة عن بعضها.
• حذف A يترك نجمة حول B على ستة رؤوس، ومثلث HIJ: تسعة رؤوس وثماني حواف ومكونان، والنسبة1/2. الأصل متصل، وحذف أي رأس آخر يبقي A، فلا يفصل؛ A أصغر قطع وحيد.
• حذف AB يترك C D E F G معزولين ومثلث HIJ، أي ثمانية رؤوس وثلاث حواف وستة مكونات. النسبة2/6=1/3، وتقل عن1/2؛ مجموعة أكبر أعطت نسبة أصغر.
• إذا بقي A فلا فصل. إذا حُذف A وبقي B، فالمكونات اثنان على الأكثر والنسبة لا تقل عن1/2. وإذا حُذف AB، فالمكونات ستة على الأكثر والنسبة لا تقل عن1/3؛ الحالة المحققة تثبت المتانة1/3.
• راجعنا جميع1024 مجموعة حذف في المثال، و23264 مجموعة عبر727 رسمًا متصلًا غير كامل على خمسة رؤوس، بمقارنة كسور دقيقة ومكونات محسوبة بطريقتين. النطاق لا يشمل اصطلاحات الرسم الكامل أو المنفصل أو كل الأحجام.

صغّر النسبة، لا البسط وحده

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

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

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

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

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

رأس شامل ومجموعتان لهما اتصال معلوم

نثبت الأسماء A B C D E F G H I J. نصل A وB بالحافة AB، ونصل كلًا منهما بكل اسم من C D E F G: AC AD AE AF AG وBC BD BE BF BG. لا توجد حواف بين C وD وE وF وG.

ثم نضيف قطعة كاملة على A H I J بحواف AH AI AJ HI HJ IJ. A هو الاسم نفسه في الجزأين؛ لم نضف نسخة ثانية منه. عدد الحواف1 ثم10 ثم6، أي17 حافة على عشرة رؤوس.

A يتصل بالأسماء التسعة الأخرى، فتبلغ درجته9. B له A والخمسة C إلى G، فدرجته6. كل رأس من C إلى G له A وB فقط، فدرجته2. H وI وJ درجتها3 داخل القطعة الكاملة.

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

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

أصغر قطع يعطي نسبة نصف

احذف A وكل حوافه التسع. تبقى الأسماء B C D E F G H I J، وتبقى BC BD BE BF BG وHI HJ IJ. العدد تسعة رؤوس وثماني حواف.

المكون الأول نجمة مركزها B وأوراقها C D E F G، وعدد أسمائه6. المكون الثاني مثلث HIJ وعدد أسمائه3. لا يوجد اتصال بين النجمة والمثلث بعد خروج A، فعدد المكونات c=2.

المحذوف رأس واحد، لذلك s/c=1/2. نجح قطع من رأس واحد، والأصل المتصل لا ينفصل بحذف صفر رؤوس؛ فحجم أصغر قطع1. لا تعني القيمة1 أن كل قطع من رأس واحد ينجح.

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

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

حذف رأسين يخلق ستة مكونات

احذف A وB مع جميع الحواف التي تمسهما. تبقى C D E F G H I J، والحواف HI وHJ وIJ فقط. لدينا ثمانية رؤوس وثلاث حواف، لا ستة رؤوس أو ست حواف.

كل اسم من C D E F G معزول لأن جيرانيه الوحيدين A وB قد حُذفا. نعد هذه الأسماء خمسة مكونات، وليست مكونًا واحدًا لمجرد أن لها الدرجة نفسها. المثلث HIJ مكون سادس، مهما كان عدد رؤوسه الثلاثة.

أصبح s=2 وc=6، فالنسبة2/6=1/3. نقارنها مع1/2 بالضرب التبادلي:2×2=4 أقل من1×6=6. يمكن إبقاء الكسر2/6 لإظهار أصل البسط والمقام، ثم اختصاره إلى1/3.

هذا القطع أكبر من القطع A حجمًا، لكنه أفضل لتصغير النسبة. المقارنة تكفي لرفض1/2 كقيمة المتانة، لكنها لا تكفي وحدها لإعلان أن1/3 هو الأصغر بين جميع القطع؛ نثبت ذلك في القسم التالي.

المقام هو عدد المكونات كله، لا عدد المكونات الجديدة الزائدة على المكون الأصلي. استعمال c−1 هنا سيعطي2/5، وهو مقياس آخر لم نعرفه. كذلك لا نقسم على الثمانية، فهي عدد الرؤوس الباقية لا عدد المكونات.

زيادة المحذوف لا تضمن تحسين النسبة في كل مرة. حذف A وC يترك نجمة بأربع أوراق ومثلث HIJ، أي مكونين ونسبة2/2=1؛ الجدول يقارن هذا التحكم بحذفي A وAB.

ثلاث حالات تمنع نسبة أقل من الثلث

لتكن S أي مجموعة أسماء نحذفها. إذا بقي A، فإنه متصل بجميع الأسماء الأخرى الباقية. الناتج متصل، أو رأس واحد إن حُذف الجميع غيره؛ لا يدخل أي منهما شرط c>1. إذن كل قطع نحتاج مقارنته يحذف A.

إذا حُذف A وبقي B، فالأسماء الباقية من B C D E F G تقع في مكون واحد حول B. والأسماء الباقية من H I J، إن بقي منها شيء، تقع في مكون واحد آخر لأنها كانت مثلثًا كاملًا.

لهذا c≤2 في هذه الحالة. ولأن A محذوف، فإن s≥1. أي قطع مؤهل فيها يعطي s/c≥1/2؛ حذف أسماء أخرى من النجمة أو المثلث لا يخلق مكونات إضافية داخل هذين الجزأين.

تبقى حالة حذف A وB معًا. الأسماء الباقية من C إلى G لا تتصل ببعضها، فتساهم بخمسة مكونات على الأكثر. وما بقي من H I J يساهم بمكون واحد على الأكثر. إذن c≤6، بينما s≥2، فتكون s/c≥2/6=1/3.

الحالات غطت كل مجموعة S: A باقٍ، أو A محذوف وB باقٍ، أو كلاهما محذوف. في القطع المؤهلة لا تقل النسبة عن1/3، وحذف AB يحققها؛ لذلك المتانة t=1/3. الحصر العددي يراجع هذه الحجة ولا يحل محل تغطية الحالات.

ولتحقيق المساواة في الحالة الأخيرة نحتاج s=2 وc=6. لا يبقى حذف إضافي، فيكون S=AB، وتبقى المستقلات الخمس والمثلث. في هذا المثال القطع الذي يحقق أصغر نسبة وحيد أيضًا، لكن وحدانيته ليست شرطًا عامًا في تعريف المتانة.

راجع المكونات والكسور ضمن النطاق المعلن

راجعنا جميع2^10=1024 مجموعة حذف في المثال. حسبنا المكونات باتباع الجيران، وبطريقة مستقلة تجمع أطراف الحواف؛ تطابقت مجموعات الأسماء، لا عددها فقط. احتفظنا بكل رأس باقٍ معزول، واستبعدنا النتائج التي لها صفر أو مكون واحد من مقارنة النسبة.

في كل قطع مؤهل حسبنا s/c ككسر دقيق، وقارنّا الكسور دون تقريب عشري. وجد الحساب القطع A وحده عند أصغر حجم، والقطع AB وحده عند أصغر نسبة. القيم1/2 و1/3 لا تعتمد على دقة طباعة0.5 أو0.333.

على خمسة أسماء توجد1024 قائمة حواف، منها728 متصلة. استبعدنا الرسم الكامل الوحيد من هذه المجموعة، فبقي727 مدخلًا متصلًا غير كامل. لكل واحد راجعنا32 مجموعة حذف، أي727×32=23264؛ ليست كل مجموعة قطعًا مؤهلًا.

راجعنا ضوابط أيضًا: النجمة الرباعية متانتها1/3، والمسار الرباعي1/2، والدورة الرباعية1، وقطعتا K4 المشتركتان في رأس متانتهما1/2، والمكعب1. الأعداد تخص قوائم هذه المدخلات، ولا تستنتج المتانة من تساوي درجة أو اتصال الرؤوس فقط.

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

للمراجعة، اكتب الأصل ثم S، وأخرج الأسماء المحذوفة وحوافها، وعد المكونات بالأسماء. تحقق من c>1 قبل تكوين النسبة، وقارن جميع القطع الممكنة أو قدم حجة تغطيها. لا تختصر البحث إلى أصغر عدد محذوف، ولا تغيّر المقام إلى عدد الرؤوس الباقية.