گراف کامل وزن دار (Complete Weighted Graph)، در ریاضیات (Mathematics)
انواع گراف وزن دار (Weighted Graph) را در آموزش زیر شرح دادیم :
گراف کامل وزن دار :
گراف کامل (Complete Graph) گرافی است که در آن بین هر دو رأسی، یک یال وجود دارد. اگر به این گراف وزن اضافه کنیم، یک گراف کامل وزن دار به دست می آید. اگر گراف
\[ n \]رأس داشته باشد، تعداد یال ها دقیقا برابر است با:
\[ \frac{n(n-1)}{2} \](در حالت غیرجهت دار).
این نوع گراف در مسائلی کاربرد دارد که همه گزینه ها به نوعی با هم در ارتباط هستند. مشهورترین مسئله در این حوزه، مسئله فروشنده دوره گرد (Travelling Salesman Problem یا TSP) است.
در مسئله TSP، فروشنده باید از یک شهر شروع کند، از تمام شهرهای دیگر دقیقا یک بار دیدن کند و به شهر اول بازگردد. از آنجایی که بین هر دو شهری راهی وجود دارد (گراف کامل)، وزن هر یال نشان دهنده هزینه یا مسافت آن مسیر است. هدف، یافتن چرخشی (Hamiltonian Cycle) با کمترین وزن مجموع است.
با وجود سادگی ظاهری، یافتن جواب بهینه برای تعداد زیاد رئوس در این گراف ها بسیار دشوار است و از دسته مسائل NP-سخت (NP-hard) محسوب می شود.
