Matching su grafi e alcune varianti del problema del matrimonio stabile

Un matching per un grafo G e' un sottoinsieme di archi a due a due non
incidenti, cioe' non aventi estremi in comune. In particolare e' un insieme di coppie distinte di nodi in relazione tra loro, relazione rappresentata dall'arco che li congiunge. Da questo punto di vista e' naturale classificare come problemi di matching tutti quei problemi che richiedono la suddivisione in coppie di elementi legati da qualche relazione, rispettando dei criteri ben determinati. L'obiettivo che ci proponiamo e' di analizzare dettagliatamente uno di questi problemi in particolare, il problema della ricerca di matching stabili per grafi bipartiti. In un problema di questo tipo il criterio seguito per formare le coppie e' la stabilita' rispetto ad una certa relazione che chiameremo
di "preferenza". Per chiarire meglio di cosa si tratta utilizzeremo la
terminologia adottata da Gale e Shapley nel 1962, quando per la prima volta introdussero il problema presentandolo come il problema del matrimonio stabile. Si considera una comunita' di n uomini e n donne ciascuno dei quali stabilisce una lista di preferenza associando ad ogni individuo di sesso opposto al proprio un certo grado di preferenza. Si vogliono formare delle coppie uomo-donna in base a queste informazioni espresse dalla comunita', in modo
tale da costituire un insieme di matrimoni stabili, cioe' tali che non esista un uomo a, sposato con x, ed una donna y, sposata con b, tali che a preferisca y a x e y preferisca a a b, dunque che si preferiscano entrambi ai rispettivi coniugi. Questa chiave di lettura si e' mantenuta nel tempo e tuttora nelle varianti di questo problema si continua a parlare di matrimoni stabili tra uomini e donne per far riferimento a matching stabili su grafi bipartiti.In generale gli elementi da abbinare possono avere delle preferenze contrastanti, dunque e' importante ricercare un abbinamento che pur tenendo in considerazione queste preferenze costituisca comunque un sistema di coppie stabile.
Il primo capitolo e' suddiviso in due parti, nella prima, dopo una breve
panoramica delle proprieta' dei grafi che utilizzeremo nel seguito, illustreremo dei risultati relativi alla teoria del matching su grafi bipartiti come il Teorema di Hall ed il Teorema del matrimonio" di Frobenius che individuano le proprieta' caratteristiche dei grafi bipartiti fattorizzabili, cioe' per i quali e' possibile costruire un matching rispetto al quale tutti i nodi del grafo sono abbinati. Nella seconda parte ci occuperemo invece dei problemi di ottimizzazione che comportano la divisione di un insieme di elementi in coppie distinte rispettando determinati vincoli e classificati percio' come problemi di matching. Suddivideremo questi problemi in tre categorie: matching massimo, matching pesato e matching stabile, fornendo degli esempi per ciascuno e sottolineando la differenza tra il caso bipartito e quello non bipartito.
Successivamente prenderemo in esame il problema del matching
massimo, descrivendo una procedura algoritmica risolutiva, ed il problema del matching pesato, presentando la relativa formulazione come problema di programmazione lineare intera.
Nel secondo capitolo affronteremo dettagliatamente il problema del matrimonio stabile. Dopo aver formalizzato il concetto di stabilita' e di preferenza enunceremo e dimostreremo il Teorema del "matrimonio stabile", degli stessi Gale e Shapley, che prova l'esistenza di matching stabili per qualsiasi istanza del problema dando vita ad un algoritmo in grado di costruire in tempo polinomiale un particolare matching stabile. Illustreremo poi due algoritmi che migliorano il primo pur mantenendo la stessa complessita' asintotica nel caso peggiore. Infine daremo una dimostrazione non costruttiva dell'esistenza di matching stabili.
Nel terzo capitolo affronteremo le varianti del problema del matrimonio
stabile ottenute rilassando le limitazioni poste nella versione classica. Analizzeremo lo stable marriage problem con insiemi di cardinalita' diversa e successivamente il problema in cui le liste di preferenza possono essere incomplete. Per entrambi forniremo algoritmi che in tempo polinomiale costruiscono un matching stabile per qualsiasi istanza. Considereremo poi liste di preferenza non strettamente ordinate e descriveremo le tre possibili nozioni di stabilita' che emergono in tal caso (debole, super e forte) fornendo poi per ognuna un algoritmo che risolve il problema in tempo polinomiale. Lo stesso faremo per l'ultima delle varianti affrontate, quella in cui le liste di preferenza possono essere incomplete e non strettamente ordinate, con la differenza che, per quanto riguarda la stabilita' debole, proveremo la NP-completezza del problema di ricerca di matching stabili di cardinalita' massima e descriveremo un algoritmo approssimante che costruisce una soluzione con scostamento garantito dall'ottimo pari a 2.
In appendice sono riportati i programmi che codificano in linguaggio C
gli algoritmi analizzati.