الگوریتمی زمان خطی برای پیدا کردن مسیرهای همیلتونی در گراف‌های توری مستطیلی با یک حفره L-شکل با اندازه فرد

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی کارشناسی ارشد، گروه علوم کامپیوتر، دانشگاه شاهد، تهران، ایران

2 استادیار، گروه علوم کامپیوتر، دانشگاه شاهد، تهران، ایران

چکیده

گراف توری یک زیرگراف رأس القایی محدود از یک گراف توری نامتناهی است که مجموعه رئوس آن تمام نقاط صفحه با مختصات صحیح است و دو رأس از طریق یالی به هم متصل هستند‏، اگر و تنها اگر فاصله اقلیدسی بین آن‌ها یک باشد. مسئله مسیر همیلتونی مشخص می‌کند که آیا یک گراف شامل یک مسیر ساده است که در آن هر رأس از گراف دقیقاً یک‌بار ملاقات شود. این مسئله برای گراف‌های عمومی و همچنین برای گراف‌های توری عمومی یک مسئله ‎‎‏-کامل است. در این مقاله‏، مسئله مسیر همیلتونی بین دو رأس معین ‎‏ و ‎‏ برای گراف‌های توری مستطیلی با یک حفره ‎‎‏-شکل به‌طوری که اندازه کل گراف فرد است را بررسی می‌کنیم. در ابتدا شرایط لازم برای وجود مسیر ‎‏همیلتونی بین دو رأس ‎‏ و ‎‏ را بیان می‌کنیم و در ادامه الگوریتم زمان خطی برای ساخت مسیر همیلتونی را ارائه می‌دهیم. الگوریتم بیان شده در این مقاله به روش تقسیم و غلبه مسئله را حل می‌کند‏، به این صورت که ابتدا‎‎ گراف را به تعدادی زیرگراف افراز می‌کند‏، سپس در هر کدام از زیرگراف‌ها مسیر همیلتونی یا دور همیلتونی را به‌دست می‌آورد و در پایان با ترکیب آن‌ها، مسیر همیلتونی در کل گراف ساخته می‌شود.





 

کلیدواژه‌ها

فایل ها

هم رسانی

ارجاع به این مقاله

آمار