گراف کامل وزن دار (Complete Weighted Graph)، در ریاضیات (Mathematics)
انواع گراف کامل (Complete Graph) را در آموزش زیر شرح دادیم :
گراف کامل وزن دار (Complete Weighted Graph) :
در این مدل، هر یال در یک گراف کامل ساده، علاوه بر وجود داشتن، دارای یک وزن (Weight) یا هزینه (Cost) نیز هست. این وزن می تواند نشان دهنده فاصله بین دو شهر، هزینه عبور از یک مسیر، ظرفیت یک خط ارتباطی، یا هر پارامتر عددی دیگری باشد. گراف همچنان کامل است، یعنی یک یال بین هر دو رأس وجود دارد، اما این یال ها دیگر "یکسان" نیستند و با اعدادی مشخص می شوند. نمایش ریاضی آن به صورت
\[ (K_n, w) \]است که در آن
\[ w: E \to \mathbb{R} \]تابع وزن است.
این نوع گراف، پایه و اساس بسیاری از مسائل بهینه سازی ترکیبیاتی (Combinatorial Optimization) است. مشهورترین این مسائل، مسئله فروشنده دوره گرد (Traveling Salesman Problem - TSP) است که به دنبال یافتن کوتاه ترین مسیری می گردد که از همه شهرها (رئوس) دقیقا یک بار عبور کرده و به شهر مبدأ بازگردد (یک دور همیلتونی با کمترین وزن). مسائل دیگری مانند درخت پوشای کمینه (Minimum Spanning Tree) نیز بر روی گراف های کامل وزندار تعریف و بررسی می شوند.
\[ \text{هزینه مسیر} = \sum_{e \in \text{مسیر}} w(e) \]گراف های کامل وزندار کاربردهای فراوانی در علوم کامپیوتر، شبکه های ارتباطی، لجستیک، طراحی مدارهای مجتمع و زیست شناسی محاسباتی دارند.
