تقسيم الحواف إلى غابات: لماذا لا يكفي حساب الرسم كله؟

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

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

• العدد التشجري هو أقل عدد من غابات منفصلة الحواف يغطي اتحادها الرسم. [1] كل حافة تتبع مجموعة واحدة، وقد يشترك أكثر من مجموعة في الرأس نفسه.
• رسمنا قلب كامل A B C D E، مع الحواف الطرفية AF وBG وCH وDI وEJ. له 10 رؤوس و15 حافة؛ القيد الكلي 15≤9k يستلزم k≥2، لكنه لا يثبت كفاية غابتين.
• داخل القلب، يلزم 10≤4k؛ عند k=2 نحصل على 10≤8 المستحيلة. لذلك يلزم ثلاث غابات على الأقل مهما أضفنا رؤوسًا طرفية حول القلب.
• الغابة الأولى هي طريق A B C D E مع الحواف الطرفية الخمس، فتضم 9 حواف. الثانية طريق A C E B D بأربع، والثالثة AD وAE بحافتين؛ لا دورة في أي منها، واتحادها كل الحواف.
• رسم آخر بعشرة رؤوس و15 حافة يحتاج غابتين فقط: طريق A B C D E F G H I J، مع المجموعة AC وAD وAE وAF وAG وAH. اختلاف اتصال الحواف يغير الحد الأدنى رغم تساوي العددين.
• نقسم الحواف لا الرؤوس، ونسمح برؤوس معزولة. التقاطعات ليست رؤوسًا؛ راجعنا 1024 مجموعة رؤوس و32768 مجموعة حواف لكل رسم. افحص غياب الدورات والتغطية مرة واحدة؛ إثبات الحد الأدنى يحتاج استبعادًا وبناءً صالحًا.

الغابة مجموعة بلا دورة، وليست بالضرورة متصلة

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

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

نثبت الأسماء A B C D E F G H I J، ونقسم الحواف الموجودة فقط. لا نضيف اتصالًا بين رأسين لتسهيل التقسيم. إذا دخلت AB في المجموعة الأولى، فلا نكررها في الثانية؛ أما A نفسه فيمكن أن يظهر في المجموعات الثلاث.

هذه مسألة غياب الدورات داخل كل مجموعة، وليست مسألة تلوين الرؤوس أو منع الحواف المتجاورة من مشاركة اللون. مجموعتان مثل AD وAE تلتقيان عند A وتظلان غابة صالحة؛ اللقاء عند رأس لا يصنع دورة بمفرده.

الحساب على الرسم كله يعطي حدًا أدنى فقط

الغابة على n رؤوس وc مكونات متصلة لها n−c حافة. [2] في مثال العشرة، الحد الأقصى 9 عند الاتصال؛ إذا فصلناها إلى مكونين، فالعدد 8، وتدخل الرؤوس المعزولة في عد المكونات.

الرؤوس الخمسة A B C D E تتصل كل اثنين منها. حواف القلب هي AB وAC وAD وAE وBC وBD وBE وCD وCE وDE؛ عددها 10. أضف AF وBG وCH وDI وEJ، فتأتي خمسة رؤوس جديدة وخمس حواف فقط.

الرسم الكامل متصل وله V=10 وE=15. إذا قسمناه إلى k غابات، فكل غابة تحمل 9 حواف على الأكثر، ومن ثم 15≤9k. قسمة 15 على 9 تعطي 5/3، وأصغر عدد صحيح لا يقل عنها هو 2.

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

قيد القلب يبقى حتى لو كثرت الرؤوس الطرفية

خذ من أي غابة محتملة الحواف التي تصل بين A B C D E فقط. المجموعة الناتجة تظل بلا دورة: حذف حواف أو رؤوس لا ينشئ دورة لم تكن موجودة. يمكن إبقاء الأسماء الخمسة كلها في هذا القيد، بما فيها رأس معزول إن ظهر.

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

إذن 10≤4k شرط لازم هنا، وأصغر عدد صحيح يحققه هو 3. لا يخفي الحساب الكلي هذا القيد الصغير أو يلغيه؛ يجب أن ينجح أي تقسيم في كل جزء من الحواف التي نحاول تغطيتها.

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

ثلاث قوائم حواف تثبت أن الحد ممكن

اجعل F1 تضم AB وBC وCD وDE مع AF وBG وCH وDI وEJ. الأربع الأولى طريق A B C D E، والخمس الباقية توصل رأسًا طرفيًا واحدًا في كل مرة. المجموعة متصلة بلا دورة على الرؤوس العشرة، وعدد حوافها 9.

اجعل F2 تضم AC وCE وBE وBD. هذه الحواف طريق A C E B D، بعد قراءة BE من E إلى B؛ الحافة غير موجهة. عددها 4، والرؤوس F وG وH وI وJ معزولة في هذه الغابة ولا تستبعد صلاحيتها.

اجعل F3 تضم AD وAE فقط. هاتان الحافتان تصلان D بA ثم E، دون إغلاق دورة؛ الرؤوس السبعة الأخرى معزولة. عدد الحواف 2، ولا مشكلة في أن تكون هذه المجموعة أصغر من الأخريين.

راجع الاتحاد: من القلب أخذت F1 أربع حواف، وF2 أربعًا أخرى، وF3 الباقيتين؛ ثم دخلت الحواف الطرفية الخمس في F1. لا تكرار ولا حافة منسية، والمجموع 9+4+2=15. التقسيم الصالح يثبت أن ثلاثًا تكفي، ومع استبعاد اثنتين يصبح الحد الأدنى 3.

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

الرؤوس والحواف نفسها عددًا، لكن غابتين تكفيان

للمقارنة، خذ طريقًا على الأسماء العشرة بالترتيب A B C D E F G H I J. حوافه AB وBC وCD وDE وEF وFG وGH وHI وIJ؛ عددها 9، ولا يعود الطريق إلى بداية ليغلق دورة.

أضف الحواف AC وAD وAE وAF وAG وAH. هذه الست نجمة مركزها A، ولا تتكرر فيها حافة من الطريق السابق. صار الرسم الجديد بعشرة رؤوس وخمس عشرة حافة أيضًا، لكنه لا يملك قائمة اتصال رسم القلب والأطراف.

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

مثلًا، AB وBC من الطريق مع AC من النجمة تشكل مثلث ABC في الاتحاد. لا يفسد ذلك التقسيم؛ المطلوب ألا تكون الدورة داخل غابة واحدة. لهذا لا يعني نجاح التقسيم أن الرسم الأصلي نفسه غابة أو أن كل مجموعتين من الحواف تصلحان تلقائيًا.

ابحث عن قيد صغير، ثم تحقق من التقسيم كاملًا

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

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

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

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