كيفية العثور على جسر في الرسم البياني: خوارزميات بسيطة وأمثلة

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

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

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

1. تحديد جسر في الرسم البياني
2. خوارزميات لإيجاد الجسور في الرسم البياني
3. خوارزمية اجتياز العمق الأول (دفس)
4. خوارزمية تاراجان
5. خوارزمية البحث في العمق
6. خوارزمية البحث الاتساع أولا
7. أمثلة على البحث عن الجسور في الرسم البياني
8. مثال 1: إيجاد الجسور في رسم بياني متصل
9. المثال 2: العثور على الجسور في الرسم البياني الموجه
10. سؤال وجواب
11. ما هو جسر في الرسم البياني?
12. لماذا أحتاج إلى العثور على الجسور في الرسم البياني?
13. ما هي الخوارزميات الموجودة للعثور على الجسور في الرسم البياني?

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

الجسر في الرسم البياني هو حافة ، تؤدي إزالتها إلى ظهور مكونات اتصال جديدة.

بمعنى آخر ، إذا أزلنا الجسر من الرسم البياني ، فسيزداد عدد مكونات الاتصال في الرسم البياني. الجسر هو اتصال مباشر بين مكونين من مكونات الاتصال.

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

يمكن تنفيذ تعريف الجسر في الرسم البياني باستخدام خوارزميات مختلفة. تعتمد إحدى الخوارزميات البسيطة لتحديد الجسر على استخدام اجتياز الرسم البياني في العمق.

خوارزمية تحديد الجسر في الرسم البياني:

1. حدد قمة عشوائية وابدأ في عبور الرسم البياني بعمق.
2. عند العبور ، احفظ معلومات حول وقت الدخول إلى كل رأس والحد الأدنى لوقت العودة من كل رأس.
3. إذا كانت الحافة (ش, الخامس) يحدث أثناء العبور ، بحيث يكون وقت الدخول قمة الرأس الخامس أقل من الحد الأدنى للوقت للعودة من قمة الرأس ش ، ثم هذه الحافة هي جسر.

تسمح لك الخوارزمية بالعثور على جميع الجسور في الرسم البياني وتحديد عددها. يمكن أيضا تعديله للبحث عن الجسور في رسم بياني موجه.

بمعرفة موقع الجسور في الرسم البياني ، يمكننا تحليل بنية الشبكة وتحسينها ، وكذلك منع مشاكل الاتصال المحتملة.

خوارزميات لإيجاد الجسور في الرسم البياني

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

هناك العديد من الخوارزميات لإيجاد الجسور في الرسم البياني. دعونا نلقي نظرة على اثنين من الخوارزميات الأكثر شعبية: عمق أول اجتياز (دفس) وخوارزمية تاراجان.

خوارزمية اجتياز العمق الأول (دفس)

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

1. حدد رأسا تعسفيا في الرسم البياني وقم بتمييزه على أنه تمت زيارته.
2. قم بإجراء زحف عمق أولا من الرأس المحدد.
3. خلال اجتياز ، تحقق مما إذا كان هناك قمة الرأس التي تم الانتقال إلى قمة الرأس التي تمت زيارتها بالفعل ، ثم هذه الحافة هي جسر.
4. ضع علامة على كل قمة وحافة تمت زيارتها في الاتجاه المعاكس.

تجعل خوارزمية اجتياز العمق أولا من الممكن العثور بكفاءة على الجسور في الرسم البياني ، ولكن تعقيدها هو ا(الخامس + ه) ، أين الخامس هو عدد الرؤوس في الرسم البياني ، ه هو عدد الحواف.

خوارزمية تاراجان

خوارزمية تاراجان هو نسخة محسنة من خوارزمية دفس ويسمح لك لإيجاد الجسور في الرسم البياني في الوقت الخطي س(الخامس + ه).

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

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

خوارزمية البحث في العمق

خوارزمية البحث العمق أولا (دفس) هي واحدة من أبسط خوارزميات اجتياز الرسم البياني. يتمثل جوهر الخوارزمية في استكشاف جميع رؤوس الرسم البياني عن طريق النزول المتسلسل لأسفل الحواف وفحص جميع الرؤوس المجاورة.

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

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

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

قد يبدو أبسط تنفيذ لخوارزمية البحث عن العمق أولا كما يلي:

1. حدد قمة البداية ووضع علامة عليه كما زار.
2. ضع قمة البداية على المكدس.
3. في حين أن المكدس ليس فارغا:

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

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

خوارزمية البحث الاتساع أولا

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

يمكن تمثيل عملية خوارزمية البحث الاتساع أولا على النحو التالي:

1. حدد قمة البداية ووضع علامة عليه كما زار.
2. أضف قمة البداية إلى قائمة الانتظار.
3. حتى تصبح قائمة الانتظار فارغة ، كرر الخطوات التالية:

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

أمثلة على البحث عن الجسور في الرسم البياني

مثال 1:

• رسم بياني به 5 رؤوس: أ ، ب ، ج ، د ، هـ.
• حواف: أب ، أس ، بد ، سي ، دي.

في هذا الرسم البياني ، الجسر هو الحافة م.

المثال 2:

• رسم بياني مع 6 رؤوس: أ ، ب ، ج ، د ، ه ، و.
• حواف: أب ، أس ، بد ، سي ، دي ، إف.

في هذا الرسم البياني ، الجسور هي الحواف أس و سي.

المثال 3:

• رسم بياني به 7 رؤوس: أ ، ب ، ج ، د ، هـ ، و ، ز.
• حواف: أب ، أس ، بد ، سي ، دي ، فغ.

في هذا الرسم البياني ، الجسور هي الحواف أس و سي.

المثال 4:

• رسم بياني مع 4 رؤوس: أ ، ب ، ج ، د.
• الحواف: أب ، قبل الميلاد ، قرص مضغوط ، م.

لا توجد جسور في هذا الرسم البياني.

المثال 5:

• رسم بياني مع 3 رؤوس: أ ، ب ، ج.
• الحواف: أب ، قبل الميلاد.

في هذا الرسم البياني ، الجسر هو الحافة قبل الميلاد.

مثال 1: إيجاد الجسور في رسم بياني متصل

لنفكر في مثال بسيط لإيجاد الجسور في رسم بياني متصل. لنتخيل أن لدينا الرسم البياني التالي:

بادئ ذي بدء ، دعنا نرقم جميع رؤوس الرسم البياني:

1. A
2. B
3. C
4. D
5. E
6. F
7. G

بعد ذلك ، لنقم ببناء جدول مجاور لهذا الرسم البياني:

باستخدام خوارزمية البحث الجسر ، يمكننا الحصول على النتيجة التالية:

• الجسور: أب ، دي
• غير الجسور: قبل الميلاد ، دينار بحريني ، سد، إف، فغ

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

المثال 2: العثور على الجسور في الرسم البياني الموجه

في هذا المثال ، لنفكر في خوارزمية لإيجاد الجسور في الرسم البياني الموجه. الخوارزمية مشابهة تماما لخوارزمية الرسم البياني غير الموجه ، ولكن لديها بعض الاختلافات.

خوارزمية لإيجاد الجسور في الرسم البياني الموجه:

1. نتجول في جميع رؤوس الرسم البياني بترتيب اجتيازها (على سبيل المثال ، باستخدام اجتياز العمق أولا).
2. لكل قمة ، نقوم بتنفيذ الإجراءات التالية:

مثال على الخوارزمية:

يمكن أن نرى من الجدول أن الحافة (1 ، 2) والحافة (3 ، 4) جسور ، لأن الطابع الزمني للخروج من فيرتكس يو أقل من الطابع الزمني للدخول إلى فيرتكس الخامس.

تسمح لك خوارزمية العثور على الجسور في الرسم البياني الموجه بالعثور على جميع الجسور في الرسم البياني في الوقت الخطي س(الخامس + ه) ، أين الخامس هو عدد الرؤوس ، ه هو عدد الحواف.

سؤال وجواب

ما هو جسر في الرسم البياني?

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

لماذا أحتاج إلى العثور على الجسور في الرسم البياني?

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

ما هي الخوارزميات الموجودة للعثور على الجسور في الرسم البياني?

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