گراف های کیوبیک ناهمیلتونی (Non-Hamiltonian Cubic Graph)، در ریاضیات (Mathematics)

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

گراف های کیوبیک ناهمیلتونی (Non-Hamiltonian Cubic Graph) :

این گراف ها با وجود اینکه کیوبیک (۳-منتظم) و گاهی حتی ۳-همبند هستند، هیچ دور همیلتونی ندارند. معروف ترین مثال آن، گراف پترسن (Petersen Graph) است که یک گراف کیوبیک ۳-همبند و غیرمسطح است و همیلتونی نیست. این گراف ها برای نشان دادن محدودیت های قضایای همیلتونی استفاده می شوند. اثبات ناهمیلتونی بودن گراف پترسن اغلب با استفاده از استدلال های رنگ آمیزی (Coloring) یا تطابق (Matching) انجام می شود. وجود این گراف ها نشان می دهد که منظم بودن بالا به تنهایی تضمین کننده همیلتونی بودن نیست.