برش کمینه

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