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

فليكن $G=(V,E)$ مخطط غير موجه، ولنفرض أنَّ $|V|=n$ وكذلك $|E|=m$ , تواصل الاضلاع بين رأسين $s,t\in V$ ونرمز لها ب- $\lambda (s,t)$ وهي مُعرف على انه القص (cut) الاصغر الذي يفصل بين s و- t , قص كهذا يُدعى القص ذو الحد الادنى بين s-t , بشكل واضح يمكن حساب $\lambda (s,t)$ في جدول لكل $O(n^{2})$ الازواج ولكن نريد وسيلة حساب اسرع وأكثر نجاعة.

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

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

تعريف

شجرة جوموري-هو $T=(V,F)$ لمخطط غير موجه $G=(V,E)$ هي شجرة ذات اوزان غير موجهة مُعرفة على رؤوس المُخطط بحيث تتحقق الخصائص التالية:

• لكل زوج $s,t\in V$ , $\lambda (s,t)$ هو وزن الضلع الاخف في المسار الوحيد بين s و- t في T (إذا يوجد أكثر من ضلع الذي هو الاخف حينها أي واحدة منها تفي بالغرض) نرمز لضلع كهذا ب- $e(s,t)$.
• لكل زوج $s,t\in V$ تقسيم الرؤوس الناتج عن حذف الضلع $e(s,t)$ هو قص ذو حد ادنى بين s-t في المُخطط الاصلي.

مثال: لننظر إلى الصورة كما هو مبين عن اليسار نرى المخطط وكل الاوزان على اضلعه 1 , وعلى اليمين نرى شجرة جوموري-هو الملائمة، مثلا بين الرأسين 2 و- 6 القص ذو الحد الادنى وزنه هو 4 , كما اننا لو ازلنا الضلع (2,6) من الشجرة تنقسم الشجرة لقسمين القسم الأول مركب من الرؤوس 1 و- 2 والباقي في المجموعة الأخرى، هذا التقسيم هو قص ذو حد ادنى في المُخطط الذي في الصورة.

لاحظ انه ليس مفهوم ضمنا ان هناك دوما شجرة تُحقق هذه المواصفات، وما حققه جوموري وهُو في عام 1961 ليس فقط ان هذه الشجرة دوما موجودة انما يمكن حسابها بواسطة حساب n-1 مسائل قص ذو حد ادنى. وفي الواقع لكل مخطط يمكن ان يكون له عدة اشجار جوموري-هو مختلفة.

خوارزمية

Gomory–Hu Algorithm

Input: A weighted undirected graph G = ((V_G, E_G), c).

Output: A Gomory–Hu Tree T = (V_T, E_T).

1. Set V_T = {V_G} and E_T = ∅.

2. Choose some X∈V_T with | X | ≥ 2 if such X exists. Otherwise, go to step 6.

3. For each connected component C = (V_C, E_C) in T∖X. Let S_C = ∪_vT∈VC v_T. Let S = { S_C | C is a connected component in T∖X}.

    Contract the components to form G' = ((V_G', E_G'), c'), where

V_G' = X ∪ S.

E_G' = E_G|_X×X ∪ {(u, S_C) ∈ X×S | (u,v)∈E_G for some v∈S_C}.

c' : V_G'×V_G'→R⁺ is the capacity function defined as,

1. if (u,S_C)∈E_G|_X×S, c'(u,S_C) = Σ_{v∈SC:(u,v)∈EG}c(u,v),
2. 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 S_C) ∪ (A' ∩ X) and B = (∪_SC∈B'∩S S_C) ∪ (B' ∩ X).

5. Set V_T = (V_T∖X) ∪ {A ∩ X, B ∩ X}.

    For each e = (X, Y) ∈ E_T do

If Y⊂A, set e' = (A ∩ X, Y), else set e' = (B ∩ X, Y).

Set E_T = (E_T∖{e}) ∪ {e'} and w(e') = w(e).

    Set E_T = E_T ∪ {(A∩X, B∩X)}.

    Set w((A∩X, B∩X)) = c'(A', B').

    Go to step 2.

6. Replace each {v} ∈ V_T by v and each ({u},{v}) ∈ E_T by (u,v). Output T.

مصادر

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