Skip to content

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.

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista
Mostra/Nascondi contenuto.
Introduzione 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’ar- co 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 chia- meremo di “preferenza”. Per chiarire meglio di cosa si tratta utilizzeremo la terminologia adottata da Gale e Shapley nel 1962, quando per la prima vol- ta 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 oppo- sto 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 α, ed una donna β, sposata con b, tali che a preferisca β a α e β 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 1

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista
Il miglior software antiplagio

L'unico servizio antiplagio competitivo nel prezzo che garantisce l'aiuto della nostra redazione nel controllo dei risultati.
Analisi sicura e anonima al 100%!
Ottieni un Certificato Antiplagio dopo la valutazione.

Informazioni tesi

  Autore: Letizia Monaldi
  Tipo: Tesi di Laurea
  Anno: 2003-04
  Università: Università degli Studi Roma Tre
  Facoltà: Scienze Matematiche, Fisiche e Naturali
  Corso: Matematica
  Relatore: Marco Liverani
  Lingua: Italiano
  Num. pagine: 148

FAQ

Per consultare la tesi è necessario essere registrati e acquistare la consultazione integrale del file, al costo di 29,89€.
Il pagamento può essere effettuato tramite carta di credito/carta prepagata, PayPal, bonifico bancario.
Confermato il pagamento si potrà consultare i file esclusivamente in formato .PDF accedendo alla propria Home Personale. Si potrà quindi procedere a salvare o stampare il file.
Maggiori informazioni
Ingiustamente snobbata durante le ricerche bibliografiche, una tesi di laurea si rivela decisamente utile:
  • perché affronta un singolo argomento in modo sintetico e specifico come altri testi non fanno;
  • perché è un lavoro originale che si basa su una ricerca bibliografica accurata;
  • perché, a differenza di altri materiali che puoi reperire online, una tesi di laurea è stata verificata da un docente universitario e dalla commissione in sede d'esame. La nostra redazione inoltre controlla prima della pubblicazione la completezza dei materiali e, dal 2009, anche l'originalità della tesi attraverso il software antiplagio Compilatio.net.
  • L'utilizzo della consultazione integrale della tesi da parte dell'Utente che ne acquista il diritto è da considerarsi esclusivamente privato.
  • Nel caso in cui l’utente che consulta la tesi volesse citarne alcune parti, dovrà inserire correttamente la fonte, come si cita un qualsiasi altro testo di riferimento bibliografico.
  • L'Utente è l'unico ed esclusivo responsabile del materiale di cui acquista il diritto alla consultazione. Si impegna a non divulgare a mezzo stampa, editoria in genere, televisione, radio, Internet e/o qualsiasi altro mezzo divulgativo esistente o che venisse inventato, il contenuto della tesi che consulta o stralci della medesima. Verrà perseguito legalmente nel caso di riproduzione totale e/o parziale su qualsiasi mezzo e/o su qualsiasi supporto, nel caso di divulgazione nonché nel caso di ricavo economico derivante dallo sfruttamento del diritto acquisito.
L'obiettivo di Tesionline è quello di rendere accessibile a una platea il più possibile vasta il patrimonio di cultura e conoscenza contenuto nelle tesi.
Per raggiungerlo, è fondamentale superare la barriera rappresentata dalla lingua. Ecco perché cerchiamo persone disponibili ad effettuare la traduzione delle tesi pubblicate nel nostro sito.
Per tradurre questa tesi clicca qui »
Scopri come funziona »

DUBBI? Contattaci

Contatta la redazione a
[email protected]

Ci trovi su Skype (redazione_tesi)
dalle 9:00 alle 13:00

Oppure vieni a trovarci su

Parole chiave

grafi
matching
stable marriage problem
stable matching

Tesi correlate


Non hai trovato quello che cercavi?


Abbiamo più di 45.000 Tesi di Laurea: cerca nel nostro database

Oppure consulta la sezione dedicata ad appunti universitari selezionati e pubblicati dalla nostra redazione

Ottimizza la tua ricerca:

  • individua con precisione le parole chiave specifiche della tua ricerca
  • elimina i termini non significativi (aggettivi, articoli, avverbi...)
  • se non hai risultati amplia la ricerca con termini via via più generici (ad esempio da "anziano oncologico" a "paziente oncologico")
  • utilizza la ricerca avanzata
  • utilizza gli operatori booleani (and, or, "")

Idee per la tesi?

Scopri le migliori tesi scelte da noi sugli argomenti recenti


Come si scrive una tesi di laurea?


A quale cattedra chiedere la tesi? Quale sarà il docente più disponibile? Quale l'argomento più interessante per me? ...e quale quello più interessante per il mondo del lavoro?

Scarica gratuitamente la nostra guida "Come si scrive una tesi di laurea" e iscriviti alla newsletter per ricevere consigli e materiale utile.


La tesi l'ho già scritta,
ora cosa ne faccio?


La tua tesi ti ha aiutato ad ottenere quel sudato titolo di studio, ma può darti molto di più: ti differenzia dai tuoi colleghi universitari, mostra i tuoi interessi ed è un lavoro di ricerca unico, che può essere utile anche ad altri.

Il nostro consiglio è di non sprecare tutto questo lavoro:

È ora di pubblicare la tesi