جلسه دفاع از رساله دکتری-فاطمه کشاورز کوهجردی

 

ارائه الگوریتم‌هایی برای مسایل مسیر همیلتونی و طولانی‌ترین مسیر در گراف‌های توری

 

مسأله‌ی مسیر همیلتونی، ﯾﻌنی ﭘﯿﺪاﮐﺮدن ﻣﺴﯿﺮی در ﮔﺮاف از رأس ﺷﺮوع ﺑﻪ رأس ﭘﺎﯾﺎن ﺑﻪ ﻃﻮری ﮐﻪ ﻫﺮ رأس دﻗﯿﻘﺎً یک‌بار ﭘﯿﻤﻮده ﺷﻮد، یکی از ﻣﺴﺎﯾﻞ ﻣﺸﻬﻮر در ﻧﻈﺮﯾﻪ ﮔﺮاف اﺳﺖ و ﮐﺎرﺑﺮدﻫﺎی زﯾﺎدی در شبکه‌های کامپیوتری و پردازش تصویر دارد. اﯾﻦﻣﺴﺄﻟﻪ ﺑﺮای ﮔﺮافﻫﺎی ﻋﻤﻮمی یک مسأله ان‌پی-کامل اﺳﺖ و ﻫﻤﭽﻨﯿﻦ ﺑﺮای ﺑﺮخی از ﮐﻼس ﮔﺮافﻫﺎ از ﺟﻤﻠﻪ ﮔﺮافﻫﺎی ﺗﻮری ﻋﻤﻮمی نیز ان‌پی-کامل اﺳﺖ. در اﯾﻦ رﺳﺎﻟﻪ، ﺷﺮاﯾﻂ ﻻزم ﺑﺮای وﺟﻮد ﻣﺴﯿﺮ ﻫﻤﯿﻠﺘﻮنی بین دو رأس ﻣﻌﯿﻦدر ﮔﺮافﻫﺎی ﺗﻮری مستطیلی ﺑﺎ یک ﺣﻔﺮه ﻣﺴﺘطیلی را ﺑﯿﺎن می‌کنیم. ﺑﻪ ﻋﻼوه، ﻧﺸﺎن می‌دهیم ﮐﻪ ﭼگونه ﭼﻨﯿﻦ ﻣﺴﯿﺮی در زﻣﺎن ﺧطی می‌تواند ﺳﺎﺧﺘﻪ ﺷﻮد.

ﺣﺎﻟﺖ ﮐلی‌ﺗﺮ اﯾﻦ ﻣﺴﺄﻟﻪ، ﻣﺴﺄﻟﻪی ﻃﻮﻻنی‌ترین ﻣﺴﯿﺮ، ﯾﻌنی ﻣﺤﺎﺳﺒﻪ ﻣﺴﯿﺮی ﺳﺎده ﺑﺎ ﻃﻮل ﺑﯿﺸﯿﻨﻪ، اﺳﺖ. ﺣتی اﮔﺮ ﮔﺮافی ﻣﺴﯿﺮ ﻫﻤﯿﻠﺘﻮنی ﻧﺪاﺷﺘﻪ ﺑﺎﺷﺪ در ﺑﺮخی از ﮐﺎرﺑﺮدﻫﺎ ﻧﯿﺎز اﺳﺖ ﺗﺎ ﻃﻮﻻنیﺗﺮﯾﻦ ﻣﺴﯿﺮ ﻣﺤﺎﺳﺒﻪ ﺷﻮد. اﯾﻦﻣﺴﺄﻟﻪ ﻧﯿﺰ یکی از مسایل ان‌پی-سخت ﻣﺸﻬﻮر اﺳﺖ و ﮐﺎرﺑﺮدﻫﺎی زﯾﺎدی دارد. دراﯾﻦرﺳﺎﻟﻪ، ﻧﺸﺎن می‌دﻫﯿﻢ ﮐﻪ ﻃﻮﻻنی‌ترین ﻣﺴﯿﺮ در ﮔﺮافﻫﺎی ﺗﻮری ﻣﺴﺘﻄیلی و ﺗﻮری ﻣﺴﺘﻄیلی ﺑﺎ یک ﺣﻔﺮه ﻣﺴﺘﻄیلی در زﻣﺎن ﺧطی می‌تواند ﺳﺎﺧﺘﻪ ﺷﻮد.

ضميمه

ضميمه

ارسال کننده خبر: مهندسي کامپيوتر و فن اوري اطلاعات| | تاريخ: ۱۳۹۶/۰۳/۰۶