الگوریتم تطابق بیشینه در گراف دوبخشی

الگوریتم زیر با گرفتن ماتریس مجاورت، یالهای تطابق بیشینه را به دست میدهد .

روش کار الگوریتم بدین صورت است که برای هر رأس در صورتی تا به حال برایش جفتی پیدا نشده باشد یک مسیر M-افزوده از آن رأس پیدا می‌کند، سپس با تعویض یالهای مسیر افزوده اندازه گراف را افزایش میدهد .

 ورودی و خروجی 

e ماتریس مجاورت گراف دوبخشی است. N تعداد رأسهای بخش اول گراف و M تعداد راسهای بخش دوم گراف است.

بعد از پایان الگوریتم آرگومان [match[i جفت رأس i در بخش اول را بدست می‌دهد.

لازم به ذکر است که برنامه زیر تحت استاندارد زبان برنامه نویسی ++C نوشته شده‌است.

 الگوریتم 
bool find (int node) {
 if (mark[node])
 return false;
 mark[node] = true;
 for (int i = 1; i <= m; i++) {
 if (e[node][i] && match2[i] == 0) {
 match2[i] = node;
 match[node] = i;
 mark[node] = false;
 return true;
 }
 }
 for (int i=1; i<=m; i++) {
 if (e[node][i] && find(match2[i])) {
 match[node] = i;
 match2[i] = node;
 mark[node] = false;
 return true;
 }
 }
 mark[node] = false;
 return false;
}

void matching() {
 for (int i = 1; i <= n; i++)
 if (match[i] == 0)
 find(i);
}

 منابع 

 کتاب آشنایی با نظریه گراف اثر دوگلاس بی.وست

رده:الگوریتم‌های گراف
رده:قضیه‌ها در ریاضیات گسسته
رده:قضیه‌ها در نظریه گراف
رده:قضیه‌های ریاضی