مروری نظام مند بر بهینه سازی افراز بر روی گراف

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

Keywords:

حل مسیله بخش بندی گراف , الگوریتم های اکتشافی , الگوریتم های فرا ابتکاری , الگوریتم های هندسی , ابزارهای بخش بندی گراف