چند برش و k-برش (فصل 4 وزیرانی)

الگوریتم های تقریبی برای تعمیم هایی از مساله برش کمینه بررسی می شوند که np-hard هستند.

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

ترمینالهای s و t را از مجموعه رئوس در نظر بگیرید: افرازی از رئوس را در نظر بگیرید که s در یک مجموعه و t در مجموعه دیگر باشد. برشی که با این افراز تعریف شود یک برش s-t نامیده می شود. مساله پیدا کردن برش با کمترین وزن و برش s-t با کمترین وزن به کمک الگوریتم شارش بیشینه به صورت کارا قابل حل هستند. این دو مساله را تعمیم می دهیم:

مساله چند برش: یک مجموعه ترمینال {S={s_1,...,s_k از رئوس داده شده، یک چند برش مجموعه ای از یالهاست که حذف آنها این ترمینالها را از هم ناهمبند می کند. مساله چندبرش مجموعه یال با کمترین وزن را می خواهد.

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

در این فصل الگوریتم های با ضریب زیر برای این دو مساله ارائه می دهیم:

2-2/k

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

مساله چند برش

یک برش ایزوله برای s_i را مجموعه ای از یالها تعریف می کنیم که حذف آنها s_i را از بقیه ترمینالها جدا می کند.

الگوریتم:

1- برای هر i از 1 تا k، برش ایزوله برای s_i با کمترین وزن را حساب کن (C_i).

2- از بین این برشها سنگین ترین آنها را حذف کن و اجتماع بقیه را برگردان (C).

--------

هر محاسبه در مرحله 1 با تشخیص ترمینالهای S-{s_i} به شکل یک گره و پیدا کردن برش مینیمم با محاسبه ی شارش بیشینه از s_i به گره اجتماع بقیه ترمینالها انجام می شود. بدیهی است حذف C از گراف هر زوج ترمینالی را ناهمبند می کند، پس یک چند برش است. (چون در الگوریتم همه ی راسها به جز یکی را از بقیه جدا کردیم و آن آخری هم چون بقیه از آن جدا هستند از بقیه جداست.)

قضیه: الگوریتم بالا ضریب تقریب زیر را دارد:

2-2/k

اثبات: فرض کنید A چندبرش بهینه باشد. می توانیم A را به صورت اجتماع k تا برش ببینیم: حذف A از گراف k مولفه همبندی ایجاد می کند که هر کدام یک ترمینال دارند (چون A چند برش با کمترین هزینه است، بیش از k مولفه ساخته نمی شود). قرار دهید A_i را به عنوان برشی که مولفه شامل s_i را از بقیه گراف جدا می کند. پس اجتماع A_i ها A می شود.

چون هر یال A مجاور دو مولفه است، هر یال در دو برش A_i ظاهر می شود. پس جمع وزن یالهای A_i ها دو برابر جمع وزن یالهای A است.

بدیهی است A_i یک برش ایزوله برای s_i است. چون C_i یک برش ایزوله با کمترین وزن برای s_i است، پس وزن C_i از وزن A_i کمتر مساوی است. (در الگوریتم این طوری حساب کردیم). توجه کنید که این الگورتیم تا همین جا با گرفتن اجتماع k برش C_i یک الگوریتم تقریبی با ضریب 2 است. در آخر چون C با حذف سنگین ترین برش C_i به دست آمده است، داریم:

w(C) <= (1-1/k) sum_1_k w(C_i) <= (1-1/k) sum_1_k (w(A_i)) = 2(1-1/k)w(A)

(نامساوی اول را می توان از اینجا به دست آورد که میانگین یک سری عدد از ماکسیمم آنها کمتر است). پایان اثبات.

الگوریتم قبل بر اساس شمای کران پایین داده نشده است. در فصل 19 آن را با LP حل می کنیم.

مثال: یک مثال tight برای این الگوریتم: گراف با 2k راس شامل یک دور k راسی و ترمینالهای متمایز متصل شده به هر راس آن. یالهای دور وزن 1 دارند و یالهای متصل به ترمینالها وزن 2-epsilon دارند.

برای هر ترمینال s_i، برش ایزوله با کمترین وزن برای s_i، یال متصل به s_i است. پس جواب الگوریتم (C) وزن (k-1)(2-epsilon) دارد. از طرف دیگر جواب بهینه حذف یالهای دور است که وزن k دارند.

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

مساله k-برش مینیمم

یک الگوریتم معمولی برای k-برش این است: یک برش مینیمم در هر مولفه همبندی حساب کن و کم وزن ترین آنها را حذف کن و این کار را ادامه بده تا k مولفه همبندی بماند. این الگورتیم به ضریب 

2-2/k

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

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

فرض کنید T درختی باشد که روی مجموعه رئوس V ساخته شده؛ یالهای T لازم نیست از E باشند. فرض کنید e یک یال درخت T باشد. حذف آن از درخت دو مولفه همبندی ایجاد می کند. فرض کنید S و S' مجموعه رئوس این مولفه ها باشند. برش در گراف G به صورت افراز (S,S') را برش متناظر یال e تعریف می کنیم. تابع وزن w' را روی یالهای T تعریف کنید. درخت T یک درخت گومری-هو است اگر:

1- برای هر زوج راسهای u و v از V، وزن برش u-v کمینه برابر متناظر آن در T باشد.

2- برای هر یال e از T، وزن w'(e) وزن برش متناظر e در گراف اصلی باشد.

بدیهی است که یک برش u-v مینیمم در T همان کم وزن ترین یال در مسیر بین u و v است (فرض کنید e) و برش متناظر e در G باید u و v را جدا کند.

به صورت شهودی، پیدا کردن یک k-برش کم وزن نیازمند برداشتن برشهای کم وزن است که مولفه های زیادی ایجاد می کنند. توجه کنید که n-1 برش متناظر یالهای T شامل برشهای u-v مینیمم برای هر زوج راس از مجموعه رئوس هستند. (C(n,2)). این حقیقت و لم بعد با هم استفاده از درخت گومری-هو برای پیدا کردن یک k-برش کم وزن را اثبات می کنند.

لم: S را اجتماع برشهای گراف متناظر با L یال T در نظر بگیرید. آنگاه حذف S از گراف یک گراف با حداقل L+1 مولفه ایجاد می کند.

اثبات: حذف L یال مذکور از درخت دقیقا L+1 مولفه می سازد، آنها را V_1 و ... و V_(L+1) بنامید. بدیهی است حذف S از G زوجهای V_i و V_j را ناهمبند می کند. بنابراین ما باید حداقل L+1 مولفه همبندی به دست بیاوریم.

در نتیجه ی لم قبل، اجتماع k-1 برش برداشته شده از T یک k-برش در گراف می سازد. الگوریتم کامل به صورت زیر است:

الگوریتم k-برش:

1- یک درخت گومری-هو T برای گراف G بسازید.

2- اجتماع کم وزن ترین k-1 برش از n-1 برش متناظر یالهای T در گراف را به عنوان خروجی برگردانید. (C)

--------

طبق لم قبل حذف C از G حداقل k مولفه همبندی می سازد. اگر بیش از k مولفه ساخته شد، بعضی از یالهای حذف شده را دوباره برگردانید تا دقیقا k مولفه شود.

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

2-2/k

دارد.

اثبات: فرض کنید A جواب k-برش بهینه گراف باشد. همان طور که در قضیه 4.4 گفته شد، می توانیم A را به صورت اجتماع k برش ببینیم: V_1 و ...و V_k را k مولفه همبندی شکل گرفته با حذف A از G بگیرید و A_i را برشی که V_i را از بقیه جدا می کند. پس A=A_1 U ...UA_k و در نتیجه هر یال A در دو تا از این برشها می افتد.

sum_i_1_k( w(A_i) ) = 2*w(A)

بدون از دست رفتن کلیت مساله فرض کنید A_k سنگین وزن ترین این برشها باشد. ایده ی بقیه اثبات نشان دادن این است که k-1 برش متناظر یالهای T هستند که وزنشان کمتر از وزن برشهای A_1 ,..., A_(k-1) هستند. پس چون الگوریتم k-1 برش سبکتر تعریف شده توسط T را بر می دارد، قضیه درست است.

k-1 برش به صورت زیر مشخص می شوند. B را مجموعه یالهای T بگیرید که V_1 و ... و V_k را متصل می کنند. گراف با رئوس V و یالهای B را در نظر بگیرید و هر یک از مجموعه های V_i را به صورت یک ابرراس در نظر بگیرید. گراف حاصل باید همبند باشد (چون T همبند بوده است).. یالها را تا زمانی که یک درخت باقی بماند حذف کنید. B' زیر مجموعه B را مجموعه یالهای باقیمانده در نظر بگیرید. |B'|=k-1 . یالهای B' برشها (k-1 تا)ی مورد نظر ما را مشخص می کنند.

بعد ریشه درخت را V_k بگذارید (سنگین ترین برش در بین A_iها). این کار به پیدا کردن ارتباط بین یالهای B' و مجموعه های V_1,...,V_(k-1) کمک می کند: هر یال متناظر مجموعه ای است که از آن بیرون می آید. (در درخت ریشه دار).

فرض کنید یال (u,v) از B' متناظر مجموعه V_i باشد. وزن برش u-v مینیمم در گراف، w'(u,v) است. چون A_i یک برش u-v در گراف است:

w(A_i) >= w'(u,v)

پس وزن هر برش بین A_1 و ... و A_(k-1) حداقل به اندازه ی برش تعریف شده در گراف متناظر یال B' است. از این موضوع و این حقیقت که C اجتماع k-1 سبکترین برش تعریف شده توسط T است به دست می آید:

w(C) <= sum_B' (w'(e)) <= sum_i_1_k-1 w(A_i) <= (1-1/k) sum_i_1_k (w(A_i)) = 2(1-1/k)w(A)

مثال tight: برای الگوریتم چندبرش بالا با 2k راس برای این مساله هم مثال خوبی است. (البته نیازی به علامت گذاری راسها به عنوان ترمینال نداریم). در زیر مثالی برای k=4 با درخت گومری-هو متناظر آن می دهیم.

سبکترین k-1 برش در درخت گومری-هو وزن 2-epsilon دارند که متناظر برداشتن یالهای با وزن 2-epsilon از G است. پس k-برش برگردانده شده توسط الگوریتم وزن (k-1)(2-epsilon) دارند. از طرف دیگر جواب بهینه برداشتن یالهای با وزن 1 است که در مجموع k می شود.