ترسیم گراف در چند ضلعی حفره دار توسط الگوریتم ژنتیکی
عنوان مقاله: ترسیم گراف در چند ضلعی حفره دار توسط الگوریتم ژنتیکی
شناسه ملی مقاله: DOROUDIT01_094
منتشر شده در همایش منطقه ای علوم کامپیوتر، مهندسی کامپیوتر و فناوری اطلاعات در سال 1391
شناسه ملی مقاله: DOROUDIT01_094
منتشر شده در همایش منطقه ای علوم کامپیوتر، مهندسی کامپیوتر و فناوری اطلاعات در سال 1391
مشخصات نویسندگان مقاله:
ابوالقاسم مهدی نیا اسبویی - دانشکده مهندسی کامپیوتر و فناوری اطلاعات - دانشگاه صنعتی امیرکبیر
علیرضا باقری - دانشکده مهندسی کامپیوتر و فناوری اطلاعات - دانشگاه صنعتی امیرکبیر
خلاصه مقاله:
ابوالقاسم مهدی نیا اسبویی - دانشکده مهندسی کامپیوتر و فناوری اطلاعات - دانشگاه صنعتی امیرکبیر
علیرضا باقری - دانشکده مهندسی کامپیوتر و فناوری اطلاعات - دانشگاه صنعتی امیرکبیر
با توجه به اهمیت زیاد مسئله ترسیم گراف و کاربردهای آن (به عنوان مثال در مهندسی نرمافزار، واسطههای گرافیکی)، این مسئله مورد توجه فراوان واقع شده است و تحقیقات مختلفی بر روی مسئله ترسیم انواع گراف ها صورت گرفته است. از جمله این مقالات، ترسیم گراف در چند ضلعی ها، ترسیم گراف مسطح در درون یک چند ضلعی، ترسیم یک درخت درون چند ضلعی است .یکی از مسائل مربوط به ترسیم گراف همانطورکه در بالا اشاره شد مسئله ترسیم گراف مستتر در درون یک چند ضلعی است که قبلاً الگوریتم برای حل مسئله ارائه شده است. اما در برخی کاربردها نیاز است که گراف مسطح را درون یک چند ضلعی حفره دار ترسیم کنیم . با توجه به این موضوع که ترسیم گراف در چند ضلعی حفره دار تاکنون پیادهسازی نشده است ما در این مقاله دو روش برای این مسئله پیشنهاد کردیم که هر یک از این دو روش مزایا و معایب خاص خود را داراست و در کاربردهای متفاوت میتوان از هر یک از آنها بهره برد. یکی از روشها گراف مسطح را طوری ترسیم میکند که مکان اولیه گرهها تغییر نمییابد و با ایجاد خم ها از برخورد بین یال هاه جلوگیری میکند. ولی در روش دیگر موقعیت گرهها ثابت نیست و الگوریتم با توجه به بیتها و اولویتها مکان گرهها را مشخص میکند. در این روش هیچ خمی به یال ها داده نمیشود.
کلمات کلیدی: کمیته ژنتیک، ترسیم گراف ، چند ضلعی حفره دار
صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/173519/