تمرین های فصل 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 هم هست (بین راسهای هر کدام از مجموعه های به دست آمده از برش). پس حتما یالی در درخت گومری-هو وجود دارد که وزن آن برابر این برش باشد. چون دو تا از این برشها داریم، پس دو یال با وزن یکسان داریم و این تناقض است. (با فرض مساله)