گراف همیلتونی هیپوهمیلتونی (Hypohamiltonian Graph)، در ریاضیات (Mathematics)

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

گراف همیلتونی هیپوهمیلتونی (Hypohamiltonian Graph) :

یک گراف را هیپوههمیلتونی می گوییم اگر خودش همیلتونی نباشد، اما با حذف هر یک از رئوس آن (یک راس دلخواه)، گراف حاصل همیلتونی شود. به بیان ساده، این گراف ها در آستانه همیلتونی شدن قرار دارند. کوچکترین گراف هیپوههمیلتونی، گراف پترسن (Petersen Graph) معروف است که با ۱۰ راس و ۱۵ یال، همیلتونی نیست اما اگر هر یک از رئوس آن را حذف کنیم، یک گراف همیلتونی به دست می آید. این مفهوم در سال ۱۹۶۰ توسط دانشمندی به نام هرشل معرفی شد. بررسی این گراف ها به درک عمیق تری از شرایط لازم و کافی برای همیلتونی بودن کمک می کند. اثبات همیلتونی نبودن یک گراف با نشان دادن اینکه گرافی هیپوههمیلتونی است، یکی از روش های مرسوم است.