شجرة جوموري-هو

بكىشمن

فليكن مخطط غير موجه، ولنفرض أنَّ وكذلك , تواصل الاضلاع بين رأسين ونرمز لها ب- وهي مُعرف على انه القص (cut) الاصغر الذي يفصل بين s و- t , قص كهذا يُدعى القص ذو الحد الادنى بين s-t , بشكل واضح يمكن حساب في جدول لكل الازواج ولكن نريد وسيلة حساب اسرع وأكثر نجاعة.

عن اليمين شجرة جوموري-هو وعن الشمال المُخطط

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

تعريف

عدل

شجرة جوموري-هو   لمخطط غير موجه   هي شجرة ذات اوزان غير موجهة مُعرفة على رؤوس المُخطط بحيث تتحقق الخصائص التالية:

  • لكل زوج   ,   هو وزن الضلع الاخف في المسار الوحيد بين s و- t في T (إذا يوجد أكثر من ضلع الذي هو الاخف حينها أي واحدة منها تفي بالغرض) نرمز لضلع كهذا ب-  .
  • لكل زوج   تقسيم الرؤوس الناتج عن حذف الضلع   هو قص ذو حد ادنى بين s-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 XVT with | X | ≥ 2 if such X exists. Otherwise, go to step 6.
3. For each connected component C = (VC, EC) in TX. Let SC = ∪vT∈VC vT. Let S = { SC | C is a connected component in TX}.
    Contract the components to form G' = ((VG', EG'), c'), where
VG' = XS.
EG' = EG|X×X ∪ {(u, SC) ∈ X×S | (u,v)∈EG for some vSC}.
c' : VG'×VG'R+ is the capacity function defined as,
  1. if (u,SC)∈EG|X×S, c'(u,SC) = Σv∈SC:(u,v)∈EGc(u,v),
  2. c'(u,v) = c(u,v) otherwise.
4. Choose two vertices s, tX and find a minimum s-t cut (A',B') in G'.
    Set A = (∪SCA'∩S SC) ∪ (A' ∩ X) and B = (∪SCB'∩S SC) ∪ (B' ∩ X).
5. Set VT = (VTX) ∪ {AX, BX}.
    For each e = (X, Y) ∈ ET do
If YA, set e' = (AX, Y), else set e' = (BX, Y).
Set ET = (ET∖{e}) ∪ {e'} and w(e') = w(e).
    Set ET = ET ∪ {(AX, BX)}.
    Set w((AX, BX)) = c'(A', B').
    Go to step 2.
6. Replace each {v} ∈ VT by v and each ({u},{v}) ∈ ET by (u,v). Output T.

مصادر

عدل
  • المقال بالإنجليزية Gomory–Hu tree , منه اخذت الخوارزمية.
  • Ming-Yang Kao , "encyclopedia of algorithms", pg. 164-166