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

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

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

این نوع خاصی از گراف همیلتونی است که دقیقا یک دور همیلتونی در آن وجود دارد. در حالی که اکثر گراف های همیلتونی چندین دور همیلتونی متفاوت دارند، این گراف ها فقط یک دور دارند و هر مسیر بسته دیگری که از تمام رئوس عبور کند، دقیقا همان دور قبلی خواهد بود (با در نظر گرفتن جهت مخالف به عنوان یک دور مشابه). یافتن و اثبات یکتایی دور همیلتونی در یک گراف کار دشواری است. این گراف ها در رمزنگاری و طراحی شبکه های با افزونگی (Redundancy) کم اهمیت دارند، زیرا اگر یک شبکه دقیقا یک مسیر چرخشی برای بازدید از تمام نقاط داشته باشد، آسیب پذیری آن در برابر خرابی ها بیشتر است. مثال معروف آن گراف هرشل (Herschel Graph) است که اگرچه نیمه همیلتونی است، اما بحث در مورد یکتایی دور در گراف های کامل همیلتونی مانند

(مثلث) که تنها یک دور دارد، مصداق پیدا می کند.