المكونات المتصلة بقوة: الوصول في اتجاه واحد لا يكفي

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

في الرسم الأصلي المكونان المتصلان بقوة هما A,B,C و D,E,F. تسمح الدورتان بالوصول والعودة داخل كل مجموعة. أما C→D فيتيح الانتقال من الأولى إلى الثانية، ولا يوجد طريق معاكس. عند إضافة F→A تصبح الرؤوس الستة في مكون واحد؛ العودة الجديدة تكمل الوصول في الاتجاهين بين المجموعتين.

• المكون المتصل بقوة مجموعة رؤوس يمكن الوصول بين كل رأسين مختلفين فيها في الاتجاهين، ولا يمكن إضافة رأس آخر مع بقاء هذا الشرط. تتوزع الرؤوس على مكونات لا تتداخل. [1]
• رسمنا موجه، وحوافه A→B و B→C و C→A و C→D و D→E و E→F و F→D فقط. يشكل A,B,C دورة، ويشكل D,E,F دورة أخرى؛ السهم الوحيد بينهما C→D.
• من A أو B أو C يمكن الوصول إلى الرؤوس الستة. من D أو E أو F يمكن الوصول إلى D,E,F فقط. الوصول في اتجاه واحد لا يكفي لدمج المجموعتين؛ لا يوجد طريق عودة إلى A,B,C.
• يمكن تمثيل كل مكون برأس واحد، وإبقاء الحواف بين المكونات المختلفة. هذا الرسم المختصر لا يحتوي دورة موجهة. [1] في مثالنا يصبح رأسيه A,B,C و D,E,F، وبينهما سهم واحد من الأول إلى الثاني.
• إضافة F→A وحدها تجعل هناك انتقالًا من المجموعة الثانية إلى الأولى، إلى جانب C→D. مع الدوران داخل كل مجموعة يصبح الوصول متبادلًا بين أي رأسين، فتندمج الرؤوس الستة في مكون واحد.
• إذا حذفنا C→D، بقي المكونان A,B,C و D,E,F، لكن اختفى الانتقال بينهما. وإذا أضفنا G معزولًا إلى الرسم الأصلي، صار مكونًا ثالثًا منفردًا؛ لا نشترط حلقة ذاتية ليكون رأس واحد مكونًا.

حدد الأسهم، ثم اختبر الوصول في الاتجاهين

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

نثبت ستة رؤوس A و B و C و D و E و F. الحواف الموجهة الوحيدة هي A→B و B→C و C→A و C→D و D→E و E→F و F→D. ليس لكل سهم سهم عكسي تلقائي؛ قائمة الحواف هي التي تسمح بالانتقال، لا قرب النقاط في الصورة.

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

ترسم الصورة الرئيسية دورة A→B→C→A بلون، ودورة D→E→F→D بلون آخر. السهم C→D يربطهما في اتجاه واحد. الألوان توضح التقسيم الذي سنبرره، ولا تغني عن فحص الأسهم والعودة.

اكتب ما يمكن الوصول إليه من كل رأس

من A نصل إلى B مباشرة وإلى C عبر B، ثم إلى D عبر C. بعد D نصل إلى E ثم F. ومن B أو C يمكن أولًا الدوران حتى A ثم متابعة هذه الطرق، لذا تستطيع كل نقطة في A,B,C بلوغ الرؤوس الستة.

أما D و E و F فتسمح دورتها بالانتقال بينها فقط. لا يخرج من أي منها سهم إلى A أو B أو C. مهما كررنا الدوران D→E→F→D، لا نكتسب حافة جديدة تتيح الخروج من تلك المجموعة. لهذا يقتصر الوصول منها على D,E,F.

الجدول يحصر الرؤوس المتاحة من كل بداية وفق الأسهم الأصلية، مع إدراج البداية نفسها بالاصطلاح المذكور. مثلًا A يصل إلى D بالطريق A→B→C→D، لكن D لا يصل إلى A. تشابه قوائم بعض البدايات هنا نتيجة للرسم، لا قاعدة نطبقها على أي شبكة.

لماذا نختار مجموعتين كاملتين لا أزواجًا صغيرة؟

داخل A,B,C يصل A إلى B مباشرة، ويعود B إلى A عبر C. وبالمثل يصل B إلى C مباشرة ويعود C إليه عبر A؛ ويصل C إلى A مباشرة ويعود A إليه عبر B. تحقق الدورة الوصول المتبادل لكل زوج من هذه الرؤوس الثلاثة.

داخل D,E,F يحدث الأمر نفسه: يسير كل رأس إلى الآخر على الدورة D→E→F→D. أما ضم أي رأس من هذه المجموعة إلى A,B,C، فيفشل لأن ذلك الرأس لا يصل إلى A أو B أو C. لا يمكن توسيع المجموعة الأولى، ولا الثانية، مع إبقاء الوصول المتبادل.

قد تحقق المجموعة A,B الوصول المتبادل، لكنها ليست مكونًا كاملًا هنا؛ يمكن إضافة C مع بقاء الشرط. وكذلك D,E يمكن توسيعها بإضافة F. شرط عدم إمكان التوسيع يمنع تقسيم الدورة إلى أجزاء أصغر وتسميتها مكونات متصلة بقوة.

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

اختصر كل مكون إلى رأس، واحتفظ بالانتقال بينهما

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

نختار الاسم X للمكون A,B,C، والاسم Y للمكون D,E,F. الحواف الست داخل الدورتين لا ترسم حلقات على X أو Y في هذا الاختصار. الحافة C→D وحدها تربط مكونين مختلفين، فتتحول إلى X→Y. لا نرسم Y→X، لأنه لا توجد حافة أصلية تبررها.

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

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

سهم عودة واحد يغير التقسيم، والحذف له أثر آخر

نضيف F→A فقط إلى الحواف الأصلية. يستطيع رأس في A,B,C الدوران حتى C، ثم عبور C→D والدوران في D,E,F إلى الوجهة المطلوبة. ويستطيع رأس في D,E,F الدوران حتى F، ثم عبور F→A والدوران في A,B,C. صار الاتجاهان ممكنين بين المجموعتين.

إذن كل رأسين من الستة يمكن الوصول بينهما ذهابًا وعودة، فتكوّن الستة مكونًا واحدًا. هذا حكم على الرسم المعدل؛ الرسم الأصلي الذي لم يتضمن F→A له مكونان. لا يجوز رسم سهم العودة لأغراض التوضيح ثم نسبة نتيجته إلى القائمة الأصلية.

في تعديل منفصل، نحذف C→D من الرسم الأصلي دون إضافة F→A. تبقى الدورتان كما هما، فيبقى المكونان A,B,C و D,E,F، لكن لا تستطيع المجموعة الأولى بلوغ الثانية. يختفي السهم X→Y من الرسم المختصر؛ ولا يفرض تغير قائمة الوصول تغير عدد المكونات.

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

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