Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

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.

Mostra/Nascondi contenuto.
Prefazione In questo breve testo si vogliono trattare alcuni problemi relativi alla teoria dei mat- ching 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à preli- minari. Elencheremo anche i piùimportanti teoremi ed algoritmidella 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. Inpiù, vorremmo capirese inundatografocisiaunmatching 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à polino- i

Laurea liv.I

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Alessandro Cecchin Contatta »

Composta da 57 pagine.

 

Questa tesi ha raggiunto 212 click dal 20/02/2015.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.