گراف همیلتونی قویا (Strongly Hamiltonian Graph)، در ریاضیات (Mathematics)

انواع گراف همیلتونی (Hamiltonian Graph) را در آموزش زیر شرح دادیم :

گراف همیلتونی قویا (Strongly Hamiltonian Graph) :

در گراف های جهت دار (Directed Graphs) یا سورگراف ها (Digraphs)، مفهوم همیلتونی بودن تعمیم می یابد. یک گراف جهت دار را قویا همیلتونی می گوییم اگر برای هر جفت راس مانند u و v، یک دور جهت دار همیلتونی وجود داشته باشد که از u شروع شده و به v ختم شود. این مفهوم بسیار قوی تر از همیلتونی بودن ساده در گراف های جهت دار است. در گراف های جهت دار، یک گراف قویا همبند (Strongly Connected) شرط لازم برای همیلتونی بودن است، اما برای قویا همیلتونی بودن، به ساختار منظم تری نیاز است. مسابقات (Tournaments) که گراف های کامل جهت دار هستند، نمونه هایی از گراف هایی هستند که تحت شرایطی می توانند قویا همیلتونی باشند.