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

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

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

گراف های وتری (Chordal Graphs) گراف هایی هستند که هیچ القاء شده ای (Induced Cycle) به طول چهار یا بیشتر ندارند (یعنی هر دور به طول حداقل چهار، حداقل یک یال وتر (Chord) دارد). یک گراف همیلتونی وتری، گرافی است که هم خاصیت وتری بودن و هم خاصیت همیلتونی بودن را دارا باشد. ویژگی جالب این گراف ها این است که ساختار خاص آنها اغلب یافتن دور همیلتونی را نسبت به گراف های همیلتونی عمومی آسان تر می کند. این گراف ها معمولا در مسائل مربوط به درخت ها (Trees) و جنگل ها (Forests) که حالت خاصی از گراف های وتری هستند، دیده می شوند. دور همیلتونی در این گراف ها می تواند با استفاده از روش های بهینه سازی مبتنی بر حذف رئوس (Vertex Elimination Orders) پیدا شود. مطالعه این گراف ها به دلیل ساختار جبری منظم ترشان در نظریه گراف های الگوریتمی اهمیت ویژه ای دارد.