Il problema del matching massimo

Let G = (V,E) be an undirected graph. A matching of G is defined as a subset M ⊆ E of edges without extremes in common. In the present study the problem of the maximum matching, or better of the maximum cardinality matching, is discussed starting from the particular case on bipartite graphs, which corresponds to the so-called assignment problem, to continue and conclude with its resolution in the more general case on a non-bipartite graph. The assignment problem (easier to solve) was analyzed and solved by the american mathematician Harold William Kuhn, who elaborated also a particular polynomial algorithm, called "Hungarian algorithm", which manage to solve a variant of the above problem, known as the "weighted assignment problem". On the other hand, the development of an efficient algorithm to solve the more general problem of maximum matching, on a given undirected graph, came only later thanks to the fundamental work of the mathematician Jack Edmonds. In conclusion, this in-depth study is justified by the fact that, within combinatorial optimization problems, the maximum matching problem is certainly one of the most fascinating, moreover, given the efficiency of its solving algorithms, it is natural that this problem is then often invoked in the construction of subsequent algorithms for more difficult problems to solve.

Sia G = (V,E) un grafo non orientato. Si definisce un matching di G come un sottoinsieme M ⊆ E di archi senza estremi in comune. Nel presente studio viene discusso il problema del matching massimo, o meglio del matching di cardinalità massima, a cominciare dal caso particolare su grafi bipartiti, che corrisponde al così detto problema dell’assegnamento, per continuare e concludere con la sua risoluzione nel caso più generale su grafo non bipartito. Il problema dell’assegnamento (di più facile risoluzione) fu analizzato e risolto ad opera del matematico statunitense Harold William Kuhn, il quale elaborò anche un particolare algoritmo polinomiale, denominato “algoritmo ungherese”, capace di risolvere una variante del suddetto problema, nota come il "problema dell'assegnamento pesato". D'altra parte, lo sviluppo di un algoritmo efficiente per risolvere il problema più generale del matching massimo, su un grafo non orientato dato, giunse solo più tardi grazie al fondamentale lavoro del matematico Jack Edmonds. In conclusione, questo studio approfondito è giustificato dal fatto che, all'interno dei problemi di ottimizzazione combinatoria, quello del matching massimo è certamente uno dei più affascinanti, inoltre, data l'efficienza dei suoi algoritmi risolutori, è naturale che tale problema venga poi spesso invocato nella costruzione di successivi algoritmi per problematiche di più difficile risoluzione.