عرض مصدر شجرة جوموري-هو

{{لا مصدر|تاريخ=يناير 2022}}
{{وصلات قليلة|تاريخ=أبريل 2020}}
{{يتيمة|تاريخ=ديسمبر 2013}}

[[ملف:Gomory-hu tree example.png|تصغير|عن اليمين شجرة جوموري-هو وعن الشمال المُخطط |200px]]
فليكن <math>G=(V,E)</math> مخطط غير موجه، ولنفرض أنَّ <math>|V|=n</math> وكذلك <math> |E|=m</math> , تواصل الاضلاع بين رأسين <math>s,t\in V </math> ونرمز لها ب- <math>\lambda (s,t)</math> وهي مُعرف على انه القص (cut) الاصغر الذي يفصل بين s و- t , قص كهذا يُدعى [[مسألة القطع الأدنى|القص ذو الحد الادنى]] بين s-t , بشكل واضح يمكن حساب <math>\lambda (s,t)</math> في جدول لكل <math>O(n^2)</math> الازواج ولكن نريد وسيلة حساب اسرع وأكثر نجاعة.

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

== تعريف ==
شجرة جوموري-هو <math>T=(V,F)</math> لمخطط غير موجه <math>G=(V,E)</math> هي شجرة ذات اوزان غير موجهة مُعرفة على رؤوس المُخطط بحيث تتحقق الخصائص التالية:
* لكل زوج <math>s,t\in V </math> , <math>\lambda (s,t)</math> هو وزن الضلع الاخف في المسار الوحيد بين s و- t في T (إذا يوجد أكثر من ضلع الذي هو الاخف حينها أي واحدة منها تفي بالغرض) نرمز لضلع كهذا ب- <math>e(s,t)</math>.
* لكل زوج <math>s,t\in V </math> تقسيم الرؤوس الناتج عن حذف الضلع <math>e(s,t)</math> هو قص ذو حد ادنى بين s-t في المُخطط الاصلي.

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

لاحظ انه ليس مفهوم ضمنا ان هناك دوما شجرة تُحقق هذه المواصفات، وما حققه جوموري وهُو في عام 1961 ليس فقط ان هذه الشجرة دوما موجودة انما يمكن حسابها بواسطة حساب n-1 مسائل قص ذو حد ادنى. وفي الواقع لكل مخطط يمكن ان يكون له عدة اشجار جوموري-هو مختلفة.
== خوارزمية ==
<div dir="LTR">
'''Gomory–Hu Algorithm'''
:''Input'': A weighted undirected graph G = ((''V''<sub>G</sub>, ''E''<sub>G</sub>), ''c'').
: ''Output'': A Gomory–Hu Tree ''T'' = (''V''<sub>T</sub>, ''E''<sub>T</sub>).
:1. Set ''V''<sub>T</sub> = {''V''<sub>G</sub>} and ''E''<sub>T</sub> = ∅.
:2. Choose some ''X''∈''V''<sub>T</sub> with | ''X'' | ≥ 2 if such ''X'' exists. Otherwise, go to step 6.
:3. For each connected component ''C'' = (''V''<sub>C</sub>, ''E''<sub>C</sub>) in ''T''∖''X''. Let ''S''<sub>C</sub> = ∪<sub>v<sub>T</sub>∈V<sub>C</sub></sub> ''v''<sub>T</sub>. Let ''S'' = { ''S''<sub>C</sub> | ''C'' is a connected component in ''T''∖''X''}.
:&nbsp;&nbsp;&nbsp; Contract the components to form ''G''<nowiki>'</nowiki> = ((''V''<sub>G<nowiki>'</nowiki></sub>, ''E''<sub>G<nowiki>'</nowiki></sub>), ''c''<nowiki>'</nowiki>), where
:: ''V''<sub>G<nowiki>'</nowiki></sub> = ''X'' ∪ ''S''.
:: ''E''<sub>G<nowiki>'</nowiki></sub> = ''E''<sub>G</sub>|<sub>X×X</sub> ∪ {(''u'', ''S''<sub>C</sub>) ∈ ''X''×''S'' | (''u'',''v'')∈''E''<sub>G</sub> for some ''v''∈''S''<sub>C</sub>}.
:: ''c''<nowiki>'</nowiki> : ''V''<sub>G<nowiki>'</nowiki></sub>×''V''<sub>G<nowiki>'</nowiki></sub>→''R''<sup>+</sup> is the capacity function defined as,
::# if (''u'',''S''<sub>C</sub>)∈''E''<sub>G</sub>|<sub>X×S</sub>, ''c''<nowiki>'</nowiki>(''u'',''S''<sub>C</sub>) = Σ<sub>v∈S<sub>C</sub>:(u,v)∈E<sub>G</sub></sub>''c''(''u'',''v''),
::# ''c''<nowiki>'</nowiki>(''u'',''v'') = ''c''(''u'',''v'') otherwise.
:4. Choose two vertices ''s'', ''t'' ∈ ''X'' and find a minimum ''s''-''t'' cut (''A''<nowiki>'</nowiki>,''B''<nowiki>'</nowiki>) in ''G''<nowiki>'</nowiki>.
:&nbsp;&nbsp;&nbsp; Set ''A'' = (∪<sub>S<sub>C</sub>∈''A''<nowiki>'</nowiki>∩''S''</sub> ''S''<sub>C</sub>) ∪ (''A''<nowiki>'</nowiki> ∩ ''X'') and ''B'' = (∪<sub>S<sub>C</sub>∈''B''<nowiki>'</nowiki>∩''S''</sub> ''S''<sub>C</sub>) ∪ (''B''<nowiki>'</nowiki> ∩ ''X'').
: 5. Set ''V''<sub>T</sub> = (''V''<sub>T</sub>∖''X'') ∪ {''A'' ∩ ''X'', ''B'' ∩ ''X''}.
:&nbsp;&nbsp;&nbsp; For each ''e'' = (''X'', ''Y'') ∈ ''E''<sub>T</sub> do
:: If ''Y''⊂''A'', set ''e''<nowiki>'</nowiki> = (''A'' ∩ ''X'', ''Y''), else set ''e''<nowiki>'</nowiki> = (''B'' ∩ ''X'', ''Y'').
:: Set ''E''<sub>T</sub> = (''E''<sub>T</sub>∖{''e''}) ∪ {''e''<nowiki>'</nowiki>} and ''w''(''e''<nowiki>'</nowiki>) = ''w''(''e'').
:&nbsp;&nbsp;&nbsp; Set ''E''<sub>T</sub> = ''E''<sub>T</sub> ∪ {(''A''∩''X'', ''B''∩''X'')}.
:&nbsp;&nbsp;&nbsp; Set ''w''((''A''∩''X'', ''B''∩''X'')) = ''c''<nowiki>'</nowiki>(''A''<nowiki>'</nowiki>, ''B''<nowiki>'</nowiki>).
:&nbsp;&nbsp;&nbsp; Go to step 2.
: 6. Replace each {''v''} ∈ ''V''<sub>T</sub> by ''v'' and each ({''u''},{''v''}) ∈ ''E''<sub>T</sub> by (''u'',''v''). Output ''T''.
</div>
== مصادر ==
{{مراجع}}

* المقال بالإنجليزية [[:en:Gomory–Hu tree|Gomory–Hu tree]] , منه اخذت الخوارزمية.
* Ming-Yang Kao , "encyclopedia of algorithms", pg. 164-166
{{شريط بوابات|رياضيات}}

[[تصنيف:استمثال توافقي]]
[[تصنيف:خوارزميات تعتمد على نظرية البيان]]