گراف دوپاره وزن دار (Weighted Bipartite Graph)، در ریاضیات (Mathematics)
انواع گراف وزن دار (Weighted Graph) را در آموزش زیر شرح دادیم :
گراف دوپاره وزن دار :
گراف دوپاره (Bipartite Graph) گرافی است که رئوس آن را می توان به دو مجموعه مجزا مانند
\[ U \]و
\[ V \]تقسیم کرد، به طوری که هر یال تنها یک رأس از مجموعه
\[ U \]را به یک رأس از مجموعه
\[ V \]وصل کند و درون هر مجموعه یالی وجود نداشته باشد. وقتی به این یال ها وزن نسبت دهیم، یک گراف دوپاره وزن دار خواهیم داشت.
کاربرد اصلی این گراف ها در مسائل تخصیص (Assignment Problems) است. برای مثال، فرض کنید
\[ U \]مجموعه کارگران و
\[ V \]مجموعه کارها باشد. وزن هر یال می تواند نشان دهنده مهارت یا سرعت آن کارگر در انجام آن کار خاص باشد.
هدف در مسائل تخصیص، یافتن یک تطابق کامل (Perfect Matching) است به گونه ای که مجموع وزن ها بیشینه (یا کمینه) شود. الگوریتم مجارستانی (Hungarian Algorithm) یکی از روش های مشهور برای حل این مسئله است.
در ریاضیات، این گراف ها در نظریه ماتروئیدها (Matroid Theory) و بهینه سازی ترکیبیاتی (Combinatorial Optimization) جایگاه ویژه ای دارند.
