1
دانشگاه شاهد، تهران، ایران, دانشکده علوم پایه، دانشگاه شاهد، تهران، ایران
2
دانشکده علوم پایه، دانشگاه شاهد، تهران، ایران
چکیده
مسیر همیلتونی در بسیاری از حوزهها از جمله ریاضیات و صنعت کاربردهای زیادی دارد. مسیر همیلتونی، مسیری در گراف است، به طوری که هر رأس دقیقا یکبار در آن ملاقات میشود. ثابت شده است که مسألهی پیدا کردن مسیر همیلتونی در گرافهای عمومی، انپی-کامل است. همچنین برای گرافهای توری عمومی نیز این مسأله در دستهی مسائل انپی-کامل قرار میگیرد. در این مقاله، این مسأله را برای زیر کلاس خاصی از گرافهای توری، به نام گراف توری L-شکل با یک حفره مستطیلی که اندازه کل گراف فرد است، حل کردهایم و شرایط لازم و همچنین الگوریتم ساخت مسیر را ارائه دادهایم. در نهایت نشان دادهایم که این الگوریتم در زمان خطی مسیر همیلتونی بین دو رأس معین s و t در این گرافها را به دست میآورد.
زالیقهی,مهران و کشاورز کوهجردی,فاطمه . (1401). الگوریتم زمان خطی برای پیدا کردن مسیر همیلتونی در گراف توری L-شکل با یک حفرهی مستطیلی با اندازه فرد. (e170597). علوم رایانش و فناوری اطلاعات, 20(2), e170597
MLA
زالیقهی,مهران , و کشاورز کوهجردی,فاطمه . "الگوریتم زمان خطی برای پیدا کردن مسیر همیلتونی در گراف توری L-شکل با یک حفرهی مستطیلی با اندازه فرد" .e170597 , علوم رایانش و فناوری اطلاعات, 20, 2, 1401, e170597.
HARVARD
زالیقهی مهران, کشاورز کوهجردی فاطمه. (1401). 'الگوریتم زمان خطی برای پیدا کردن مسیر همیلتونی در گراف توری L-شکل با یک حفرهی مستطیلی با اندازه فرد', علوم رایانش و فناوری اطلاعات, 20(2), e170597.
CHICAGO
مهران زالیقهی و فاطمه کشاورز کوهجردی, "الگوریتم زمان خطی برای پیدا کردن مسیر همیلتونی در گراف توری L-شکل با یک حفرهی مستطیلی با اندازه فرد," علوم رایانش و فناوری اطلاعات, 20 2 (1401): e170597,
VANCOUVER
زالیقهی مهران, کشاورز کوهجردی فاطمه. الگوریتم زمان خطی برای پیدا کردن مسیر همیلتونی در گراف توری L-شکل با یک حفرهی مستطیلی با اندازه فرد. علوم رایانش و فناوری اطلاعات, 1401; 20(2): e170597.
علوم رایانش و فناوری اطلاعات