برش کمینه

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

مقدمه[ویرایش]

در این مقاله برش کمینه در گراف‌های بی وزن بررسی شده است. جهت آشنایی با اثبات لم‌ها و قضایای مطرح شده، به منابع مراجعه شود.
مسئله برش کمینه، معادل مسئله بیشینه جریان در گراف است. به همین علت اغلب نام این دو مسئله با هم به عنوان قضیه "جریان بیشینه - برش کمینه" به کار برده می شود.

تعریف[ویرایش]

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

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

گام اول ادغام یال است. یعنی یال بین دو راس 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) \! می یابد.

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

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