برش کمینه

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

برش کمینه[ویرایش]

برش کمینه
برش در نظریه گراف بخش کردن گراف به دو بخش ناهمبند است. به سخنی دیگر، برش گره‌های گراف به دو زیرمجموعه جدا از هم بخش می‌شوند.
"مجموعه‌ی برش"، مجموعه‌ای از یال‌هاست که دو سر آن ها، هر یک، در یک بخش است.
یال‌های "گذر" از یک برش همان یال‌های مجموعه‌ی برش‌اند.
هزینه‌ی برش در گراف‌‌های بی‌وزن، شمار یال‌های گذر است و در گراف‌های وزن‌دار، جمع وزن‌های یال‌های گذر.
برش گرافی را با کم‌ترین هزینه برش کمینه نامند. اگر مجموعه‌ی V همه‌ی گره‌های گرافی بی‌وزن و S ‌‌زیرمجموعه‌ای از گره‌ها (S \subseteq V \!) باشد، مجموعهٔ (S \times (V-S)) \cap E \! کم‌ترین شمار یال‌ها را دارد.

الگوریتم[ویرایش]

اگر گرافی را با G(V,E) نمایش دهیم؛ V گره‌ها و E یال‌های گراف را نشان می‌دهند. یک یال را به دو روش می‌نمایانیم. دوتایی xy یالی را نمایش می‌دهد که x \in V و y \in V گره‌های دو سر یال هستند. هم‌چنین e_i \in E یال iام را نشان می‌دهد. برای یافتن برش کمینه، خوارزمیک (الگوریتم) زیر را به کار می‌بریم:

گام نخست آمیختن دو گره‌ی یک یال است: یال میان دو گره x \! و y \! را برداشته و دو گره را بر هم می‌نهیم، به گونه‌ای که دیگر یال‌ها دست نخورده بمانند.
گراف تازه را با G/xy \! نشان می‌دهیم. این کار در یک گراف n \! گره‌ای می‌تواند از پیچیدگی زمانی O(n) \! پیاده‌سازی شود.
  • ملاحظه 2.1: اندازه G/xy \! دست‌کم برابر اندازه‌ی برش در G \! می باشد. چون هر برشی در G/xy \!، برش هم‌ارزی در G \! دارد.
  • ملاحظه 2.2: اگر e_{1}, ... , e_{n-2} \!، دنباله‌ای از یال‌ها در G \! باشد و G/{e_{1}, ... , e_{n-2}} \! دربردارنده‌ی یک یا چند یال باشد، این چند یال، هم‌ارز برش کمینه در G \! می‌باشند.
هدف، پیدا کردن دنباله ای از یال‌های e_{1}, ... , e_{n-2} \!، به گونه‌ای که G/e_{1}, ... , e_{n-2} \! هم‌ارز برش کمینه باشد. پس پرسش این است که بدون شناسایی برش، دنباله‌ای از یال‌ها را پیدا کرد که در برش نباشند؟
  • لم 2.3: اگر گراف G \! با شمار گره‌های n \!، دارای برش کمینه با اندازهٔ k \! باشد، آنگاه داریم \left\vert E(G) \right\vert \geq kn/2 \!.
  • لم 2.4: اگر به صورت تصادفی، یال e \! را از گراف G \! برداریم، با احتمال 2/n \!، این یال در برش کمینه است.
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: MinCutInner\!، با مرتبه O(n^2) \! کار می کند.
  • ملاحظه 2.6: این الگوریتم همواره برشی را به عنوان خروجی می دهد، که لزوماً معادل برش کمینه نیست.
  • لم 2.7: MinCutInner\!، برش کمینه را با احتمال بزرگتر مساوی 2/n(n-1) \! به عنوان خروجی می دهد.
  • تعریف 2.8: تشدید(بی قاعده): فرایند انجام مکرر یک آزمایش، تا وقتی که نتیجهٔ مورد نظر، با احتمال مطلوب اتفاق افتد.
فرض کنید که MinCut\!، الگوریتمی باشد که MinCutInner\! را n(n-1) \! بار انجام می دهد و در آخر برش کمینه را بر می گرداند:
  • لم 2.9: احتمال اینکه MinCut\!، در برگرداندن برش کمینه ناموفق باشد، کوچکتر از 0.14 است.
  • قضیه 2.10: می توان برش کمینه را از مرتبه O(n^4) \! با احتمال درستی ثابتی، محاسبه کرد. همچنین از مرتبه O(n^4logn) \!، برش کمینه با احتمال بهتری قابل محاسبه است.
با توجه به این که الگوریتم بسیار ساده است، آیا می توان طوری ایدهٔ اصلی مسئله را فشرده سازیم که به الگوریتم سریع تری برسیم؟ (یا به بیان دیگر، آیا می توان با پیچیده کردن الگوریتم، سرعت آن را افزایش داد؟)
چرا الگوریتم نیاز به زمان اجرای بالایی دارد؟ دلیل این است که احتمال وقوع خطا، زمانی که گراف کوچک تر می شود، به سرعت بالا می رود. احتمال موفقیت در ادغام گراف زمانی که دارای t \! راس می شود، برابر است با: t(n-1)/n(n-1) \!.
بنابراین هر چقدر t \! بزرگتر باشد، (یعنی t \geq n/c \! که c \! عدد حقیقی ثابتی باشد) احتمال این که برش با مشکل مواجه شود، کمتر می شود.
  • ملاحظه 2.11: هر چقدر گراف کوچکتر شود، احتمال این که انتخاب اشتباهی صورت گیرد افزایش می یابد.
  • ملاحظه 2.12 این الگوریتم را وقتی گراف کوچک تر می‌شود اجرا می کنیم:
Contract(G,t)

  while |V(G)|> t do
    Pick a random edge e in G.
    G = G/e

  return G
یعنی contract(G,t)\!، گراف G \! را تا زمانی که فقط به تعداد t \! راس از آن باقی بماند، کوچک می کند.
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: زمان اجرای FastCut(G)\! از مرتبه O(n^2logn) \! است، که n \! تعداد رئوس گراف G \! می باشد.
توجه شود که برای این الگوریتم: T(n) = O(n^2) + 2T(n/\sqrt{2}) \!.
  • تمرین 2.14: به عنوان تمرین نشان دهید که استفاده FastCut \! از حافظه، از مرتبه O(n^2)\! است.
  • لم 2.15: احتمال اینکه contract(G,t) \! به برش کمینه منجر شود، حداقل 0.5 است.
  • قضیه 2.16:FastCut \!، برش کمینه را به احتمال بیشتر از \Omega(1/logn) \! می یابد.

صفحات مربوط[ویرایش]

منابع[ویرایش]