grafi nel mondo reale:

reti stradali

internet

incontri sportivi

nodi = incroci, archi = strade

nodi = pagine, archi = links

nodi = squadre, archi = incontri

facebook nodi = persone, archi = amicizie

giochi nodi = posizioni, archi = mosse

reti elettriche nodi = connessioni, archi = elementi

ognuno amico di tutti gli altri

GRAFO COMPLETO

nessuno amico di nessuno

sottografo completo -> cricca (clique)

un’ altra cricca

c’è almeno una persona con un numero pari di amici ?

grado di un nodo = numero nodi adiacenti

somma dei gradi per ogni nodo= 2 volte numero degli archi

numero nodi con grado dispari è pari

come dimostrare per induzione ?

5 persone diconoA: ho 4 amici in (A,B,C,D,E)B: ho 3 amici in (A,B,C,D,E)C: ho 3 amici in (A,B,C,D,E)D: ho 2 amici in (A,B,C,D,E)E: ho 2 amici in (A,B,C,D,E)

è possibile ?

A B C D E

4 3 3 2 2

A

BC

E D

B C D E

2 2 1 1

A

BC

E D

B C D E

2 2 1 1

A

BC

E D

C D E

1 0 1

A

BC

E D

C D E

1 0 1

A

BC

E D

la soluzione è unica ?

A

B C

E D

A

BC

E D A

B C

E D

sono diversi,ma se non si tiene conto dei nomi,sono uguali

hanno la stessa forma -> isomorfi

non isomorfi

A B C D E

4 4 4 2 2

A

BC

E D

B C D E

3 3 1 1

A

BC

E D

B C D E

3 3 1 1

A

BC

E D

C D E

2 0 0

A

BC

E D

3 brocche: capacità 8, 5, 3 litri

come ottenere 4 litri ?

nodi=particolare distribuzione dei litri

archi=mosse=versamenti ammissibili

siccome la somma totale è costante basta indicare il contenuto delle brocche piccole

(0,0); (0,1); (0,2); (0,3); (1,0); (1,1); (1,2); (1,3);(2,0); (2,1); (2,2); (2,3);(3,0); (3,1); (3,2); (3,3);(4,0); (4,1); (4,2); (4,3);(5,0); (5,1); (5,2); (5,3);

hmm… servono proprio tutti ?

(0,0); (0,1); (0,2); (0,3); (1,0); (1,1); (1,2); (1,3);(2,0); (2,1); (2,2); (2,3);(3,0); (3,1); (3,2); (3,3);(4,0); (4,1); (4,2); (4,3);(5,0); (5,1); (5,2); (5,3);

possibile che nessuna brocca sia piena oppure vuota?

NO

(0,0); (0,1); (0,2); (0,3); (1,0); (1,1); (1,2); (1,3);(2,0); (2,1); (2,2); (2,3);(3,0); (3,1); (3,2); (3,3);(4,0); (4,1); (4,2); (4,3);(5,0); (5,1); (5,2); (5,3);

da escludere i casi in cuinessuna brocca è piena oppure vuota

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(0,0)(0,1) (0,2)

(0,3)

(1,0)

(2,0)

(3,0)

(4,0)

(5,0) (5,1) (5,2)

(1,3)

(2,3)

(3,3)

(4,3)

(5,3)

(8,0,0)

(0,8,0) (0,0,8)

(7,0,1)

(6,0,2)

(5,0,3)

(4,0,4)

(3,0,5)

(2,0,6)

(1,0,7)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,6,0)

(1,7,0)

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

7 versamenti

(8,0,0)

(7,0,1)

(6,0,2)

(5,0,3)

(7,1,0)

(6,2,0)

(5,3,0)

(4,4,0)

(3,5,0)

(2,5,1)

(1,5,2)

(0,5,3)

(1,4,3)

(2,3,3)

(3,2,3)

(4,1,3)

6 versamenti

qual è il più grande insieme di personeche non si conoscono ?

qual è il più grande insieme di personeche non si conoscono ?

qual è il più grande insieme di personeche non si conoscono ?

ma non sempre si può provare, anzi ….

qual è il più grande insieme di personeche non si conoscono ?

colorare i nodi in modo che nodi adiacenti abbiano colori diversi

minimo numero di colori ?

ma non sempre si può provare, anzi ….

trovare un esempio (semplice) dove

max cricca < numero cromatico

max ind set > decomposizione in cricche

mappa geografica

minimo numero di colori ?

mappa geografica

minimo numero di colori ?

grafo planare !

Teorema (Appel Haken 1976): 4 colori sono sufficienti

Congettura dal 1850

grafo planare !

Teorema (Appel Haken 1976): 4 colori sono sufficienti

Congettura dal 1850

quattro colori sononecessaricricca da 4 nodi

1 2 3

7

6

5

4

7 nodi

1

23

76

5

4

7 nodi

7 regioni

1 2

3 76

5

4

7 nodi

7 regioni

89

11

1012

12 archin + r = a + 2

formula di Eulero

dimostrazione per induzione

vera per n =1 a=0 r = 1

n + r = a + 2

vera per n-1 si aggiunge un nodo

si aggiungono a-1 regioni

si aggiungono a archi

cammino più corto ? 3

cammino più corto ? 2

il più lungo fra i cammini più corti ?

diametro del grafo

cammino più corto ? 4

congettura: il diametro del grafo delle conoscenze(nel mondo) = 7

è possibile disegnare il grafo senza staccare la penna ?

è possibile disegnare il grafo senza staccare la penna ?

è possibile far sedere tutti attorno ad un tavolo rotondoin modo che ognuno sia seduto vicino a due amici ?

è possibile far sedere tutti attorno ad un tavolo rotondoin modo che ognuno sia seduto vicino a due amici ?

problema del circuito hamiltoniano (molto difficile)

?

solo circuiti pari ma i nodi sono dispari !

e adesso ?

è possibile far sedere a due a due le personein modo da far sedere vicini solo amici ?

è possibile far sedere a due a due le personein modo da far sedere vicini solo amici ?

come costruire un torneo in cui ogni squadra incontra ogni altra squadra ?

!

come assegnare chi gioca in casa per ogni partita ?

è possibile che ogni squadra alterni partite in casa con partite fuori casa ?

A

B

C

D

A

B

C

D

A

B

C

D

come assegnare chi gioca in casa per ogni partita ?

è possibile che ogni squadra alterni partite in casa con partite fuori casa ?

A

B

C

D

A

B

C

D

A

B

C

D

come assegnare chi gioca in casa per ogni partita ?

è possibile che ogni squadra alterni partite in casa con partite fuori casa ?

A

B

C

D

A

B

C

D

A

B

C

D

come assegnare chi gioca in casa per ogni partita ?

è possibile che ogni squadra alterni partite in casa con partite fuori casa ?

A

B

C

D

A

B

C

D

A

B

C

D

come assegnare chi gioca in casa per ogni partita ?

è possibile che ogni squadra alterni partite in casa con partite fuori casa ?

A

B

C

D

A

B

C

D

A

B

C

D

come assegnare chi gioca in casa per ogni partita ?

è possibile che ogni squadra alterni partite in casa con partite fuori casa ?

A

B

C

D

A

B

C

D

A

B

C

D

colorare i nodi con due coloriin modo da avere il massimonumero di archi con due colorie gli archi grossi obbligati con due colori

n nodin-1 archi

m nodi n-m nodi

m-1 archi n-m-1 archi

(m-1)+1+(n-m-1)=n-1

almeno due nodi di grado 1

2(n-1)somma dei gradi uguale a

alberi di supporto quanti ?

forse ?

tutti gli archi archi dell’albero

NO ERRATO ! perché?

se il grafo è completo

se il grafo non è completo

det = 8

Laplaciano del grafo

-1

1

11

111

1110

11101

111010

1110100

11101001

11101001101000

quante sono le stringhe di 0 e 1 tali che in ogni prefissogli 0 sono meno degli 1 ?

numeri di Catalan

1100

per n=2 =1

per n=3 = 2

111000

110100

per n=4 = 5

11110000

11101000

11100100

11011000

11010100

isomorfi

I numeri di Catalan rappresentano una limitazione superioreal numero di alberi isomorficamente diversi