گراف همیلتونی تصادفی (Random Hamiltonian Graph)، در ریاضیات (Mathematics)
انواع گراف همیلتونی (Hamiltonian Graph) را در آموزش زیر شرح دادیم :
گراف همیلتونی تصادفی (Random Hamiltonian Graph) :
در نظریه گراف های تصادفی (Random Graph Theory)، به گرافی که با احتمال بالایی (معمولا نزدیک به ۱) دارای دور همیلتونی باشد، در ناحیه آستانه (Threshold) همیلتونی، گراف همیلتونی تصادفی می گویند. مدل معروف
\[ G(n, p) \]را در نظر بگیرید که در آن n راس وجود دارد و هر یال با احتمال p به طور مستقل وجود دارد. قضیه ای در این زمینه می گوید که اگر
\[ p \geq \frac{\log n + \log \log n + c_n}{n} \]باشد، آن گاه گراف حاصل تقریبا به طور قطع همیلتونی خواهد بود. این حوزه از ریاضیات به مطالعه رفتار گراف ها در حالت حدی می پردازد و نشان می دهد که همیلتونی بودن یک ویژگی بسیار شایع در گراف های بزرگ با چگالی متوسط به بالاست.
نویسنده علیرضا گلمکانی
شماره کلید 5516
گزینه ها 
نظرات 0 0 0