برش کمینه
برش کمینه یکی از پرسمانهای کلیدی در زمینهٔ بهینهسازی شبکه است. برش در اینجا برداشتن شماری از یالهای گرافی همبند است به گونهای که گراف را به دو بخش ناهمبند بِبُرد. اگر برداشتن هر یال هزینهای داشته باشد، برش کمینه به دنبال یافتن زیرمجموعهای از یالهاست که برداشتن این یالها کمترین هزینه را در پی داشته باشد.
برش کمینه
[ویرایش]
- برش در نظریه گراف بخش کردن گراف به دو بخش ناهمبند است. به سخنی دیگر، برش گرههای گراف به دو زیرمجموعه جدا از هم بخش میشوند.
- "مجموعهی برش"، مجموعهای از یالهاست که دو سر آن ها، هر یک، در یک بخش است.
- یالهای "گذر" از یک برش همان یالهای مجموعهی برشاند.
- هزینهی برش در گرافهای بیوزن، شمار یالهای گذر است و در گرافهای وزندار، جمع وزنهای یالهای گذر.
- برش گرافی را با کمترین هزینه برش کمینه نامند. اگر مجموعهی همهی گرههای گرافی بیوزن و زیرمجموعهای از گرهها () باشد، مجموعهٔ کمترین شمار یالها را دارد.
الگوریتم
[ویرایش]اگر گرافی را با نمایش دهیم؛ گرهها و یالهای گراف را نشان میدهند. یک یال را به دو روش مینمایانیم. دوتایی یالی را نمایش میدهد که و گرههای دو سر یال هستند. همچنین یال ام را نشان میدهد. برای یافتن برش کمینه، الگوریتم زیر را به کار میبریم:
- گام نخست آمیختن دو گرهی یک یال است: یال میان دو گره و را برداشته و دو گره را بر هم مینهیم، به گونهای که دیگر یالها دست نخورده بمانند.
- گراف تازه را با نشان میدهیم. این کار در یک گراف گرهای میتواند از پیچیدگی زمانی پیادهسازی شود.
- ملاحظه 2.1: اندازه دستکم برابر اندازهٔ برش در میباشد . چون هر برشی در ، برش همارزی در دارد.
- ملاحظه 2.2: اگر ، دنبالهای از یالها در باشد و دربردارندهٔ یک یا چند یال باشد، این چند یال، همارز برش کمینه در میباشند.
- هدف، پیدا کردن دنباله ای از یالهای ، به گونهای که همارز برش کمینه باشد. پس پرسش این است که بدون شناسایی برش، دنبالهای از یالها را پیدا کرد که در برش نباشند؟
- لم 2.3: اگر گراف با شمار گرههای ، دارای برش کمینه با اندازهٔ باشد، آنگاه داریم .
- لم 2.4: اگر به صورت تصادفی، یال را از گراف برداریم، با احتمال ، این یال در برش کمینه است.
Algorithm MinCutInner(G)
G0 = G
i = 0
while Gi has more than two vertices do
Pick randomly an edge ei from the edges of Gi
Gi 1 = Gi/ei
i = i 1
Let(S,V-S) be the cut in the original graph corresponding to Gi
return (S,V-S)
- ملاحظه 2.5: ، با مرتبه کار میکند.
- ملاحظه 2.6: این الگوریتم همواره برشی را به عنوان خروجی میدهد، که لزوماً معادل برش کمینه نیست.
- لم 2.7: ، برش کمینه را با احتمال بزرگتر مساوی به عنوان خروجی میدهد.
- تعریف 2.8: تشدید(بی قاعده): فرایند انجام مکرر یک آزمایش، تا وقتی که نتیجهٔ مورد نظر، با احتمال مطلوب اتفاق افتد.
- فرض کنید که ، الگوریتمی باشد که را بار انجام می دهد و در آخر برش کمینه را بر می گرداند:
- لم 2.9: احتمال اینکه ، در برگرداندن برش کمینه ناموفق باشد، کوچکتر از 0.14 است.
- قضیه 2.10: میتوان برش کمینه را از مرتبه با احتمال درستی ثابتی، محاسبه کرد. همچنین از مرتبه ، برش کمینه با احتمال بهتری قابل محاسبه است.
- با توجه به این که الگوریتم بسیار ساده است، آیا می توان طوری ایدهٔ اصلی مسئله را فشرده سازیم که به الگوریتم سریع تری برسیم؟ (یا به بیان دیگر، آیا می توان با پیچیده کردن الگوریتم، سرعت آن را افزایش داد؟)
- چرا الگوریتم نیاز به زمان اجرای بالایی دارد؟ دلیل این است که احتمال وقوع خطا، زمانی که گراف کوچک تر می شود، به سرعت بالا می رود. احتمال موفقیت در ادغام گراف زمانی که دارای راس می شود، برابر است با: .
- بنابراین هر چقدر بزرگتر باشد، (یعنی که عدد حقیقی ثابتی باشد) احتمال این که برش با مشکل مواجه شود، کمتر می شود.
- ملاحظه 2.11: هر چقدر گراف کوچکتر شود، احتمال این که انتخاب اشتباهی صورت گیرد افزایش می یابد.
- ملاحظه 2.12 این الگوریتم را وقتی گراف کوچک تر میشود اجرا می کنیم:
Contract(G,t)
while |V(G)|> t do
Pick a random edge e in G.
G = G/e
return G
- یعنی ، گراف را تا زمانی که فقط به تعداد راس از آن باقی بماند، کوچک می کند.
FastCut(G = (V,E))
INPUT: G multigraph
begin
n = |V(G)|
if n<7 then t = n/
compute min-cut of G using brute force and return cut
t = n/2
H1 = Contract(G,t)
H2 = Contract(G,t) // Contract is randomized!!
X1 = FastCut(H1)
X2 = FastCut(H2)
return the smallr cut out of X1 and X2
- لم 2.13: زمان اجرای از مرتبه است، که تعداد رئوس گراف میباشد .
- توجه شود که برای این الگوریتم: .
- تمرین 2.14: به عنوان تمرین نشان دهید که استفاده از حافظه، از مرتبه است.
- لم 2.15: احتمال اینکه به برش کمینه منجر شود، حداقل 0.5 است.
- قضیه 2.16:، برش کمینه را به احتمال بیشتر از می یابد.
صفحات مربوط
[ویرایش]منابع
[ویرایش]- CLRS01 T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press/McGraw-Hill, Cambridge, Mass., 2001.
- MR95 R.Motwani and P.Raghavan. Randdomized Algorithms. Camb ridge University Press, NY, 1995.
- Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning", J. ACM, ACM, 56 (2): 1–37, ISSN 0004-5411
- توماس اچ کورمن, Charles E. Leiserson, Ronald L. Rivest, and کلیفورد استین (2001). مقدمهای بر الگوریتمها, Second Edition. MIT Press and McGraw-Hill. pp. 563, 655, 1043. ISBN 0-262-03293-7.
{{cite book}}: نگهداری یادکرد:نامهای متعدد:فهرست نویسندگان (link) - سایت http://en.wikipedia.org/wiki/Cut_(graph_theory)