گراف همیلتونی مسطح (Planar Hamiltonian Graph)، در ریاضیات (Mathematics)

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

گراف همیلتونی مسطح (Planar Hamiltonian Graph) :

گراف همیلتونی مسطح، گرافی است که هم خاصیت همیلتونی و هم خاصیت مسطح بودن (Planarity) را داشته باشد. یک گراف مسطح، گرافی است که می توان آن را روی صفحه (Page) بدون هیچ یال متقاطع (Crossing) رسم کرد. قضیه معروفی از "ویلیام توماس تات" (William Thomas Tutte) وجود دارد که می گوید هر گراف مسطح ۳-همبند (3-connected Planar Graph) یک دور همیلتونی دارد (هرچند این قضیه برای همه موارد اثبات شد، اما مثال نقضی برای آن پیدا شد که نشان داد همیشه هم درست نیست). شناخته شده ترین مثال، گراف های چندوجهی (Polyhedral Graphs) هستند که مربوط به اجسام افلاطونی (Platonic Solids) می باشند. برای مثال، گراف مکعب (Cube Graph) و گراف هشت وجهی (Octahedron Graph) هر دو همیلتونی و مسطح هستند.