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

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

Keywords:

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