شجرة جوموري-هو
المحتويات

على سبيل التعريف، فليكن مخطط غير موجه، ولنفرض أنَّ وكذلك , تواصل الاضلاع بين رأسين ونرمز لها ب- وهي مُعرف على انه القص (cut) الاصغر الذي يفصل بين s و- t , قص كهذا يُدعى القص ذو الحد الادنى بين s-t , بشكل واضح يمكن حساب في جدول لكل الازواج ولكن نريد وسيلة حساب اسرع وأكثر نجاعة. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
كذلك، اشجار جوموري-هو (والمعروفة كذلك باشجار القص) تعطي وسيلة ناجعة لهذه المسألة وهي ايجاد القص ذو الحد الادنى بين كل الازواج، وهذه الاشجار تستعمل مساحة ذاكرة ولكل زوج s-t يمكن معرفة قيمة الحد الادنى بوقت ثابت أي (O(1 وقت.
تعريف
وفي السياق ذاته، لكل زوج تقسيم الرؤوس الناتج عن حذف الضلع هو قص ذو حد ادنى بين s-t في المُخطط الاصلي.
وعلى صعيد آخر، شجرة جوموري-هو لمخطط غير موجه هي شجرة ذات اوزان غير موجهة مُعرفة على رؤوس المُخطط بحيث تتحقق الخصائص التالية:
من جهة ثانية، لكل زوج , هو وزن الضلع الاخف في المسار الوحيد بين s و- t في T (إذا يوجد أكثر من ضلع الذي هو الاخف حينها أي واحدة منها تفي بالغرض) نرمز لضلع كهذا ب- .
وعلى صعيد آخر، مثال: لننظر إلى الصورة كما هو مبين عن اليسار نرى المخطط وكل الاوزان على اضلعه 1 , وعلى اليمين نرى شجرة جوموري-هو الملائمة، مثلا بين الرأسين 2 و- 6 القص ذو الحد الادنى وزنه هو 4 , كما اننا لو ازلنا الضلع (2,6) من الشجرة تنقسم الشجرة لقسمين القسم الأول مركب من الرؤوس 1 و- 2 والباقي في المجموعة الأخرى، هذا التقسيم هو قص ذو حد ادنى في المُخطط الذي في الصورة.
خوارزمية
من جانب آخر، لاحظ انه ليس مفهوم ضمنا ان هناك دوما شجرة تُحقق هذه المواصفات، وما حققه جوموري وهُو في عام 1961 ليس فقط ان هذه الشجرة دوما موجودة انما يمكن حسابها بواسطة حساب n-1 مسائل قص ذو حد ادنى. وفي الواقع لكل مخطط يمكن ان يكون له عدة اشجار جوموري-هو مختلفة.
Gomory–Hu Algorithm
- Input: A weighted undirected graph G = ((VG, EG), c).
- Output: A Gomory–Hu Tree T = (VT, ET).
- 1. Set VT = {VG} and ET = ∅.
- 2. Choose some X∈VT with – X – ≥ 2 if such X exists. Otherwise, go to step 6.
- Contract the components to form G' = ((VG', EG'), c'), where
- VG' = X ∪ S.
- c' : VG'×VG'→R+ is the capacity function defined as,
- c'(u,v) = c(u,v) otherwise.
- 4. Choose two vertices s, t ∈ X and find a minimum s-t cut (A',B') in G'.
- Set A = (∪SC∈A'∩S SC) ∪ (A' ∩ X) and B = (∪SC∈B'∩S SC) ∪ (B' ∩ X).
- 5. Set VT = (VT∖X) ∪ {A ∩ X, B ∩ X}.
- For each e = (X, Y) ∈ ET do
- If Y⊂A, set e' = (A ∩ X, Y), else set e' = (B ∩ X, Y).
- Set ET = (ET∖{e}) ∪ {e'} and w(e') = w(e).
- Set ET = ET ∪ {(A∩X, B∩X)}.
- Set w((A∩X, B∩X)) = c'(A', B').
- Go to step 2.
- 6. Replace each {v} ∈ VT by v and each ({u},{v}) ∈ ET by (u,v). Output T.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟