پیدا کردن مسیرهای همیلتونی بین دو راس معین در گراف های توری T-شکل با اندازه زوج
سال انتشار: 1401
نوع سند: مقاله ژورنالی
زبان: فارسی
مشاهده: 140
فایل این مقاله در 13 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_JSCIT-11-2_001
تاریخ نمایه سازی: 25 مهر 1403
چکیده مقاله:
یکی از مسایل مشهور در نظریه گراف، مساله مسیر یا دور همیلتونی است. این مساله برای گراف های عمومی و حتی برخی از کلاس های گراف از جمله گراف های توری عمومی NP-کامل است. در این مقاله، مساله پیدا کردن مسیر همیلتونی بین دو راس معین s و t در گرافهای توری T-شکل با اندازه زوج، که حالت خاصی از گراف های توری است، بررسی می شود. این مساله کاربردهای مختلفی از جمله در ربات های جاروکننده و پردازش موازی دارد. در این مقاله، ابتدا شرایط لازم برای اینکه مسیر و دور همیلتونی وجود داشته باشد بیان می شود، سپس یک الگوریتم زمان خطی بر حسب اندازه گراف برای حل مساله مسیر و دور همیلتونی ارائه می شود.
کلیدواژه ها:
نویسندگان
Ryhaneh Forghani-Tehrani
Department of Mathematics & Computer Science, Shahed University, Tehran, Iran
Fatemeh Keshavarz-Kohjerdi
Department of Mathematics & Computer Science, Shahed University, Tehran, Iran
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
