مكون متصل بقوة

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة
رسم بياني بمناطق مظللة توضح المكونات المتصلة بقوة

في النظرية الرياضية للرسوم البيانية الموجهة ، يُقال إن الرسم البياني متصل بقوة إذا كان كل رأس فيه قابلاً للوصول من أي رأس آخر. تُشكل المكونات المتصلة بقوة في الرسم البياني الموجه تجزئةً إلى رسوم بيانية فرعية متصلة بقوة بدورها. من الممكن اختبار الاتصال القوي للرسم البياني، أو إيجاد مكوناته المتصلة بقوة، في زمن خطي (أي Θ( V  + E )). 

التعريفات

يُطلق على الرسم البياني الموجه اسم " متصل بقوة" إذا وُجد مسار في كل اتجاه بين كل زوج من رؤوسه. أي أن هناك مسارًا من الرأس الأول في الزوج إلى الثاني، ومسارًا آخر من الثاني إلى الأول. في الرسم البياني الموجه G الذي قد لا يكون متصلًا بقوة، يُقال إن زوج الرؤوس u و v متصلان بقوة إذا وُجد مسار في كل اتجاه بينهما.

العلاقة الثنائية للترابط القوي هي علاقة تكافؤ ، وتُسمى الرسوم البيانية الفرعية المُستحثة لفئات التكافؤ هذه بالمكونات المترابطة بقوة . وبالمثل، فإن المكون المترابط بقوة في الرسم البياني الموجه G هو رسم بياني فرعي مترابط بقوة، ويكون أقصى ما يمكن تحقيقه بهذه الخاصية: لا يمكن تضمين أي مجموعة من الحواف أو الرؤوس الإضافية من G في الرسم البياني الفرعي دون الإخلال بخاصية ترابطه القوي. تُشكل مجموعة المكونات المترابطة بقوة تجزئة لمجموعة رؤوس G. يُسمى المكون المترابط بقوة C تافهًا عندما يتكون من رأس واحد غير متصل بنفسه بحافة، وغير تافه في غير ذلك. [ 1 ]

الرسم البياني الأصفر الموجه غير الدوري هو تكثيف للرسم البياني الأزرق الموجه. ويتكون من خلال دمج كل مكون متصل بقوة من الرسم البياني الأزرق في رأس أصفر واحد.

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

الخوارزميات

خوارزميات خطية تعتمد على البحث العميق أولاً

تقوم العديد من الخوارزميات القائمة على البحث العميق أولاً بحساب المكونات المتصلة بقوة في وقت خطي.

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

الخوارزميات القائمة على إمكانية الوصول

تعتمد الخوارزميات الخطية السابقة على البحث العميق أولًا، والذي يُعتبر عمومًا صعب التوازي. في عام 2000، اقترح فليشر وآخرون [ 7 ] منهجًا قائمًا على فرق تسد يعتمد على استعلامات الوصول ، وتُعرف هذه الخوارزميات عادةً باسم خوارزميات SCC القائمة على الوصول. تقوم فكرة هذا المنهج على اختيار رأس محوري عشوائي وتطبيق استعلامات وصول أمامية وخلفية من هذا الرأس. يقسم الاستعلامان مجموعة الرؤوس إلى 4 مجموعات فرعية: رؤوس تم الوصول إليها بواسطة كلا البحثين، أو أحدهما، أو لم يتم الوصول إليها على الإطلاق. يمكن إثبات أن المكون المتصل بقوة يجب أن يكون موجودًا في إحدى المجموعات الفرعية. تشكل مجموعة الرؤوس التي تم الوصول إليها بواسطة كلا البحثين مكونًا متصلًا بقوة، ثم تُكرر الخوارزمية عملها على المجموعات الفرعية الثلاث الأخرى.

يُظهر التحليل أن زمن التشغيل التسلسلي المتوقع لهذه الخوارزمية هو O( n  log n )، أي أسرع بمعامل O(log n ) من الخوارزميات التقليدية. ويعود التوازي إلى: (1) سهولة موازاة استعلامات الوصول (على سبيل المثال، باستخدام البحث بالعرض أولاً (BFS)، وسرعتها العالية إذا كان قطر الرسم البياني صغيرًا)؛ و(2) استقلالية المهام الفرعية في عملية فرق تسد. تُحقق هذه الخوارزمية أداءً جيدًا على الرسوم البيانية الواقعية، [ 3 ] ولكن لا يوجد ضمان نظري للتوازي (على سبيل المثال، إذا لم يكن للرسم البياني أي حواف، فإن الخوارزمية تتطلب O( n ) مستوى من الاستدعاءات المتكررة).

أظهرت دراسة بليلوخ وآخرون [ 8 ] في عام 2016 أنه في حال تطبيق استعلامات الوصول بترتيب عشوائي، فإن الحد الأقصى للتكلفة O( n  log n ) يظل قائمًا. علاوة على ذلك، يمكن تجميع الاستعلامات في دفعات (أي 1، 2، 4، 8 استعلامات) وتشغيلها في وقت واحد في جولة واحدة. يبلغ المدى الإجمالي لهذه الخوارزمية log₂ n استعلام وصول، وهو على الأرجح التوازي الأمثل الذي يمكن تحقيقه باستخدام منهجية الوصول.

توليد رسوم بيانية عشوائية مترابطة بقوة

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

التطبيقات

يمكن استخدام خوارزميات إيجاد المكونات المتصلة بقوة لحل مسائل الإرضاء الثنائي (أنظمة المتغيرات المنطقية ذات القيود على قيم أزواج المتغيرات): كما أوضح أسبفال وبلاس وتارجان (1979) ، فإن مسألة الإرضاء الثنائي تكون غير قابلة للإرضاء إذا وفقط إذا كان هناك متغير v بحيث يكون كل من v ونفيه موجودين في نفس المكون المتصل بقوة في الرسم البياني للاستلزام الخاص بالمسألة. [ 10 ]

تُستخدم المكونات المتصلة بقوة أيضًا لحساب تحليل دولماج-مندلسون ، وهو تصنيف لحواف الرسم البياني ثنائي الأجزاء ، وفقًا لما إذا كان يمكن أن تكون جزءًا من تطابق مثالي في الرسم البياني أم لا. [ 11 ]

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

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

انظر أيضاً

مراجع

  1. ↑ نوتيلا، إيسكو؛ سويسالون-سوينين، إلياس (1994)، "حول إيجاد المكونات المتصلة بقوة في رسم بياني موجه"، رسائل معالجة المعلومات ، 49 (1): 9-14 ، doi : 10.1016/0020-0190(94)90047-7
  2. ↑ توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7القسم 22.5، الصفحات  552-557 .
  3. 1 2 هونغ، سونغباك؛ روديا، نيكول سي؛ أولوكوتون، كونلي (2013)، "حول الكشف المتوازي السريع عن المكونات المتصلة بقوة (SCC) في رسوم بيانية العالم الصغير" (ملف PDF) ، وقائع المؤتمر الدولي للحوسبة عالية الأداء والشبكات والتخزين والتحليل - SC '13 ، الصفحات 1-11 ، doi : 10.1145/2503210.2503246 ، ISBN  9781450323789، S2CID 2156324 
  4. ↑ شارير، ميشا (1981)، "خوارزمية الاتصال القوي وتطبيقاتها في تحليل تدفق البيانات"، الحوسبة والرياضيات مع التطبيقات ، 7 : 67-72 ، doi : 10.1016/0898-1221(81)90008-0
  5. ↑ تارجان، ر. إي. (1972)، "البحث العميق أولاً وخوارزميات الرسم البياني الخطي"، مجلة SIAM للحوسبة ، 1 (2): 146-160 ، doi : 10.1137/0201010 ، S2CID 16467262 
  6. ↑ ديكسترا، إدجر (1976)، منهج البرمجة ، نيوجيرسي: برنتيس هول، الفصل 25 .
  7. ↑ فليشر، ليزا ك.؛ هندريكسون، بروس؛ بينار، علي (2000)، "حول تحديد المكونات المتصلة بقوة بالتوازي" (ملف PDF) ، المعالجة المتوازية والموزعة ، سلسلة محاضرات في علوم الحاسوب، المجلد 1800، الصفحات 505-511 ، doi : 10.1007/3-540-45591-4_68 ، ISBN   978-3-540-67442-9
  8. ↑ بليلوش، غاي إي؛ غو، يان؛ شون، جوليان؛ صن، ييهان (2016)، "التوازي في الخوارزميات التزايدية العشوائية" (ملف PDF) ، وقائع ندوة ACM الثامنة والعشرين حول التوازي في الخوارزميات والهياكل - SPAA '16 ، الصفحات 467-478 ، arXiv : 1810.05303 ، doi : 10.1145/2935764.2935766 ، hdl : 1721.1/146176 ، ISBN  9781450342100.
  9. ↑ ماورر، بي إم (فبراير 2018)، توليد الرسوم البيانية العشوائية المتصلة بقوة (ملف PDF) ، المؤتمر الدولي لنمذجة ومحاكاة وأساليب الرؤية MSV'17، مطبعة CSREA، رقم ISBN 978-1-60132-465-8تم الاطلاع عليه بتاريخ 27 ديسمبر 2019
  10. ↑ أسبفال، بنغت؛ بلاس، مايكل ف.؛ تارجان، روبرت إي. (1979)، "خوارزمية خطية لاختبار صحة بعض الصيغ المنطقية الكمية"، رسائل معالجة المعلومات ، 8 (3): 121-123 ، doi : 10.1016/0020-0190(79)90002-4.
  11. ↑ دولماج، أ. ل. ومندلسون، ن. س. (1958)، "أغطية الرسوم البيانية ثنائية الأجزاء"، المجلة الكندية للرياضيات ، 10 : 517-534 ، doi : 10.4153/cjm-1958-052-0 ، S2CID 123363425 .
  12. ↑ روبنز، هـ. إي. (1939)، "نظرية حول الرسوم البيانية، مع تطبيق على مشكلة في التحكم المروري"، المجلة الرياضية الأمريكية الشهرية ، 46 (5): 281-283 ، doi : 10.2307/2303897 ، JSTOR 2303897 .