ترسیم گراف داخل چند ضلعیهای محدب با استفاده از الگوریتم ژنتیک

گراف ساختار معروفی است که کاربردهای فراوانی از جمله در مهندسی نرم افزار ، پایگاه داده و واسطه های گرافیکی کاربر (GUI) دارد. ترسیم گراف، با نمایش هندسی گراف ها درک آنها را آسان می کند. اغلب الگوریتم های ترسیم گراف موجود، گراف را روی یک سطح نامحدود ترسیم می کنند و سعی می نمایند که مساحت ترسیم را کمینه کنند. کاربردهایی وجود دارد که در آن لازم یا مطلوب است گراف ها روی یک سطح با اندازه و شکل از پیش تعیین شده ترسیم شوند. در این مقاله، ما برای اولین روی مساله ترسیم گراف بر سطوح دو بعدی با اندازه و شکل مشخص تحقیق می نماییم. چون این یک مساله NP-complete می باشد، برای حل آن باید از روش های ابتکاری حل مسائل بهینه سازی استفاده کنیم. بدین جهت در این مقاله متدهایی ابتکاری مبتنی بر الگوریتم ژنتیک برای ترسیم گراف روی سطوح دو بعدی محصور شده با چند ضلعی های ساده محدب ارائه می کنیم و نشان خواهیم داد که الگوریتم ژنتیک هدایت شده نسبت به متد شبیه سازی سرد شدن فلزات مذاب، روشی موثرتر و سریع تر جهت حصول ترسیمات زیبا می باشد.

Keywords:

ترسیم گراف , چند ضلعی ساده , الگوریتم ژنتیک , متد شبیه سازی سرد شدن فلزات مذاب