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

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

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

گراف کیوبیک (Cubic Graph) یا ۳-منتظم (3-regular)، گرافی است که درجه (Degree) تمام رئوس آن برابر ۳ است. یک گراف کیوبیک همیلتونی، گرافی کیوبیک است که دارای دور همیلتونی باشد. قضیه معروفی به نام حدس تات (Tutte's conjecture) وجود داشت که می گفت تمام گراف های کیوبیک ۲-همبند (2-connected) همیلتونی هستند. این حدس بعدا با یافتن یک مثال نقض (گراف کیلر - Keller's graph) رد شد. با این حال، زیرمجموعه هایی از این گراف ها مانند گراف های کیوبیک مسطح ۳-همبند (که به گراف های چندوجهی مکعبی معروفند) همگی همیلتونی هستند. این گراف ها به دلیل کاربرد در شیمی (مطالعه ساختار مولکول ها) و معماری کامپیوتر (شبکه های اتصال) اهمیت دارند.