Il problema del matching massimo su grafo: un approccio algebrico

In questo breve testo si vogliono trattare alcuni problemi relativi alla teoria dei matching in grafi finiti; in particolare affronteremo il problema del matching massimo. Il nostro intento è di discutere alcuni risultati "classici" della teoria dei matching con tecniche algebriche, invece delle tecniche combinatorie, che sono quelle spesso trattate nei corsi di base.

Nel Capitolo 1 verranno enunciate le definizioni di base ed alcune proprietà preliminari. Elencheremo anche i più importanti teoremi ed algoritmi della teoria "classica" dei matching, la cui discussione verrà rimandata ai capitoli successivi.
Ora, ad ogni grafo si possono associare delle matrici. Una domanda che sorge spontanea è se ci sia qualche relazione tra i matching di un grafo e le matrici a lui associate. La risposta a questa domanda è affermativa e sarà oggetto del Capitolo 2. Mostreremo, infatti, che la cardinalità di un massimo matching per un grafo G è legata al rango di un’opportuna matrice. Nella trattazione di questo capitolo, come pure nei successivi, per la trattazione dei vari argomenti ci restringeremo prima al caso bipartito, per poi estenderci al caso generale.
A questo punto, nel Capitolo 3, ci chiediamo se è possibile fare una stima sulla cardinalità di un matching massimo; dimostreremo quindi il Teorema di König e la Formula di Tutte-Berge. In più, vorremmo capire se in un dato grafo ci sia un matching che saturi tutti i nodi. A questa domanda rispondono il Teorema di Hall, per i grafi bipartiti, ed il Teorema di Tutte, per un qualsiasi grafo.
Nel Capitolo 4, enunceremo degli algoritmi che determinino un matching massimo.
L’idea di fondo è quella di definire un pre-ordine sul rango delle matrici e, sfruttando la stretta connessione tra matrici e grafi, "scalare" le classi di questo pre-ordine per ottenere il risultato cercato. Dimostreremo che tale algoritmo ha complessità polinomiale sul numero di nodi del grafo e termina in un tempo finito. Inoltre, al termine del capitolo, daremo un breve sguardo, anche, a degli algoritmi randomizzati, più veloci di quelli deterministici, che restituiscono con alta probabilità la taglia di un matching massimo.
In fine, nel Capitolo 5, enunceremo dei risultati strutturali riguardanti i matching massimi di un grafo, tra i quali, il più importante è il Teorema strutturale di Edmonds-Gallai.