برش بیشینه

تعریف

A maximum cut.

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

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

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

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

برش بیشینه در یک گراف، برشی است که اندازه آن از تمام برش‌های ممکن در گراف بزرگتر است.

بیان ساده برش بیشینه: برشی که تعداد یال‌های عبور آن بیشینه باشد.

نمونه پیشرفته این مسئله، برش بیشینه وزن دار نامیده می شود. در این مورد، به هر یال یک عدد نسبت داده می‌شود (وزن یال) و هدف، یافتن برشی است که وزن یال‌های عبوری آن بیشینه باشد. توجه شود که وزن یال‌ها در این مساله باید مثبت باشد، چون مقادیر منفی حاصل جمع را تضعیف می کنند.

پیچیدگی الگوریتم

به دلیل اینکه مسئله برش بیشینه ان‌پی کامل است، هیچ الگوریتمی از مرتبه چند جمله ای برای برش بیشینه شناخته نشده است. این در حالی است که این مرتبه برای یافتن برش بیشینه در گراف‌های سطحی موجود است.

الگوریتم‌های تخمین

"الگوریتم تخمین (0.5)" تصادفی و ساده ای بری این مسئله وجود دارد: برای هر راس یک سکه در نظر می گیریم تا تصمیم بگیریم که به کدام قسمت آن را اختصاص دهیم. انتظار داریم، نیمی از یال ها، یال‌های برش باشند. این الگوریتم می تواند مجددا به صورت تصادفی با تابع احتمال شرطی بیان شود؛ بدین منظور، "الگوریتم تخمین (0.5)" ساده و معینی وجود دارد:

گراف $G = (V,E) \!$ داده شده است. با تقسیم دلخواه از $V \!$ شروع کنید ودر صورت پیشرفت روند حل مسئله،َ یک راس را از یک طرف به طرف دیگر جابجا کنید. تا وقتی که چنین راسی موجود نباشد، این کار را ادامه دهید. این الگوریتم، برش را با حداقل یک عمل در هر گام، جلو می برد، پس تعداد تکرار این عمل، از مرتبه یا پیچیدگی زمانی $O(|E|) \!$ است. وقتی که الگوریتم متوقف می شود، حداقل نیمی از یال‌های هر راس $v \!$، در برش قرار دارد. (در غیر این صورت، برای پیشرفت در حل مسئله باید راس $v \!$ را به زیر مجموعه دیگر، منتقل کنیم.) بنابراین، اندازه برش حداقل $0.5|E| \!$ است.

بهترین الگوریتم برش بیشینه شناخته شده، "الگوریتم تخمین(0.878)" می‌باشد که توسط ژئومنز و ویلیامسون ارائه شده است. گفتنی است که این بهترین تخمین ممکن برای برش بیشینه است.

بزرگترین زیر گراف دوبخشی

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

فرض کنید $G = (V,E) \!$ گراف اصلی و $H = (V,X) \!$ زیر گرافی دوبخشی از $G \!$ است. پس بخش $(S,T) \!$ از $V \!$ وجود دارد که هر یال در $X \!$ یک انتها در $S \!$ و یک انتها در $T \!$ داشته باشد. وگرنه، برشی در $H \!$ وجود دارد که "مجموعه-برش" شامل یال‌های $X \!$ می باشد. بنابراین، برشی در $G \!$ وجود دارد که $X \!$، زیر مجموعه "مجموعه-برش" $G \!$ می باشد.

به طور خلاصه، اگر زیر گراف دو بخشی با $k \!$ یال وجود داشته باشد، برشی با حداقل $k \!$ "یال عبوری" وجود دارد؛ و اگر برشی با $k \!$ یال عبوری وجود داشته باشد، یک زیر گراف دو بخشی با $k \!$ یال موجود می باشد. پس مسئله پیدا کردن زیر گراف دو بخشی بیشینه، معادل مسئله پیدا کردن برش بیشینه است.

صفحات مربوط

• برش کمینه

منابع

• Trevisan, Luca; Sorkin, Gregory; Sudan, Madhu; Williamson, David (2000), "Gadgets, Approximation, and Linear Programming", Proceedings of the 37th IEEE Symposium on Foundations of Computer Science: 617–626 .
• Motwani, Rajeev; Raghavan, Prabhakar (1995), Randomized Algorithms, Cambridge .
• Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning", J. ACM (ACM) 56 (2): 1–37, ISSN 0004-5411 
• سایت http://en.wikipedia.org/wiki/Cut_%28graph_theory%29:
• سایت http://en.wikipedia.org/wiki/Max_cut