Grafi triangolati e triangolazioni di grafi M. Moscarini M. Mezzini

Grafi triangolati e triangolazioni di grafi

M. Moscarini M. Mezzini

Definizioni

Percorso in un grafo

Definizioni

1

2

3

4

5

Ciclo in un grafo

Definizioni

1

2

3

4

5

Corda di un ciclo o di un percorso

1

2

3

4

5

Definizioni

Grafo triangolato (o cordale)

1

2

3

4

5

Definizioni

Triangolazione di un grafo

1

2

3

4

5

Definizioni

Applicazioni dei grafi triangolati

•Basi dati: progettazione delle basi di dati



•Calcolo numerico: calcolo delle soluzioni dei sistemi di equazioni lineari




•Statistica: calcolo di probabilità



•Statistica: calcolo di probabilità

•Intelligenza artificiale: machine learning


Schema base di dati

Studenti

Mat_Stud Nome Cognome

Appello

Codice_App Materia Data

Prenotazione

Codice_App Mat_Stud


Schema base di dati

Studenti


Appello


Prenotazione

Codice_App Mat_Stud



Ipergrafo associato allo schema


Schema base di dati

Studenti


Appello


Prenotazione

Codice_App Mat_Stud




Nome

Cognome

Mat_Stud

Data

Materia

Codice_App

Grafo associato allo schema


Schema base di dati

Studenti


Appello


Prenotazione

Codice_App Mat_Stud




Nome

Cognome

Mat_Stud

Data

Materia

Codice_App

Grafo associato allo schema

Lo schema è buono solo se il grafo associato è cordale


Attività di ricerca nell’ambito della cordalità


Percorso senza corde per tre vertici in grafi bipartiti

s t

v



s t

v

Motivazioni: •Collegato alla teoria dei grafi perfetti•Collegato alla convessità dei percorsi senza corde in grafi bipartiti



s t

v

Motivazioni: •Collegato alla teoria dei grafi perfetti•Collegato alla convessità dei percorsi senza corde in grafi bipartiti

Risultati: •NP-Completo



Convessità dei percorsi senza corde in grafi bipartiti. Dato un insieme di vertici X trovare l’involucro convesso CH(X).


1

4

5

3

6

2X



X1

4

5

3

6

2



CH(X)1

4

5

3

6

2



CH(X)

Motivazioni: •Collegato alla teoria delle basi di dati•Collegato alla teoria della convessità

1

4

5

3

6

2



Motivazioni: •Collegato alla teoria delle basi di dati•Collegato alla teoria della convessità

Risultati: •Algoritmo polinomiale

CH(X)1

4

5

3

6

2


Triangolazione minimale di un grafo


1

2

3

4

5


1

2

3

4

5

Motivazioni: •Calcolo delle soluzioni di un sistema di equazioni lineari•Teoria dei grafi



1

2

3

4

5

Motivazioni: •Calcolo delle soluzioni di un sistema di equazioni lineari•Teoria dei grafi

Risultati: •Algoritmo semplice e veloce quando il grafo è denso•Implementazione in C e confronto con gli algoritmi esistenti



Algoritmo dinamico per inserire o rimuovere archi da un grafo cordale



1

2

3

4

5



1

2

3

4

5


Motivazioni: •Applicazioni in ambito dell’intelligenza artificiale


1

2

3

4

5


Motivazioni: •Applicazioni in ambito dell’intelligenza artificiale

Risultati: •Algoritmo con O(1) per decidere se un arco può essere aggiunto od eliminato e O(n2) per modificare le strutture dati.

Attività di ricerca nell’ambito della protezionedei dati statistici


4

4

4

2

x1

x2 x3

x4

x5


4

4

4

2

x2 =3

x1 =0x4 =2

x3 =1

x5=1


4

4

4

2

x2 =2

x1 =1x4 =1

x3 =2

x5=1


4

4

4

2

x2 =2

x1 =1x4 =1

x3 =2

x5=1

Motivazioni: •Protezione della privacy

Risultati: •Diversi algoritmi lineari nelle dimensioni del grafo (ottimi)

Grafi triangolati e triangolazioni di grafi M. Moscarini M. Mezzini

Documents

Transcript of Grafi triangolati e triangolazioni di grafi M. Moscarini M. Mezzini