تقسيم كل حافة: هل يصبح الرسم شجرة؟

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

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

• تقسيم حافة يستبدلها بحافتين عبر رأس جديد. [1] والشجرة رسم بسيط غير موجه متصل بلا دورات. [2] نقسم كل حافة أصلية مرة واحدة في الأمثلة الأساسية، مع وسيط مستقل لكل حافة.
• K4 بأربعة رؤوس وست حواف يصبح بعشرة واثنتي عشرة. الدورة A-U-B-X-C-V-A باقية بطول6؛ درجات القدامى3 ودرجات الوسطاء2، فلا يكون الناتج شجرة.
• توسيع دورة قديمة عبر الوسطاء يحفظ دورة، وضغط دورة جديدة بإزالة أسماء الوسطاء يعيد دورة في الأصل. المكونات باقية أيضًا؛ لذلك الشجرية قبل التقسيم وبعده متكافئة في النموذج المعلن.
• بعد تقسيم كل حافة مرة واحدة، كل حافة بين قديم وجديد، فيصح اللونان. لكن K4 المقسم والمثلث المقسم ما زالا دوريَّين؛ قبول لونين ليس غياب الدورات. التقسيم الجزئي قد يبقي مثلثًا لا يقبل اللونين.
• المسار AB BC CD يصير شجرة بسبعة رؤوس وست حواف. المثلث مع D معزولًا يعطي العددين نفسيهما بعد التقسيم، لكنه دورة ومكون معزول؛ الاتصال ضروري مع عد الحواف.
• للجولة الكاملة: عدد الرؤوس n+m والحواف2m، ودرجة كل جديد2. المسافة الجديدة بين اسمين قديمين متصلين هي2d؛ لا ننقل الصيغة إلى التقسيم الجزئي أو إلى أسماء جديدة.
• راجعنا1024 رسمًا مسمى على خمسة رؤوس و25600 خانة مسافة قديمة، مع فحص المكونات والدورات والدرجات والعد والتلوين. لا يشمل ذلك كل الأحجام أو الأوزان والاتجاهات.

نحذف الحافة القديمة ونصل طرفيها بالرأس الجديد

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

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

في أبسط خطوة، نبدل AB إلى AU وUB، حيث U اسم جديد. لا تبقى AB إلى جانبهما. إبقاؤها كان سيعطي مثلث A-U-B-A، وهو اتصال مختلف عن استبدال الحافة الذي نختبره.

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

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

ست حواف تصير اثنتي عشرة، لكن الدورة تبقى

نبدأ بـA وB وC وD، ونصل كل زوج مختلف: AB وAC وAD وBC وBD وCD. هذا K4 بست حواف، وكل رأس درجته3. يحتوي مثلًا الدورة A→B→C→A، فلا يكون شجرة.

نعطي الحواف الست أسماء الرؤوس الجديدة U وV وW وX وY وZ بالترتيب. AB تستبدل إلى AU وUB، وAC إلى AV وVC، وAD إلى AW وWD، وBC إلى BX وXC، وBD إلى BY وYD، وCD إلى CZ وZD.

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

الدورة A→B→C→A أصبحت A→U→B→X→C→V→A. خطواتها الست كلها موجودة، وأسماؤها الداخلية مختلفة. لذلك ما زال الناتج يحوي دورة، رغم أن مثلث الأسماء القديمة لم يعد مثلثًا من ثلاث حواف.

الرسم متصل أيضًا: نصل أي رأسين قديمين باتباع الاتصال السابق عبر الوسطاء، وكل وسيط متصل بطرفيه. الشجرة على عشرة رؤوس لها تسع حواف. [2] هنا لدينا اثنتا عشرة، والدورة المعروضة سبب مباشر يمنع الشجرية دون الاكتفاء بالعدد.

درجة A ما زالت3، لكن جيرانه صاروا U وV وW بدل B وC وD. وبالمثل تبقى درجات B وC وD ثلاثًا، بينما درجة كل من U وV وW وX وY وZ هي2. تغيرت أسماء الجيران، ولم ترتفع درجة الرأس القديم لمجرد زيادة عدد الحواف الكلي.

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

إطالة الدورة لا تلغي إغلاقها

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

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

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

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

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

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

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

لونان يكفيان، ومع ذلك قد توجد دورة

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

في K4 المقسم، الزرقاء A وB وC وD، والذهبية U وV وW وX وY وZ. وجود الحواف يمنع لونًا واحدًا، لكن الدورة السداسية المعروضة تبقى. إذن قبول لونين لا يثبت أن الرسم شجرة؛ الدورات الزوجية لا تخرق هذا التلوين.

للضبط نأخذ المسار AB وBC وCD، ونسمي وسطاءها U وV وW. يصير الطريق A→U→B→V→C→W→D، بسبعة رؤوس وست حواف. الاتصال باقٍ ولا دورة؛ هذا شجرة لأن المسار الأصلي كان شجرة، لا لأننا منحناه لونين.

ومثلث ABC بعد تقسيم حوافه كلها يصبح A→U→B→X→C→V→A، بستة رؤوس وست حواف. هو متصل ويقبل اللونين القديم والجديد، لكنه ليس شجرة بسبب الدورة. الصورة الداخلية تقارن هذه الدورة بالمسار ذي السبعة.

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

ولا ننقل حكم القديم والجديد بلونين إلى كل تقسيم جزئي. تقسيم AB وحدها في K4 يترك مثلث A-C-D-A دون تغيير، فيمنع اللونين. وفي مثلث ABC تقسيم AB وحدها يعطي دورة A-U-B-C-A من4، فتقبل لونين لكنها تظل دورة.

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

المسافة بين القديمين تتضاعف في الجولة الكاملة

نعني بالمسافة هنا أقل عدد من حواف طريق، في رسم غير موزون. عند تقسيم كل حافة أصلية مرة واحدة، أي طريق قديم من d حواف يتحول إلى طريق جديد من2d حافة. توسيع أقصر طريق يثبت أن المسافة الجديدة بين طرفيه لا تزيد على2d.

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

إذا كان طول الطريق الجديد s، صار d≤s/2، ومن ثم2d≤s. مع البناء الأول تتساوى المسافة الجديدة و2d. هذه الصيغة للطرفين القديمين فقط، وفي تقسيم كل حافة مرة واحدة؛ لا نعطيها لطرف جديد لم يكن موجودًا في الأصل.

في K4 كانت مسافة A إلى B هي1، وصارت2 عبر U. وبين A وD صارت2 عبر W. وفي المسار كانت مسافة A إلى D هي3، وصارت6 عبر A→U→B→V→C→W→D. ليست هذه المسافات أطوال خطوط الصور.

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

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

ما اختبرناه وما بقي خارج النموذج

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

لكل مدخل قارنا25 خانة مسافة بين الرؤوس القديمة، فكان العدد1024×25=25600. شملت الخانات المتساوية الطرفين والمسارات غير الموجودة، ولم ندع أن جميع المدخلات متصلة. راجعنا مضاعفة المسافة المنتهية وبقاء غير المتصل غير متصل.

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

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

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

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