مقدمه

در حوزه ­ی بهینه ­سازی ترکیباتی با مسائل بسیار مهم و کاربردی آشنا می­ شویم که هر یک با توجه به درجه­ ی سختی، در رده ­ی خاصی از مسائل قرار می ­گیرند. از جمله ­ی این مسائل، مساله­ ی افراز بندی در گراف است که جزو مسائل سخت است و به طور خاص در رده­ ی مسائل NP-Complete قرار داده می­ شود و در حالت کلی الگوریتم حلی وجود ندارد که بتواند این مساله را در زمان چندجمله ­ای حل نماید.

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

در حالت کلی یک مساله ­ی افرازبندی در گراف به این صورت است؛ فرض کنید گراف داده شده باشد. هدف تقسیم کردن راس­ های به زیرمجموعه ­ی جدا از هم، با اندازه­ های مساوی است، به طوری که تعداد یال­ های عبوری بین هر مجموعه ­ی جدا از هم، کمترین باشد. در شکل نمونه­ هایی از افرازبندی گراف نشان داده شده است. با توجه به اهیمت مساله ­ی افرازبندی گراف، طبیعتا روش­ها و رویکردهای گسترده­ای برای حل و برخورد با آن وجود دارد. این روش ­ها، گستره­ای از الگوریتم­ های ساده­ای همچون الگوریتم جستجوی عرضی تا روش­های پیچیده­ای همچون بهینه ­سازی ترکیبی را شامل می­ شوند. در این گزارش قصد داریم تا ضمن ارائه­ ی تعریفی دقیق از مساله ­ی افرازبندی گراف و بیان تاریخچه و کاربردهای آن به بررسی برخی از الگوریتم ­های حل این مساله بپردازیم و یک روش حل فراابتکاری را برای حل مساله پیاده­ سازی نماییم.