سمیه امیری - دانشجوی کارشناسی ارشد مهندسی کامپیوتر، واحد علوم و تحقیقات کرمانشاه، دانشگاه آزاد اسلامی، کرمانشاه، ایران / دانشجوی مهندسی کامپیوتر، واحد کرمانشاه، دانشگاه آزاد اسلامی، کرمانشاه، ایران
علی حنانی - عضو هیات علمی، گروه مهندسی کامپیوتر، مرکز سنقر کلیایی، دانشگاه آزاد اسلامی، سنقر کلیایی، کرمانشاه، ایران/گروه مهندسی کامپیوتر، واحد کرمانشاه، دانشگاه آزاد اسلامی، کرمانشاه، ایران

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

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