نواة الرسم البياني: هل تكفي الدرجة قبل الحذف؟

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

لا؛ نعيد حساب الدرجة داخل الرؤوس الباقية بعد كل حذف. في المسار A-B-C-D، حذف A وD يترك B وC بدرجة1 لكل منهما؛ يُحذفان أيضًا، فتكون نواة الدرجة2 فارغة. بقاء الرأس وفق درجته الأصلية لا يكفي ليحقق الحد داخل الناتج.

• نواة الدرجة k رسم جزئي أكبر لا تقل فيه درجة أي رأس عن k. [1] سنحافظ على جميع الحواف الأصلية بين الرؤوس التي نبقيها، ونحسب الدرجة داخل هذه المجموعة، لا داخل الرسم قبل الحذف.
• في المسار AB BC CD، الدرجات الأصلية (1,2,2,1). المرشحان B وC يتصلان ببعضهما فقط بعد حذف الطرفين، فتكون درجتاهما1؛ الجولة التالية تحذفهما، والناتج فارغ عند k=2.
• في الدورة AB BC CD AD، درجة كل رأس2 داخل الرسم نفسه، فلا يبدأ الحذف عند k=2؛ تبقى الرؤوس الأربعة. يكفي شرط الدرجة، ولا نطلب اتصال كل زوج من الرؤوس مباشرة.
• أي مجموعة صالحة للحد لا تفقد رأسًا في أي جولة، لأن جيرانه داخلها ما زالوا موجودين. عند توقف الحذف تكون البقية صالحة وتحتوي كل مجموعة صالحة؛ لذلك هي الأكبر، ولا يعتمد الناتج على ترتيب حذف المسموح حذفهم.
• في نجمة بستة رؤوس، درجة A الأصلية5، لكن نواتها عند k=2 فارغة. في مثلث ABC مع الأطراف AD AE AF، درجة A أيضًا5 وتبقى ABC؛ درجة A داخل النواة2، لا5.
• لا نشترط اتصال النواة: مثلثا ABC وDEF المنفصلان يبقيان جميع الرؤوس الستة عند k=2. الفارغة نتيجة مسموحة، وعند k=0 تبقى جميع الرؤوس والمعزولة أيضًا. زيادة k لا تضيف رؤوسًا خارج النواة السابقة.
• راجعنا1024 رسمًا مسمى على خمسة رؤوس عند k=0,1,2,3,4:5120 حالة نواة و163840 اختبار مجموعة رؤوس. اتفق الحذف بالجولات وحذف أصغر اسم أو أكبره مع اتحاد المجموعات الصالحة؛ ليست هذه كل الأحجام أو كل ترتيبات الحذف.

الدرجة داخل المجموعة التي نحتفظ بها

نواة الدرجة k رسم جزئي أكبر لا تقل فيه درجة أي رأس عن k. [1] سنحافظ على جميع الحواف الأصلية بين الرؤوس التي نبقيها، ونحسب الدرجة داخل هذه المجموعة، لا داخل الرسم قبل الحذف.

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

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

في هذا المقال k عدد صحيح غير سالب. المجموعة صالحة إذا كان لكل رأس فيها k جيران على الأقل من المجموعة نفسها. عند k=2 لا يكفي أن يتصل الرأس بجارين حُذفا؛ المطلوب جاران موجودان معه الآن.

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

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

مرشحان بدرجة2 يصبحان غير صالحين

نثبت A وB وC وD بالحواف AB وBC وCD فقط. A له جار واحد B، وD له جار واحد C؛ أما B فجاره A وC، وC فجاره B وD. قائمة الدرجات الأصلية في ترتيب الأسماء هي (1,2,2,1).

إذا اخترنا الأسماء التي درجتها الأصلية2 أو أكثر، أبقينا B وC. لكن الرسم داخل هذه المجموعة لا يحتوي سوى BC؛ A وD خارجها. لذلك B له جار واحد C، وC له جار واحد B. لم تحقق المجموعة الحد2 الذي اختيرت بسببه.

نبدأ الحذف الصحيح من الرسم كله. في الجولة الأولى نحذف A وD لأن درجتهما1 أقل من2، وتخرج الحافتان AB وCD معهما. نعيد حساب الدرجات في البقية B وC؛ نحصل على (1,1)، لا (2,2).

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

الصورة الرئيسية تعرض المسار ثم البقية ذات الحافة BC. الذهبية في اللوحة الأولى تميز من يحقق الحد قبل الحذف، ولا تعلن عضوية النواة النهائية. اللون الأحمر يميز الرؤوس التي لا تحقق الحد في الحالة المعروضة.

للمقارنة نغلق الدورة بإضافة AD إلى الحواف الثلاث. تصبح درجتا A وD أيضًا2، ويظل لكل رأس جاران داخل المجموعة الكاملة. لا يوجد اسم نحذفه عند k=2، فتبقى الدورة كلها. اختلاف حافة واحدة غير نتيجة الحذف.

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

لماذا لا نحذف رأسًا من مجموعة صالحة؟

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

لذلك لا يمكن أن تحذفه قاعدة «احذف درجة أقل من k» في تلك الجولة. وبعد إزالة الأسماء الأخرى تظل T كلها موجودة. نكرر الحجة: جيران الرأس داخل T لم يختفوا، فلا يمكن حذفه في الجولة التالية أيضًا.

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

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

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

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

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

الدرجة الأصلية5 قد تنتهي إلى صفر أو2

نثبت نجمة على A B C D E F، بالحواف AB وAC وAD وAE وAF. A درجته5، وكل اسم آخر درجته1. عند k=2 نحذف الأوراق B وC وD وE وF في الجولة الأولى، ولا يبقى لـA جار داخل البقية.

صارت درجة A الحالية0، فيُحذف في الجولة الثانية؛ النواة فارغة. لو احتفظنا به بسبب الدرجة الأصلية5، لكان الناتج رأسًا معزولًا يخالف الحد2. كثرة الجيران في البداية لا تضمن بقاءهم في مجموعة صالحة.

نقارن مثلثًا ABC بالحواف AB وAC وBC، ثم نضيف الأطراف AD وAE وAF. هنا درجة A أيضًا5، لكن درجتي B وC تساويان2، وD وE وF درجتها1. قائمة البداية هي (5,2,2,1,1,1).

نحذف D وE وF وحوافها الثلاث. تبقى AB وAC وBC؛ لكل اسم في ABC جاران من داخلها. يتوقف الحذف، فتكون النواة ABC. درجة A في هذه المجموعة2، رغم أن بطاقته الأصلية كانت5.

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

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

النواة لا يلزم أن تكون متصلة

نثبت ستة أسماء A B C D E F، وحواف المثلث ABC وحواف المثلث DEF فقط: AB وAC وBC وDE وDF وEF. لا توجد وصلة بين المجموعتين، ومع ذلك درجة كل رأس2 داخل الرسم كله.

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

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

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

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

الحساب الذي راجع النتيجة وحدوده

فحصنا جميع1024 قائمة حواف ممكنة على خمسة أسماء ثابتة. لكل واحدة حسبنا النواة عند k=0,1,2,3,4، فكان العدد1024×5=5120 حالة. تسمية الرؤوس جزء من المدخل؛ لا نزعم أن1024 عدد الأنواع المختلفة بعد حذف إعادة التسمية.

لكل حالة راجعنا32 مجموعة رؤوس ممكنة، بما فيها الفارغة والكاملة. حسبنا درجة كل رأس داخل مجموعته، ثم اتخذنا اتحاد المجموعات الصالحة. مجموع اختبارات المجموعات5120×32=163840؛ ليست163840 رسمًا جديدًا.

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

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

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

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