برش کمینه

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

"مجموعه‌ی برش"، مجموعه‌ای از یال‌هاست که دو سر آن ها، هر یک، در یک بخش است.

یال‌های "گذر" از یک برش همان یال‌های مجموعه‌ی برش‌اند.

هزینه‌ی برش در گراف‌های بی‌وزن، شمار یال‌های گذر است و در گراف‌های وزن‌دار، جمع وزن‌های یال‌های گذر.

برش گرافی را با کم‌ترین هزینه برش کمینه نامند. اگر مجموعه‌ی ${\displaystyle V}$

همه‌ی گره‌های گرافی بی‌وزن و ${\displaystyle S}$

زیرمجموعه‌ای از گره‌ها (${\displaystyle S\subseteq V}$

) باشد، مجموعهٔ ${\displaystyle (S\times (V-S))\cap E}$

کم‌ترین شمار یال‌ها را دارد.

اگر گرافی را با ${\displaystyle G(V,E)}$

گام نخست آمیختن دو گره‌ی یک یال است: یال میان دو گره ${\displaystyle x}$

و ${\displaystyle y}$

را برداشته و دو گره را بر هم می‌نهیم، به گونه‌ای که دیگر یال‌ها دست نخورده بمانند.

گراف تازه را با ${\displaystyle G/xy}$

نشان می‌دهیم. این کار در یک گراف ${\displaystyle n}$

گره‌ای می‌تواند از پیچیدگی زمانی ${\displaystyle O(n)}$

پیاده‌سازی شود.

• ملاحظه 2.1: اندازه ${\displaystyle G/xy}$
  دست‌کم برابر اندازهٔ برش در ${\displaystyle G}$
  می‌باشد . چون هر برشی در ${\displaystyle G/xy}$
  ، برش هم‌ارزی در ${\displaystyle G}$
  دارد.
• ملاحظه 2.2: اگر ${\displaystyle e_1,...,e_{n-2}}$
  ، دنباله‌ای از یال‌ها در ${\displaystyle G}$
  باشد و ${\displaystyle G/e_1,...,e_{n-2}}$
  دربردارندهٔ یک یا چند یال باشد، این چند یال، هم‌ارز برش کمینه در ${\displaystyle G}$
  می‌باشند.

هدف، پیدا کردن دنباله ای از یال‌های ${\displaystyle e_1,...,e_{n-2}}$

، به گونه‌ای که ${\displaystyle G/e_1,...,e_{n-2}}$

هم‌ارز برش کمینه باشد. پس پرسش این است که بدون شناسایی برش، دنباله‌ای از یال‌ها را پیدا کرد که در برش نباشند؟

• لم 2.3: اگر گراف ${\displaystyle G}$
  با شمار گره‌های ${\displaystyle n}$
  ، دارای برش کمینه با اندازهٔ ${\displaystyle k}$
  باشد، آنگاه داریم ${\displaystyle \left|E(G)\right|\ge kn/2}$
  .
• لم 2.4: اگر به صورت تصادفی، یال ${\displaystyle e}$
  را از گراف ${\displaystyle G}$
  برداریم، با احتمال ${\displaystyle 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: ${\displaystyle MinCutInner}$
  ، با مرتبه ${\displaystyle O(n^2)}$
  کار می‌کند.
• ملاحظه 2.6: این الگوریتم همواره برشی را به عنوان خروجی می‌دهد، که لزوماً معادل برش کمینه نیست.
• لم 2.7: ${\displaystyle MinCutInner}$
  ، برش کمینه را با احتمال بزرگتر مساوی ${\displaystyle 2/n(n-1)}$
  به عنوان خروجی می‌دهد.
• تعریف 2.8: تشدید(بی قاعده): فرایند انجام مکرر یک آزمایش، تا وقتی که نتیجهٔ مورد نظر، با احتمال مطلوب اتفاق افتد.

فرض کنید که ${\displaystyle MinCut}$

، الگوریتمی باشد که ${\displaystyle MinCutInner}$

را ${\displaystyle n(n-1)}$

بار انجام می دهد و در آخر برش کمینه را بر می گرداند:

• لم 2.9: احتمال اینکه ${\displaystyle MinCut}$
  ، در برگرداندن برش کمینه ناموفق باشد، کوچکتر از 0.14 است.
• قضیه 2.10: می‌توان برش کمینه را از مرتبه ${\displaystyle O(n^4)}$
  با احتمال درستی ثابتی، محاسبه کرد. همچنین از مرتبه ${\displaystyle O(n^{4}logn)}$
  ، برش کمینه با احتمال بهتری قابل محاسبه است.

با توجه به این که الگوریتم بسیار ساده است، آیا می توان طوری ایدهٔ اصلی مسئله را فشرده سازیم که به الگوریتم سریع تری برسیم؟ (یا به بیان دیگر، آیا می توان با پیچیده کردن الگوریتم، سرعت آن را افزایش داد؟)

چرا الگوریتم نیاز به زمان اجرای بالایی دارد؟ دلیل این است که احتمال وقوع خطا، زمانی که گراف کوچک تر می شود، به سرعت بالا می رود. احتمال موفقیت در ادغام گراف زمانی که دارای ${\displaystyle t}$

راس می شود، برابر است با: ${\displaystyle t(n-1)/n(n-1)}$

.

بنابراین هر چقدر ${\displaystyle t}$

بزرگتر باشد، (یعنی ${\displaystyle t\ge n/c}$

که ${\displaystyle 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

یعنی ${\displaystyle contract(G,t)}$

، گراف ${\displaystyle G}$

را تا زمانی که فقط به تعداد ${\displaystyle 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: زمان اجرای ${\displaystyle FastCut(G)}$
  از مرتبه ${\displaystyle O(n^{2}logn)}$
  است، که ${\displaystyle n}$
  تعداد رئوس گراف ${\displaystyle G}$
  می‌باشد .

توجه شود که برای این الگوریتم: ${\displaystyle T(n)=O(n^2)+2T(n/\sqrt{2})}$

.

• تمرین 2.14: به عنوان تمرین نشان دهید که استفاده ${\displaystyle FastCut}$
  از حافظه، از مرتبه ${\displaystyle O(n^2)}$
  است.
• لم 2.15: احتمال اینکه ${\displaystyle contract(G,t)}$
  به برش کمینه منجر شود، حداقل 0.5 است.
• قضیه 2.16:${\displaystyle FastCut}$
  ، برش کمینه را به احتمال بیشتر از ${\displaystyle \mathrm{\Omega }(1/logn)}$
  می یابد.

• برش بیشینه

• 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.
• سایت http://en.wikipedia.org/wiki/Cut_(graph_theory)