انكماش حافة: هل ينقص عدد الحواف بواحدة فقط؟

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

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

• انكماش حافة يدمج طرفيها في رأس واحد، وتصبح الحواف الأخرى المتصلة بأي منهما متصلة بالرأس المدمج. [1] نختار حافة موجودة بالفعل، ونكتب X لاسم الرأس الذي يحل محل طرفيها في أمثلتنا. نختار ناتجًا بسيطًا بلا حلقات وبلا حواف متوازية.
• مثلث AB AC BC بعد انكماش AB يعطي XC فقط:3 حواف تصير1. الجار المشترك C يسبب دمج نسختين في حافة واحدة، إلى جانب حذف AB.
• الدورة AB BC CD AD بعد انكماش AB تعطي XC XD CD:4 حواف تصير3، لغياب جار مشترك. K4 بعد انكماش AB يعطي المثلث نفسه، لكن6 حواف تصير3 لوجود C وD مشتركين.
• إذا كان العدد الأصلي m والجيران المشتركون c، فالعدد الجديد m−1−c، ودرجة X هي deg(u)+deg(v)−2−c. الجار المشترك يفقد وصلة واحدة، وغير المشترك يحفظ درجته.
• عدد المكونات محفوظ عند انكماش حافة موجودة. لكن دورة المثلث تزول والدورة الرباعية تقصر إلى مثلث؛ حفظ الاتصال لا يعني حفظ كل دورة.
• المسار AB BC CD بعد انكماش BC يصبح A-X-D متصلًا، بينما حذف BC وحدها يفصله. والحافة AB مع C معزولًا تعطي X وC معزولين، فلا نحذف الرأس المدمج لمجرد خلوه من الجيران.
• راجعنا5120 انكماشًا لحواف موجودة عبر1024 رسمًا مسمى على خمسة رؤوس، و20480 فحص درجة. الأعداد للنموذج البسيط المحدد، وليست حكمًا على الحلقات أو الرسوم المتعددة أو كل الأحجام.

نثبت نوع الناتج قبل دمج الطرفين

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

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

توضح وثائق NetworkX أن اتصال الطرفين بجار ثالث يدمج الحافتين في حالة الرسم البسيط، بينما يضيف الرسم المتعدد حافة أخرى، وأن للحلقات سياسة اختيار مستقلة. [2] لم نشغل هذه الأدوات؛ نحسب رسمنا البسيط من قوائم الأسماء والحواف.

إذا دمجنا A وB، تختفي هويتهما المنفصلتان وتحل X محلهما. تبقى الأسماء الأخرى كما هي، فينقص عدد الرؤوس بواحد. لا نحذف جميع جيران A أوB، ولا نزيل كل الحواف التي كانت عندهما؛ نعيد تحديد أطرافها وفق الدمج.

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

مثلث بثلاث حواف يصبح حافة واحدة

نثبت A وB وC بالحواف AB وAC وBC. نختار AB للانكماش، ونسمي نتيجة دمج A وB بالرأس X. تصبح قائمة الرؤوس X وC، لا A وB وC مع رأس إضافي.

الحافة AB كانت بين الرأسين اللذين صارا X نفسه، فنزيلها في نموذجنا بلا حلقات. أما AC فتصبح XC، وBC تصبح XC أيضًا. كلاهما يصل الزوج نفسه؛ الناتج البسيط يحتوي XC مرة واحدة فقط.

إذن انخفض عدد الحواف من3 إلى1، وليس إلى2. C جار مشترك لـA وB في الأصل، وقد تسبب في تكرار زوج واحد بعد الدمج. يمكن تتبع الخسارتين: الحافة المنكمشة أولًا، ثم إحدى نسختي الوصلة إلى C.

درجة كل رأس في المثلث كانت2. بعد الانكماش درجة X هي1، ودرجة C هي1. لم نجمع2 و2 لنحصل على4؛ الحافة بين الطرفين والتكرار إلى الجار المشترك يجب أن يؤخذا في الحساب.

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

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

الدورة الرباعية تكشف متى تكفي خسارة واحدة

نختار A B C D بالحواف AB وBC وCD وAD، ثم ننكمش AB إلى X. لا يوجد رأس ثالث مجاور لـA وB معًا: جيران A خارج B هم D، وجيران B خارج A هم C.

نزيل AB، ونعيد BC إلى XC وAD إلى XD، ونبقي CD كما هي. أزواج الناتج مختلفة، فالقائمة XC وXD وCD بثلاث حواف. انخفض العدد من4 إلى3 لأن عدد الجيران المشتركين صفر.

الناتج مثلث على X وC وD: الطريق X→C→D→X مغلق. إذن انكماش الحافة قد يبقي دورة، كما في الرباعية، وقد يزيلها، كما في مثلث القسم السابق. لا نستنتج الحكم من إنقاص عدد الرؤوس وحده.

ولضبط آخر، خذ K4 بحوافه AB وAC وAD وBC وBD وCD، ثم انكمش AB. الجاران المشتركان C وD يعطيان زوجين مكررين: AC وBC يصبحان XC، وAD وBD يصبحان XD، وتبقى CD.

صار K4 ذو ست الحواف مثلثًا بثلاث. فقدنا AB وتكرارًا لكل من C وD؛ هذه ثلاث خسارات لا واحدة. ومع ذلك بقيت الدورة X→C→D→X، فلا يكفي وجود جار مشترك لضمان إزالة جميع الدورات.

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

احسب اتحاد الجيران، ثم عدد الأزواج

لنرمز إلى الجارين اللذين ندمجهما بـu وv، وإلى عدد الحواف الأصلي بـm. ولتكن c عدد الأسماء التي تتصل بكل منهما في الأصل. لا نعد u أوv جارًا مشتركًا؛ الرسم الأصلي بلا حلقات.

نفقد الحافة uv نفسها. ولكل جار مشترك w، تصبح uw وvw حافتين بين X وw، ونحتفظ بواحدة فقط. الجيران المختلفون يعطون أزواجًا مختلفة، والحواف التي لا تمس الطرفين تبقى دون تغيير. لذلك عدد الحواف الجديد m−1−c.

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

درجة X هي عدد أعضاء اتحاد جيران u خارج v وجيران v خارج u. نجمع درجتي الطرفين، ثم نستبعد ظهور الحافة uv عندهما مرتين، ثم نستبعد تكرار كل جار مشترك مرة واحدة. نحصل على deg(X)=deg(u)+deg(v)−2−c.

في المثلث: m=3 وc=1، فيكون العدد3−1−1=1، ودرجة X هي2+2−2−1=1. وفي الرباعية: m=4 وc=0، فيكون العدد3 ودرجة X تساوي2. وفي K4: m=6 وc=2، فيكون العدد3 ودرجة X هي2.

الجار المشترك نفسه يفقد وصلة واحدة، لأن جارَيه القديمين صارا رأسًا واحدًا. أما رأس لم يكن مجاورًا لكليهما، فدرجته تبقى كما هي. عد الجيران المشتركين من الأصل قبل الدمج، ولا تبحث عن A وB بعد خروجهما من قائمة الأسماء.

المكونات تبقى، لكن الدورة قد تقصر أو تزول

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

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

نأخذ المسار AB وBC وCD، وننكمش BC إلى X. يبقى A وD، وتصبح الحافتان AX وXD. الناتج مسار من ثلاثة رؤوس وحافتين، متصل بلا دورة. لا يظهر جار مشترك بين B وC في الأصل.

في رسم يتكون من AB وحدها ورأس C معزول، ينتج رأسان معزولان X وC بعد إزالة AB ودمج طرفيها. لا نترك A وB في القائمة، ولا نحذف X لأنه صار بلا جيران. عدد المكونات اثنان قبل العملية وبعدها.

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

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

ما فحصناه وما لا تعنيه المعادلة

راجعنا جميع1024 قائمة حواف على خمسة رؤوس مسماة، ولكل مدخل اخترنا كل حافة موجودة على حدة للانكماش. كان مجموع حالات اختيار الحافة5120؛ المدخل الخالي من الحواف لا يتيح اختيارًا.

بنينا الناتج بطريقتين: إعادة تسمية أطراف كل حافة ثم تجاهل الحلقة وتوحيد الأزواج، وبناء اتحاد الجيران حول X مع إبقاء الحواف التي لا تمس الطرفين. تطابقت القائمتان في كل حالة، وراجعنا المعادلة m−1−c وعدد الرؤوس والمكونات.

في كل ناتج أربعة رؤوس، فكان عدد فحوص الدرجات5120×4=20480. راجعنا درجة X ودرجة كل جار مشترك أو غير مشترك. وشملت الأمثلة المعلنة المثلث والرباعية وK4 والمسار والحافة مع المعزول.

هذه حالات مسماة محدودة الحجم، لا كل الأحجام أو أنواع الرسوم. لم نشغل NetworkX أو Wolfram ولم نقس السرعة. المعادلة تشرحها قسمة الحواف واتحاد الجيران في سياسة الناتج المعلنة؛ الحساب يراجع الأمثلة ولا يستبدل الحجة.

لا نطبق m−1−c على رسم يحتفظ بالحواف المتوازية أو الحلقة الناتجة عن uv، ولا على دمج رأسين غير متجاورين أو رسم موجه أو موزون دون تحديد جديد. هنا نتتبع الأزواج غير الموجهة المختلفة فقط، لا عدد سجلات نقل أو أوزان مجمعة.

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