فرق الحواف: هل نجمع الدرجتين؟

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

لا؛ في الفرق المتناظر يجب استبعاد كل حافة مشتركة من حاصل جمع الدرجتين مرتين. للرأس A في مثالنا درجة 1 في كل رسم، لكن حافته AB مشتركة، فدرجته الجديدة 1+1−2=0. تبقى الرؤوس الأربعة، ويضم الناتج حافتين ومكونين؛ اتصال المدخلين لا يضمن اتصال الفرق.

• الفرق المتناظر بين مجموعتين يأخذ ما ينتمي إلى واحدة منهما فقط، ويستبعد المشترك؛ ويوافق عملية XOR المنطقية. [1] في فرق رسمين، تبقى الحواف الموجودة في أحدهما فقط، وتكون مجموعة الرؤوس نفسها في المدخلين. [2] نثبت هنا رسومًا بسيطة غير موجهة بلا حلقات أو أوزان، ونحفظ الأسماء والمعزولات.
• المدخل G له AB BC CD، والمدخل H له AB BD CD. المشترك AB وCD يختفي، وBC وBD موجودتان في طرف واحد فتظهران. لا تظهر AC أوAD لأنهما غائبتان عن الطرفين.
• عدد الحواف 3+3−2×2=2، لا 6 ولا عدد الاتحاد 4. ولرأس v، إذا كان c(v) عدد الحواف المشتركة التي تمسه، فدرجته dG(v)+dH(v)−2c(v). الدرجة الجديدة في ترتيب A B C D هي (0,2,1,1).
• كل مدخل مسار متصل، لكن الناتج يترك A معزولًا ويصل B بـC وD. لدينا المكون {A} والمكون {B,C,D}. لا نحذف A كي تبدو الصورة متصلة، ولا نجمع درجتين دون فحص المشترك.
• الفرق المتناظر ليس الفرق باتجاه واحد: G دون H يعطي BC فقط، وH دون G يعطي BD فقط؛ نأخذ كليهما. أما الاتحاد فيحتفظ بالمشترك مرة واحدة، والفرق المتناظر يستبعده كليًا.
• فرق رسم بنفسه بلا حواف، مع بقاء الرؤوس الأربعة معزولة. فرق G مع مدخل بلا حواف يعيد G؛ ومع الكامل K4 يقلب جميع الأزواج المسموحة فيعطي متمم G. الرسم الثاني ليس كاملًا في مثال المسارين.
• راجعنا جميع 4096 زوجًا مرتبًا على أربعة رؤوس، و16384 خانة درجة. من 1444 زوجًا بمدخلين متصلين أعطى 670 فرقًا غير متصل. هذه نتائج حصر محدود، لا احتمالًا لشبكة واقعية أو اختبار أداء.

حافة في طرف واحد، لا في الطرفين

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

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

نثبت أربعة رؤوس مسماة A B C D في كل رسم وفي الناتج. الحواف أزواج من اسمين مختلفين، بلا اتجاه أو وزن أو تكرار للزوج نفسه. AB وBA حافة واحدة في هذا النموذج، ولا تدخل AA ضمن الأزواج الممكنة.

لا ندمج اسمين ولا نعيد تسمية رأس من جهة وحدها. المقارنة تسأل عن الزوج نفسه في الرسمين: هل AB موجودة هنا وهناك؟ إذا غيرنا أسماء المدخل الثاني وحده فقد غيرنا المقارنة، حتى لو بقي شكل المسار مألوفًا.

نستعمل الرمز G للمدخل الأول وH للثاني، وX للناتج؛ هذه أسماء رسوم، وليست رؤوسًا إضافية. سنحسب من قوائم الحواف مباشرة. لا نشغل NetworkX هنا، ولا نختبر خصائص كائنات مكتبة أو نسخ صفات الحواف.

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

مساران بثلاث حواف ينتجان حافتين

اختر G بالحواف AB BC CD، فيعطي المسار A→B→C→D. واختر H بالحواف AB BD CD، فيعطي المسار A→B→D→C. كل مدخل متصل، وكل أسماء الرؤوس الأربعة موجودة فيه.

نراجع الأزواج الستة الممكنة: AB مشتركة فنستبعدها، وAC غائبة عن الاثنين فلا نضيفها، وAD غائبة كذلك. BC في G وحده فنحتفظ بها، وBD في H وحده فنحتفظ بها، وCD مشتركة فنستبعدها.

إذن قائمة X هي BC BD. لم نحتفظ بإحدى نسختي AB أوCD؛ التعريف يستبعد المشترك، لا يزيل تكراره فقط. وغياب AC عن أحد المدخلين لا يكفي لإضافتها؛ يجب وجودها في الآخر.

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

في اتحاد الحواف نجد AB BC BD CD، أي أربع حواف. وفي التقاطع نجد AB CD، أي حافتين مختلفتين عن حافتي X. تساوي عدد الفرق وعدد التقاطع هنا لا يعني تطابق الرسمين الناتجين.

وإذا طلبنا G دون H، بقيت BC وحدها؛ وإذا طلبنا H دون G، بقيت BD وحدها. الفرق المتناظر يجمع القائمتين غير المشتركتين، لذلك لا يخص اتجاهًا واحدًا من المدخل إلى الآخر.

المشترك يدخل الجمع مرتين ثم يغيب

لنسم عدد حواف G بالرمز mG، وعدد حواف H بالرمز mH، وعدد الحواف المشتركة t. جمع mG+mH يحسب كل غير مشترك مرة، وكل مشترك مرتين. في الفرق لا نريد أي ظهور للمشترك، فنطرح 2t.

فيكون mX=mG+mH−2t. في مثالنا mG=3 وmH=3 وt=2، فنحصل على 3+3−2×2=2. أما عدد الاتحاد فيطرح المشترك مرة فقط، فيعطي 3+3−2=4. اختلاف العملية يغير معنى الطرح.

والحجة نفسها عند رأس ثابت v. لتكن c(v) عدد الحواف المشتركة المتصلة به. نجمع درجتيه في G وH، ثم نستبعد ظهور كل حافة مشتركة عنده مرتين: dX(v)=dG(v)+dH(v)−2c(v).

درجات G في ترتيب A B C D هي (1,2,2,1)، ودرجات H هي (1,2,1,2). الحافتان المشتركتان AB وCD تمسان كل رأس مرة، فالقائمة c هي (1,1,1,1).

لذلك درجة A هي 1+1−2=0؛ ودرجة B هي 2+2−2=2؛ ودرجة كل من C وD هي 2+1−2=1 مع مراعاة ترتيب المدخلين. الدرجات النهائية (0,2,1,1)، ومجموعها 4، أي ضعفا الحافتين.

لا نطرح عدد كل الحواف المشتركة من درجة كل رأس. عند A تمس AB وحدها، فلا نستعمل t=2 بدل c(A)=1. المعادلة الأولى تعد كل الرسم، والثانية تعد الحواف التي تمس الاسم المعين.

يبقى الرأس، وقد يصير معزولًا

في X، يصل B بـC عبر BC، ويصل B بـD عبر BD. إذن B وC وD في مكون واحد، حتى مع غياب CD. أما A فلا تمسه أي حافة؛ يكون وحده مكونًا آخر.

يمكن مشاهدة سبب العزلة دون بحث طويل: حافة A الوحيدة في كل مدخل هي AB، وقد استُبعدت لأنها مشتركة. لم تختفِ هوية A، بل اختفت صلته المباشرة. صفر الدرجة ليس أمرًا بحذف الرأس.

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

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

ولا نستنتج أن الفرق يفصل كل زوج من رسمين متصلين. أبق G مسار AB BC CD، وخذ مدخلًا ثانيًا بالحواف AC BC BD، وهو المسار A→C→B→D. المشتركة BC فقط؛ يبقى AB AC BD CD، فتظهر الدورة A→B→D→C→A على الأسماء الأربعة. هنا المدخلان والفرق متصلة.

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

نفس المدخل والخالي والكامل

إذا كان المدخلان G نفسه، كانت كل حافة مشتركة، فيكون الفرق بلا حواف. على أسماء A B C D نحصل على أربعة معزولات، لا مجموعة رؤوس فارغة. كل درجة تصبح d+d−2d=0.

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

أما الكامل K4 فيضم كل الأزواج الستة بين الرؤوس الأربعة. مع هذا المدخل الثاني، تستبعد كل حافة موجودة في G، وتظهر كل حافة غائبة عنه؛ فيعطي الفرق متمم G ضمن الأزواج المسموحة بلا حلقات.

لمسار G ذي AB BC CD، تكون قائمة المتمم AC AD BD. هذه ثلاث حواف، بينما فرق G مع H المسار الآخر كان BC BD بحافتين. لذلك لا نستبدل الرسم الثاني بالكامل ضمنيًا ولا نسمي كل فرق متممًا.

تبديل G وH لا يغير الفرق المتناظر، لأن معيار طرف واحد فقط لا يفضل جهة. وباستعمال H مرة أخرى بعد الفرق، نعيد G: الحافة الموجودة في H يتبدل وجودها مرتين، والحافة الغائبة عنه لا تتبدل.

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

حصر الأزواج لا يستبدل حجة العضوية

أربعة رؤوس مختلفة تتيح ست حواف ممكنة بلا حلقات. لكل حافة وجود أو غياب، فيكون 2⁶=64 رسمًا مسمى. وللمدخلين المستقلين في الفحص 64×64=4096 زوجًا مرتبًا؛ لا نحذف الأزواج بعد إعادة أسماء أو تشابه أشكال.

في كل زوج حسبنا الفرق من مجموعتي الحواف، وقارناه بعملية على بت لكل زوج مسموح. راجعنا عدد الحواف ومعادلة الدرجة لكل رأس، فأصبح عدد خانات الدرجة 4096×4=16384.

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

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

راجعنا كذلك تبديل المدخلين والعودة إلى G بإجراء الفرق مع H ثانية. لم نستعمل صورة أو مثال مجموعات من المرجع، ولم نشغل symmetric_difference في NetworkX. الحصر يراجع نموذجنا البسيط فقط، ولا يغطي حلقات أو أوزانًا أو حواف متوازية.

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