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

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

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

گراف همیلتونی بیشینه، گرافی همیلتونی با n راس است که با افزودن هر یال جدید بین دو راس غیرمجاور، تعداد دورهای همیلتونی آن افزایش می یابد. به عبارت دیگر، این گراف ها در حالت مرزی قرار دارند به طوری که اضافه کردن هر یال جدید، مستقیما بر تعداد دورهای همیلتونی می افزاید. این مفهوم به حساسیت ساختار گراف نسبت به دورهای همیلتونی اشاره دارد. در طراحی شبکه های ارتباطی، گاهی اوقات می خواهیم شبکه تا حد ممکن پایدار باشد و افزودن یک اتصال جدید، تعداد مسیرهای دوری (چرخه های همیلتونی) را افزایش دهد که نشانه خوبی برای مقاوم سازی شبکه است.