مروری بر ادبیات تحقیق در مورد پارتیشن بندی گراف می باشد که 47 صفحه می باشد و برای استفاده در پایان نامه بسیار مفید است . 4 – روش های سنتی 4-1 پارتیشن بندی گراف مسئله پارتیشن بندی گراف شامل تقسیم کردن رئوس در گراف های g با اندازه از قبل تعیین شده می باشد به نحوی که تعداد لبه های واقع شونده بین گروه ها حداقلی می باشند . تعداد لبه های اجراء شونده بین خوشه ها را اندازه برش می نامند . راه حل مشکل گراف با رئوس چهارده تایی در شکل 9 برای g=2 و خوشه های اندازه مساوی ارایه می گردد . مشخص کردن تعداد خوشه های پارتیشن ضروری می باشد . در صورتی که هر کسی به راحتی یک پارتیشن را به حداقل اندازه برش تحمیل کرده بود و تعدادی از خوشه ها را آزاد گذاشته بود ، مشکل جزیی بوده و با تمامی رئوس خاتمه یابنده در خوشه یکسان شباهت دارد و همانطور این موضوع به اندازه برش تلاقی منجر خواهد شد . همچنین مشخص کردن اندازه ضروری می باشد همانگونه در غیر اینصورت محتمل ترین راه حل مشکل شامل جدا سازی کمترین راس های درجه از مابقی گراف خواهد بود که تا حدی مورد توجه نمی باشد . این مشکل را می توان از طریق انتخاب ی …
