ضرب دو عدد به صورت موازی و تفاوت آن با جمع اعداد

برای جمع اعداد اگر رقمهای اعداد را از چپ به راست داشتیم می توانستیم به ترتیب با هم جمع کنیم و جواب به دست می آمد. برای ضرب دو عدد چون بیت اول عدد اول باید در همه ی بیت های عدد دوم ضرب شود و بعد به سراغ بیت دوم عدد اول برویم، نمی توانیم دو عدد را مثل هم وارد سیستم کنیم. از طرفی هر عدد را یک بار بیشتر نمی توانیم وارد کنیم، پس باید کاری کنیم که با همان یک بار عمل ضرب انجام شود. قسمت ساده ای که می دانیم چطور انجام بدهیم جمع حاصل ضرب هر بیت عدد اول در عدد دوم است. با توجه به اینکه باید بتوانیم حاصل جمع های میانی را نگه داریم و جمع کنیم تا به جواب آخر برسیم، به 2n پردازنده نیاز داریم، که از آنجایی که طول جواب از این مقدار کمتر است می توانیم هر بیت جواب را در یک پردازنده نگه داریم. بیت jام جواب از رابطه ی زیر به دست می آید:

c_j = sum_i_1_j (a_i*b_(j-i+1))+carry(j-1)

برای محاسبه ی رابطه ی بالا در مدل آرایه خطی، اولین چیزی که به ذهن می رسد این است که خود عدد a و معکوس عدد b را وارد سیستم کنیم، اما از آنجایی که نمی خواهیم اعداد ورودی را تغییر بدهیم، عدد b را از سمت دیگر وارد می کنیم و خود به خود باعث می شود ترتیب آن عکس ترتیب a باشد.

وقتی دو عدد کامل وارد پردازنده ها می شوند به صورت متوالی نوشته شده اند:

a3 a2 a1 b3 b2 b1

next step:

    a3 a2 a1

        b3 b2 b1

همان طور که دیدید به جای اینکه دو رقم اول در هم ضرب شوند، رقم های بعدی ضرب شدند. برای حل این مشکل از بیت فاصله استفاده می کنیم. (این مشکل در مراحل بعد هم به این صورت خواهد بود). برای حل مشکل اولین بیت باید یک فاصله به اول یکی از اعداد اضافه کنیم و برای بیت های بعد باید یکی در میان بین رقم ها فاصله باشد تا وقتی هر دو عدد یک پردازنده جا به جا می شوند، فقط یک بیت از آنها در یک پردازنده قرار بگیرند (زوج بیت دیگر حداقل یکی از آنها فاصله باشد و ورود آن هیچ عملی انجام ندهد).

بعد از این دیگر کافی است که جمع ها را انجام بدهیم و در هر پردازنده حاصل را نگه داریم.

برای حل مشکل بیکار بودن پردازنده ها در نصف سیکل ها از یکی از دو مدل زیر می توانیم استفاده کنیم:

حل تمرین های WS فصل 5.1-5.3

1- در مساله k-برش ماکسیمم، گراف بدون جهت G با وزنهای نامنفی wij>=0 به ازای هر یال (i,j) گراف داده شده است. هدف افراز راسهای گراف به k قسمت V1,...,Vk است طوری که وزن یالهایی که سرهای مختلف آن در مولفه های همبندی مختلف است ماکسیمم شود.

یک الگوریتم (k-1)/k تقریبی برای MAX k-Cut بدهید.

حل: k-برش مینیمم را که با k تا برش ایزوله سبکتر به دست می آوردیم، این را با k تا برش ایزوله ی سنگین تر به دست می آوریم. (برش ایزوله را هم با سنگین ترین یالها حساب می کنیم).

میانگین وزن k-1 برش سنگینتر از میانگین وزن k برش سنگینتر بیشتر است، پس ضریب تقریب (k-1)/k است.

2-الگوریتم حریصانه زیر را برای مساله برش ماکسیمم در نظر بگیرید. فرض کنید راسها از 1 تا n برچسب زده شده اند. در تکرار اول، الگوریتم راس 1 را در U قرار می دهد. در تکرار k-ام الگوریتم راس k را یا در U یا در W می گذاریم. برای اینکه تصمیم بگیریم کدامیک از انتخابها را انجام دهیم به مجموعه یالهای F که راس k یک سر آنها است و سر دیگر آنها بین راسهای 1,...,(k-1) است، پس F={(j,k)| 1<= j <= k-1}. ما بر اساس اینکه کدام انتخاب تعداد یالهای F را که بریده می شود بیشتر می کند، عمل می کنیم.

الف) ثابت کنید که این الگوریتم 1/2-تقریبی است. (برای مساله برش ماکسیمم)

ب) ثابت کنید که این الگوریتم معادل غیرتصادفی کردن الگوریتم بخش 5.1 با روش امیدریاضی شرطی است.

حل:

الف)

OPT <= sum(deg_U(v))+sum(deg_W(v)) <= 2*sum(max(deg_U(v),deg_W(v)))

ALG(v) = max(deg_U(v),deg_W(v)) ==> ALG = sum(max(deg_U(v),deg_W(v)))

==> OPT <= 2*ALG

(نکته اینه که سوال تکراریه..؟)

ب)

pr(k in U)=1/2 = pr(k in W)

E(#edges) = E(#edges| v_k in U)Pr(v_k in U)+E(#edges| v_k in W)pr(v_k in W)=1/2(E(#edges|v_k in U)+E(#edges|v_k in W) )

b_k = argmax( E(#edges|v_k in b_k) ) ==> E(#edges|v_k in b_k) >= E(#edges)

(j,k) in F: pr((j,k) in U| v_(k-1)=b_(k-1),...) = 1 if j in W, 1-(1/2)^k if j in U

3- در برش ماکسیمم جهت دار (MAX DICUT)، یک گراف جهتدار داده شده و هر یال آن وزن نامنفی دارد wij >= 0. هدف تقسیم راسها به دو زیرمجموعه U و W است که جمع وزن یالهایی که از U به W می روند ماکسیمم شود. یک الگوریتم تصادفی 1/4-تقریبی برای این مساله بدهید.

همان استدلال و روش سوال بالا+

E(#edges) >= 1/4 OPT

که 1/4 از ضرب احتمال حضور سر اول یال در U و سر دوم آن در W به دست آمده است: 1/2*1/2=1/4

تمرین های WS فصل 5.1-5.3

فصل 5 وزیرانی: k-مرکز

تعریف مساله k-مرکز: مجموعه ای از شهرها و فاصله ی بین هر دو شهر داده شده است. k شهر را انتخاب کنید و در آنها انبار بسازید که حداکثر فاصله ی هر شهر تا نزدیک ترین انبار به آن مینیمم شود.

این مساله و مساله ی وزن دار آن را با شرط برقرار بودن نامساوی مثلث حل می کنیم. بدون این شرط مساله قابل تقریب زدن نیست (مگر اینکه p=np باشد).

تکنیکی که برای حل مسائل این فصل استفاده می شود "هرس پارامتری" نام دارد. در فصل 17 از این تکنیک به همراه LP استفاده می کنیم.

مساله k-مرکز متریک: گراف کامل بدون جهت با یالهای وزندار که در نامساوی مثلث صدق می کنند (گراف G) و عدد صحیح مثبت k داده شده است. زیرمجموعه ای از رئوس (زیرمجموعه S) و هر راس دلخواهی از گراف را در نظر بگیرید، connect(v,S) را هزینه ی سبکترین یال از v به یک راس از S تعریف می کنیم. مساله پیدا کردن زیرمجموعه ی S ای است که |S|=k و عبارت زیر را مینیمم کند:

max_v (connect(v,S))

*هرس پارامتری برای حل مساله k-مرکز متریک

اگر هزینه ی جواب بهینه را بدانیم، می توانیم قسمت های زائد ورودی را هرس کنیم و مساله جستجو برای جواب را ساده تر کنیم. البته به دست آوردن هزینه ی جواب بهینه معمولا قسمت اصلی حل کردن مساله است. تکنیک هرس پارامتری به این صورت این مشکل را حل می کند: یک پارامتر t انتخاب می شود، که می تواند به عنوان حدس جواب بهینه در نظر گرفته شود. برای هر مقدار t، مساله داده شده (I) با حذف قسمت هایی که در هیچ جوابی با هزینه ی بیشتر از t هرس می شود. نسخه ی هرس شده را I(t) بنامید. الگوریتم از دو مرحله تشکیل شده است: 1) از یک خانواده از نمونه های I(t) برای محاسبه ی کران پایین جواب بهینه استفاده می شود (t*). در قدم دوم یک جواب برای نمونه ی I(a.t*) به دست می آید (برای a مناسب).

بیان مجدد مساله k-مرکز با هرس پارامتری: یالهای گراف G را به ترتیب از وزن کمتر به بیشتر مرتب می کنیم. گراف Gi را با همان مجموعه رئوس G و مجموعه ی i یال سبکتر G تعریف می کنیم. یک مجموعه ی غالب (dominating set) در گراف بدون جهت را زیرمجموعه ای S از رئوس تعریف می کنیم که هر راس خارج از این مجموعه مجاور یک راس در مجموعه S باشد. قرار دهید dom(H) را اندازه ی مجموعه غالب با کمترین تعداد اعضا. محاسبه ی dom(H) یک مساله np-سخت است. مساله k-مرکز معادل پیدا کردن کوچکترین اندیس i است که Gi یک مجموعه غالب با اندازه ی حداکثر k باشد؛ یعنی Gi شامل k گراف ستاره (دوبخشی کامل 1وp که p>1) باشد که همه ی راسها را می پوشاند. اگر i* را کوچکترین اندیس با این شرایط بگیریم، هزینه ی cost(ei*) هزینه ی k-مرکز بهینه است. {یالی که در آخرین مرحله اضافه می شود، ماکسیمم فاصله تا نزدیک ترین مرکز است.}. ما این هزینه را با OPT نشان می دهیم. خانواده ای که با آن کار می کنیم، گرافهای G1,..,Gm هستند.

مربع گراف H را تعریف می کنیم: گرافی که در آن بین دو راس یال هست، اگر در گراف اولیه بین آنها مسیر به طول حداکثر 2 وجود داشته باشد. به این گراف H^2 می گوییم.

ساختار زیر روشی برای پیدا کردن کران پایین برای OPT می دهد.

لم: گراف H داده شده است، I را یک مجموعه مستقل (زیرگراف تهی) از H^2 فرض کنید. در این صورت |I| <= dom(H).

اثبات: فرض کنید D مجموعه غالب در H باشد. آنگاه H شامل |D| ستاره است که همه ی راسها را می پوشانند. چون هر کدام از این ستاره ها یک خوشه(زیرگراف کامل) در H^2 می شوند، H^2 شامل |D| زیرگراف کامل است که تمام راسها را می پوشانند. بدیهی است که I حداکثر می تواند یک راس از هر زیرگراف کامل بردارد، پس لم برقرار است.

*الگوریتم k-مرکز متریک

1) گرافهای G1^2,..,Gm^2 را بسازید.

2) مجموعه مستقل ماکسیمال در هر کدام از گرافهای Gi^2 را بسازید (Mi).

3) کوچکترین اندیس i را برگردانید که |Mi| <= k باشد. (اندیس j-ام)

4) Mj را به عنوان جواب برگردانید.

*کران پایین الگوریتم:

لم: به ازای j تعریف شده در الگوریتم، cost(ej) <= OPT. (که ej همان طور که قبلا تعریف کردیم j-امین کوچکترین یال است).

اثبات: به ازای هر i<j داریم |Mi|>k است. {چون j اولین اندیسی است که |Mj| <= k}. طبق لم dom(Gi)>k و در نتیجه i* > i. پس j<=i*.

قضیه: ضریب تقریب الگوریتم قبل برای k-مرکز 2 است.

اثبات: مشاهده ی اصلی این است که مجموعه مستقل ماکسیمال I در گراف، یک مجموعه غالب هم هست (اثبات: برهان خلف: اگر راسی باشد که توسط I پوشش داده نشده باشد، آن را می توان به I اضافه کرد و جواب باز هم یک مجموعه مستقل خواهد بود که اندازه ی بیشتری دارد که با ماکسیمال بودن I تناقض دارد). پس در Gj^2 گراف های ستاره وجود دارند که مرکز آنها روی راسهای Mj است و همه ی راسها را پوشش می دهند. طبق نامساوی مثلث، وزن هر یال که در ساخت ستاره ها استفاده شده حداکثر دو برابر وزن یال ej است. پس قضیه با کمک لم قبل ثابت می شود.

حالا نشان می دهیم که 2 بهترین ضریب برای مساله k-مرکز متریک است.

قضیه: اگر p=np نباشد، هیچ الگوریتم چندجمله ای به ضریب بهتر از 2-epsilon برای مساله k-مرکز متریک نمی رسد.

اثبات: نشان می دهیم چنین الگوریتمی می تواند مساله dominating set را در زمان چندجمله ای حل کند. ایده آن مشابه اثبات فصل قبل است و شامل کاهش از مساله k-مرکز به مساله dominating set است. فرض کنید گراف G یک نمونه از مساله dominating set باشد. گراف کامل G' را به این صورت بسازید که راسهای آن همان رئوس G باشد و هر یال G در آن وزن 1 و هر یال دیگر وزن 2 داشته باشد. بدیهی است که G' در نامساوی مثلث صدق می کند. این کاهش در شرایط زیر صدق می کند:

- اگر dom(G) <=k باشد، G' یک k-مرکز با هزینه 1 دارد.

- اگر dom(G) >k بود، هزینه بهینه k-مرکز برای G' مقدار 2 است.

در حالت اول، وقتی روی G' الگوریتم را اجرا می کنیم، یک 2-epsilon تقریب است پس باید جواب 1 بدهد پس نمی تواند شامل هیچ یال با وزن 2 باشد. پس با استفاده از این الگوریتم می توانیم بین دو حالت ممکن تمایز قائل شویم، در نتیجه مساله dominating set را حل کنیم.

----------------------------------------------------------------------------------------------------------------------------------------------------

نسخه وزن دار

از تکنیک هرس پارامتری برای به دست آوردن الگوریتم با ضریب تقریب 3 برای تعمیم زیر از مساله k-مرکز استفاده می کنیم.

مساله k-مرکز وزن دار: علاوه بر تابع وزن روی یالها، یک تابع وزن روی راسها تعریف می کنیم و یک کران W. مساله باید زیرمجموعه ای از رئوس را بردارد که وزن آنها حداکثر W باشد و همان تابع هزینه ی قبلی را مینیمم کند:

max_v_V (min_u_S(cost(u,v)))

فرض کنید wdom(G) وزن dominating set با کمترین وزن را در G نشان دهد. پس با توجه به تعریف Gi، باید کوچکترین اندیسی را پیدا کنیم که wdom(Gi) <= w باشد. اگر i* این اندیس باشد، آنگاه هزینه جواب بهینه OPT=cost(ei*) است.

یک گراف با رئوس وزندار H داده شده، I را مجموعه مستقل H^2 فرض کنید. برای هر u عضو I قرار دهید s(u) = کم وزن ترین همسایه u در H که خود u هم می تواند همسایه ی خودش باشد. (توجه کنید که همسایه از H به دست می آید نه از H^2). مجموعه S را مجموعه همه ی همسایه های رئوس I قرار دهید. حقیقت زیر متناظر لم 5.2 برای به دست آوردن کران پایین به کار می رود.

لم:

w(S) <= wdom(H)

اثبات:

D را dominating set با کمترین وزن برای H فرض کنید. آنگاه مجموعه ای از ستاره های مجزا در H وجود دارد که راسهای آن رئوس D هستند و همه ی راسها را پوشش می دهند. چون هر کدام از این ستاره ها یک زیرگراف کامل در H^2 خواهند بود، I می تواند حداکثر یک راس از هر کدام بردارد. پس هر راس در I مرکزی از ستاره متناظر را به عنوان همسایه دارد. پس w(S) <=w(D).

در الگوریتم زیر si(u) کم وزن ترین همسایه u در Gi را مشخص می کند و خود u هم می تواند همسایه خودش باشد.

الگوریتم 5.10: k-مرکز متریک وزن دار

1) گرافهای G1^2,...,Gm^2 را بسازید.

2) در هر کدام از Gi^2 ها مجموعه مستقل ماکسیمال Mi را محاسبه کنید.

3) Si را که اجتماع si(u) ها به ازای هر u عضو Mi است حساب کنید.

4) کمترین اندیس i را که w(Si) <= W باشد را پیدا کنید. (j)

5) Sj را برگردان.

قضیه: ضریب تقریب الگوریتم بالا = 3

تمرین های فصل 4

1- نشان دهید الگوریتم 4.3 می تواند به عنوان یک تابع برای پیدا کردن k-برش با ضریب 2-2/k از k-برش کمینه استفاده شود. چند فراخوانی تابع برای این کار لازم است؟

(الگوریتم 4.3: برش چندگانه: برای هر ترمینال (k تا کلا) برش ایزوله کمینه را پیدا می کند و اجتماع k-1 برش سبکتر را بر می گرداند.

برای پیدا کردن برش ایزوله همه ی راسهای دیگر را به صورت یک راس در نظر می گیرد و با شارش بیشینه برش کمینه آن را پیدا می کند.

ضریب تقریب: 2-2/k)

در حالتی که هر کدام از ترمینالها در یک مولفه همبندی بیفتند، این دو مساله یکی می شوند. یک راه این است که همه ی حالت های انتخاب k تا از n تا راس به عنوان ترمینال را انجام بدهیم و یک بار تابع چند برش را صدا کنیم. در این صورت جواب مینیمم با ضریب 2-2/k به دست می آوریم. چون حتما حالتی که جواب هست را هم در نظر گرفته ایم و چند برش این حالت جواب بهینه است، پس ضریب تقریب همان ضریب تقریب چند برش خواهد بود.

2- یک الگوریتم حریصانه معمولی برای محاسبه چندبرش این است: از گراف به ازای هر زوج ترمینالی که در یک مولفه همبندی هستند، برش s-t را به دست بیاوریم و کم وزن ترین آنها را حذف کنیم و این کار را ادامه بدهیم تا همه ی ترمینالها جدا شوند. ثابت کنید این الگوریتم ضریب تقریب 2-2/k دارد.

این مساله برعکس مساله قبلی است. چون کم وزن ترین برش در گراف کم وزن ترین برش در درخت گومری-هو هم هست، پس این کار معادل اجرای الگوریتم 4.7 برای k-برش کمینه است که ضریب تقریب 2-2/k دارد.

* سوالات مربوط به درخت گومری-هو:

3- فرض کنید گراف با یالهای وزندار نامنفی داده شده است. و f(u,v) وزن برش u-v کمینه بین این دو راس در گراف است.

1) اگر f(u,v) <= f(u,w) <=f(v,w) باشد، ثابت کنید f(u,v)=f(u,w).

حل: اگر دو راس را با یک برش از هم جدا کرده باشیم، هر دوی آنها نمی توانند به یک راس دیگر وصل باشند. در اینجا فرض کنید v و u را از هم جدا کرده باشیم، در این صورت حتما یا w-u یا v-w از هم جدا شده اند. پس

f(u,v) >= min(f(u,w),f(v,w)) = f(u,w)

f(u,v) <= f(u,w)

==> f(u,v) = f(u,w)

2) نشان دهید بین C(n,2) مقدار f(u,v) به ازای همه زوج رئوس، حداکثر n-1 مقدار متمایز است.

حل: هر برش رئوس را به دو قسمت ناتهی تقسیم می کند. پس هر بار حداقل یک راس جدا می شود. قسمت آخر هم که خود به خود وقتی بقیه جدا شده باشند جدا خواهد بود. پس حداکثر n-1 مقدار کمترین برش وجود دارد. اگر قسمت هایی که جدا می شوند، بیشتر از یک راس باشند به همین دلیل که راس آخر خود به خود جدا می شود، مقدار کمتر هم خواهد شد.

3) نشان دهید به ازای هر سه راس u و v و w داریم:

f(u,v) >= min( f(u,w), f(w,v) )

حل: به قسمت 1 نگاه کنید.

4) نشان دهید به ازای هر زیرمجموعه از رئوس داریم:

f(u,v) >= min{ f(u,w_1),f(w_1,w_2),...,f(w_r,v) }

(فکر کنم منظورش v بوده ولی توی صورت سوال نوشته بود w)

حل: برای جدا کردن راس u و v باید هیچ مسیری بین آنها نباشد، یعنی باید مسیر بالا هم نباشد، یعنی باید حداقل یک یال از آن حذف شود. پس هزینه ی برش از هزینه ی یال با وزن مینیمم در این مسیر بیشتر مساوی است. (به دلیل وجود مسیرهای دیگر مساوی نیست و بیشتر است.)

4- فرض کنید T درختی باشد که روی مجموعه رئوس V ساخته شده و روی یالها آن تابع وزن W' وجود دارد. می گوییم T یک درخت معادل شارش! (flow equivalent tree) است اگر در شرط اول از دو شرط درخت گومری-هو صدق کند؛ یعنی برای هر زوج رئوس u,v عضو V وزن برش u-v کمینه در G برابر وزن آن در T باشد. فرض کنید K گراف کامل روی V باشد. وزن هر یال K را f(u,v) تعریف کنید (وزن برش کمینه u-v). نشان دهید هر درخت پوشای با بیشترین وزن روی K یک درخت معادل شارش برای G است.

راهنمایی: برای هر u,v عضو V، قرار دهید u,w1,..,wr,v مسیر یکتا از u به v در T باشد. طبق 4.1 و این حقیقت که چون T یک درخت پوشای با ماکسیمم وزن است داریم:

f(u,v) <= min{ f(u,w1),..,f(wr,v)}

(4.1 = قسمت آخر سوال قبل!)

حل:

برای روشن شدن صورت سوال، مثلا گراف سه راسی را در نظر بگیرید که یالهاش این وزن ها را دارند:

G

(1,2): 1

(1,3): 2

(2,3): 4

----------

K

(1,2): 1

(1,3): 2

(2,3): 3

---------

T

(1,3): 2

(2,3): 3

برش کمینه بین 1 و 2 وزن 3 دارد.

وقتی یک درخت پوشا می سازیم، یعنی همه ی راسها به هم مسیر دارند و وقتی یک برش داریم می خواهیم هیچ دو راسی به هم مسیر نداشته باشند. پس باید بتوانیم همه ی آنها را جدا کنیم که این یعنی ماکسیمم بین برشهای مینیمم = ماکسیمم بین یالهای مسیرهای بین دو راس = یال درخت پوشای بیشینه.

به صورت ریاضی؛ باید نامساوی را برای همه ی مسیرهای ممکن بنویسیم و برای اینکه در همه صدق کند باید ماکسیمم مقادیر سمت چپ را بگیریم که همان وزن یال درخت پوشای بیشینه است.

5- فرض کنید (A, A') یک برش s-t مینیمم باشد که s در A است. x و y را هر دو راسی از A فرض کنید. گراف G' را با تبدیل همه ی راسهای A' به یک راس به نام v_A' بسازید. وزن هر یال (a,v_A') به اندازه ی مجموع وزن یالهای (a,b) است که b در A' است. بدیهی است که هر برشی در G' یک برش در G تعریف می کند. نشان دهید که یک برش x-y مینیمم در G' یک برش x-y مینیمم در G تعریف می کند.

حل:

همه ی راسهای A' به راس t وصل اند، پس برای اینکه x و y را (که در A هستند) از هم جدا کنیم، باید هیچ یالی بین راسهای x و y و مجموعه A' نباشد. چون این یالها مینیمم یالهایی هستند که باید قطع شوند (یک برش s-t بوده است) پس در برش مینیمم بین x و y هم همین یالها از مسیر بین x و y با t باید حذف شوند. پس می توانیم همه ی راسهای A' را به صورت یک ابرراس بگیریم و وزن یالها را هم جمع کنیم.

6- الگوریتم درخت گومری-هو: {پیشنهاد می کنم اول شکل پایین رو ببینید!}

افرازی از رئوس به مجموعه های S1,..,St انجام می دهیم و یک MST روی آنها می سازیم. w' تابعی است که وزن یالهای این درخت را می دهد. درخت ساخته شده T در ویژگی زیر صدق می کند:

ویژگی: به ازای هر یال (Si,Sj) از T، راسهای a و b به ترتیب در Si و Sj وجود دارند که w'(Si,Sj) = f(a,b) باشد (یعنی وزن برش کمینه a-b) و برش تعریف شده توسط یال (Si,Sj) یک برش a-b کمینه در G باشد.

الگوریتم از یک افراز بدیهی از V شروع می کند و n-1 تکرار انجام می دهد. در هر تکرار مجموعه Si در افراز را پیدا می کند که |Si|>2 باشد و افراز را با تقسیم Si و پیدا کردن یک درخت روی افرازی که در ویژگی صدق می کند، تصحیح می کند. به این صورت که x و y را دو راس متمایز Si قرار می دهد. ریشه درخت فعلی را در Si قرار می دهد و زیر درخت های با ریشه های فرزندان Si را در نظر می گیرد. هر زیر درخت به صورت یک ابرراس در می آید و گراف G' به این صورت به دست می آید. (راسهای Si در G' هستند و برای بقیه این ابرراسها ساخته می شوند نه خود Si). یک برش x-y مینیمم در G' پیدا می کنیم. فرض کنید (A,B) افرازی از راسهای G' باشد که این برش را تعریف می کنند که x در A و y در B باشد و w_xy را وزن این برش تعریف می کنیم. اشتراک S_i با A و B را به دست می آوریم و Si_x و Si_y می نامیم.

الگوریتم تقسیم ها و درخت را به روز می کند: افراز را با جایگزین کردن Si با Si_x و Si_y و درخت جدید بین راسهای Si_x و Si_y یال به وزن w_xy دارد. زیر درخت مجاور Si در درخت قبلی را در نظر بگیرید. بدون از دست رفتن عمومیت مساله فرض کنید گره متناظر این زیردرخت در A باشد. در این صورت زیردرخت با یک یال به Si_x وصل است. وزن این یال همان وزن اتصال زیردرخت به Si است. همه ی یالهای این زیردرخت وزنشان را حفظ می کنند.

نشان دهید که این درخت جدید در ویژگی صدق می کند. پس نشان دهید که الگوریتم متوقف می شود (وقتی که افراز شامل راسهای تکی باشد) و یک درخت گومری-هو در گراف پیدا می کند.

مثال: برای درخت زیر اجرای الگوریتم به دست آوردن درخت گومری-هو نشان داده شده است.

حل:

چیزی که سوال می خواهد ثابت کنیم این است که برش کمینه در Si برای دو راس در Si با برش کمینه در گراف مساوی است. پس وقتی Si ها تک عضوی بشوند الگوریتم تمام می شود و همان درخت گومری-هو به دست می آید.

کافی است ثابت کنیم که ترتیب انجام برشها تاثیری روی جواب ندارد. چون هنگام محاسبه ی برش بین دو راس تمام مسیرهای بین این دو راس در نظر گرفته می شوند، پس نمی شود دو راس در این مجموعه باشند که با برش با وزن کمتری بتوان آنها را از هم جدا کرد ولی در الگوریتم هر دو در یک مجموعه بیفتند.

با همین استدلال برای هر دو راسی از گراف می توان گفت که وزن یال بین آنها وزن برش مینیمم s-t بین آنهاست یعنی همان درخت گومری-هو به دست می آید.

7- ثابت کنید اگر درخت گومری-هو برای یک گراف وزندار بدون جهت n-1 وزن متمایز داشته باشد آنگاه گراف فقط یک برش با کمترین وزن دارد.

حل:

هر برش با وزن مینیمم، راسهای گراف را به دو مجموعه افراز می کند که وزن یالهای بین این دو مجموعه مینیمم است.

برهان خلف: فرض کنید که دو تا از این برشها وجود داشته باشد. هر برش کمینه یک برش s-t هم هست (بین راسهای هر کدام از مجموعه های به دست آمده از برش). پس حتما یالی در درخت گومری-هو وجود دارد که وزن آن برابر این برش باشد. چون دو تا از این برشها داریم، پس دو یال با وزن یکسان داریم و این تناقض است. (با فرض مساله)