K_Edge connected

مشروع يختص بالمشاكل الهامة والتي تحتاج لحل مناسب بزمن فعال وهي مشكلة ترابط البيان

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

والجواب سيكون نعم أم لا لكن بزمن فعال جداً .

•الطريقة المناسبة للإجابة عن هذا السؤال هو تمثيل البيان وحساب التدفق بين المنبع و الهدف لحساب ال K edge connected

•بنية المعطيات المستعملة هي ford Fulkerson لحساب ال max flow.

•بم تناولعدة طرق لحساب ال K edge لكل منها حسنات و سلبيات مع مقارنات بين تلك الطرق من حيث زمن التنفيذ. ومن هذه الطرق:

الفصل سنستعرض أهم الخوارزميات المستخدمة لحساب K Edge Connected والطرق المستخدمة هي

•Ford Fulkerson By BFS

•Ford Fulkerson By DFS

•Ford Fulkerson By DFS Improved

•Max Flow Using Spanning tree

•Max Flow ST improved

•Max Flow by dominating set

•Max Flow by dominating set Improved