Третата задача от нашия Конкурс е класическа и се нарича съчетание в двуделен граф с максимална цена или още задача за назначенията. През 1946г. G. Birkhoff показва че задачата за назначенията може да се формулира като задача на линейното програмиране. Най-популярният алгоритъм за решаване на общата задача на линейното програмиране е т.н. симплекс метод, който е с експоненциална сложност. Първият ефективен алгоритъм, създаден от  H. W. Kuhn през 1955г. и използва резултат на унгарските математици D. König и E. Egervari (от 1916-1917г. – 15 години преди откриването на техниката на линейното програмиране) и затова е наричан унгарски. През 1976г. Lawler предлага имплементация на унгарския алгоритъм със сложност O(n³) където n е броят на върховете на графа. През 1986 R. Jonker и T. Volgenant предлагат изчислителни подобрения в унгарския алгоритъм (виж http://www.magiclogic.com/assignment.html ), които не променят порядъка на сложността. През 1989 Gabow и Tarjan, а през 1992 Orlin и Ahuja  създават алгоритми, които макар и с малко подобряват порядъка на сложност. В една статия от 1993г. на J. Orlin иY. Lee предлага нов алгоритъм с предполагана средна сложност O(m), където m е броят на ребрата на графа ( http://web.mit.edu/jorlin/www/oldpapersfolder/quickmatch.pdf ).  

Нека S ={1,2,...,|S|}, а на T={1,2,...,|T|}. Нека G(SÈT,E) е двуделен граф, т.е. множеството от ребрата му е разбито на две подмножества S и T такива, че за всяко ребро (i,j) от E е в сила i е от S, а j е от T. Подмножеството от ребра M наричаме съчетание, ако всеки връх на графа е край на не повече от едно ребро от M. Едно от възможните решения на задачата за намиране на съчетание с максимален брой ребра в двуделен граф се основава на понятието алтерниращ път. Нека M е произволно съчетание в графа. Върховете, които са краища на ребра от M наричаме покрити, а тези, които не са краища на ребра от M – свободни. Пътят v_i1, v_i2,…, v_im в двуделен граф наричаме алтерниращ (относно M), ако в него се редуват свободни и покрити върхове. Ако началният и крайният върх на един алтерниращ път са свободни, той се нарича нарастващ. Основната теорема тук гласи, че M е с максимален брой елементи тогава и само тогава, когато не съществува нарастващ алтерниращ път относно M. Действително ако се изхвърлят от M тези ребра, които участват в нарастващ алтерниращ относно M път, а се добавят тези, които участват в пътя, но не са от M, ще се получи ново съчетание M’, което има едно ребро повече от M. Построяването на нарастващи пътища обикновено се извършва с модификация на обхождане в ширина.

Нека сега за всяко ребро (i, j) е зададена  цена c_ij – реално неотрицателно число. Спокойно можем да считаме, че двуделният граф е пълен, т.е. всеки връх от S е свързан с ребро с всеки връх от T (липсващите ребра можем да добавим като им дадем цена 0). Сега задачата за съчетение с максимален брой ребра е тривиална. Интересната задача е да се намери съчетание (то непременно ще е с максимален брой елементи), което има максимална цена, т.е. максимална сума от цените на участващите в него ребра. В нашата задача |S|=|T|=n, което не е от съществено значение.

Една възможност за решаване на задачата за съчетание с максимална цена в двуделен граф е с помощта на дискутираната вече техника потоци в мрежи (вж. например решение на зад.5 от 2000/01). Действително: да добавим един връх за източник и да го свържем с върховете от S, както и един връх за цел и да свържем всеки връх от T с него. На всяко от ребрата да поставим капацитет 1. За цени на ребрата, които добавихме нека поставим числото 0, а на всяко ребро (i, j) на двуделния граф – числото M + 1 – c_ij, където M е максималната цена на ребро от графа. В получената по този начин мрежа трябва да решим задача за намиране на максимален поток с минимална цена, която разбира се е малко по-трудна от задачата, коментирана в цитирания по-горе брой на списанието. Сложността на такъв алгоритъм ще бъде с O(n³).

Задачата за съчетание с максимална цена може да бъде формулирана и като следната задача на линейното програмиране: да се намерят такива стойности на променливите x_ij, 0£x_ij£1, S_iÎS x_ij=1, S_jÎT x_ij=1, i=1,2,…,n, j=1,2,…,n, че сумата S_iÎS S_jÎT c_ij.x_ij да е максимална.  Не е трудно да се види, че решението на тази задача винаги е целочислено и x_ij=1 тогава и само тогава, когато реброто (i, j) участва в съчетание с максимална цена.

Споменатият по-горе алгоритъм на Кун, известен още като унгарски алгоритъм, е сложна смес от техниката на алтерниращите пътища и линейното програмиране. Като използва спецификата на конкретната задача той я решава със сложност O(n³). Традиционно за линейното програмиране е да се обърне дадената задача в така наречената дуална, която в случая е следната: на всеки връх i от S да съпоставим променлива u_i, a на всеки връх j от T - променлива v_j. Дуалната задача е да се  намерят такива стойности на променливите u_i и v_j, 0£u_i,v_j и c_ij£u_i+v_j за всяко i от S и за всяко j от T така, че Su_i+Sv_j да е минимална. Не е никак лесно да се види връзката между двете задачи, но тя се дава от следните три условия:

а) ако x_ij=1, то u_i+v_j= c_ij;

б) ако u_i > 0, то S_jÎT x_ij=1;

в) ако v_j > 0, то S_iÎS x_ij=1.

Идеята на унтарския алгоритъм е да се започне с някакви стойности на променливите  u_i и v_j, за които са изпълнени условията а) и в) и да се поддържат тези условия изпълнени през цялото време на работата, като постепенно се намалява броя на неизпълнените условия б), с използване на техниката на нарастващите алтерниращи пътища. Тъй като в този случай ребрата имат цени, за нарастване на пътищата се използва модификаця на алгоритъма на Дейкстра, вместо обхождане в ширина. (по начина който споменахме по-горе задачата се обръща предварително от задача за максимум в задача за минимум тъй като ще се използва алгоритъма на Дейкстра).