estensioni dei grafi

• grafi pesati
• grafi etichettati
• ipergrafi

formalizzazione matematica

un grafo è una coppia di insiemi:

grafo = (nodi,archi)

dove:

il primo nodi è un qualsiasi insieme di elementi
il secondo archi è un insieme di coppie del primo

formalizzazioni matematiche

definizione di grafo usando solo:
insiemi e tuple

insiemi: {…}
tuple: (…)

da grafo a stringa
simboli: elementi semplici, graffe, parentesi e virgole

formalizzazione del grafo di esempio

trascrizione come stringa
simboli: elementi semplici, graffe, parentesi e virgole

({1,2,3,4}, {(1,2), (1,3), (2,3), (2,4)}}

grafi pesati ed etichettati

percorsi non intersecanti:
trovare percorsi da un nodo a a un nodo b
che non si intersecano

quando serve?

flussi continui (di energia, fluidi, beni)
da a a b

problema reale da cui viene:

• percorsi senza archi in comune
  invece di nodi in comune
• capacità diversa degli archi

capacità degli archi

arco = percorso possibile per un flusso

• tipo di cavi elettrici
• ampiezza dei tubi
• numero e grandezza degli aerei su una tratta
• …

massimizzare il flusso

maximum flow:

trovare percorsi da a a b
con la massima capacità di trasmissione

memorizzazione della capacità

per ogni arco: intero o reale che indica la capacità

insieme archi

l'arco diventa una tripla (n,s,c)
arco da n a s con capacità c

insiemi di successori

il successore diventa una coppia (s,c)
insiemi { (successore,capacita'), (successore,capacita'), … }

matrice di adiacenza

matrice di booleani ⇒ matrice di numeri
esiste arco da n a s diventa:
capacità dell'arco da n a s
assenza arco = capacità 0

percorso più breve

esiste percorso da a a b?
trovare il percorso più breve da a a b

da dove vengono:

• trovare la strada più breve da un posto a un altro
• trovare la minima sequenza di azioni che realizza un obiettivo
• …

arco: tratta di percorso
azione

tratte di lunghezza diversa
azioni di tempi diversi
o costi diversi

capacità, lunghezze, costi

stessa memorizzazione:

ogni arco ha un numero associato

nome generico: peso di un arco

nome generico: grafo pesato

collegamenti multipli

ci possono essere due strade diverse fra gli stessi due posti

ci possono essere due condutture con gli stessi punti di partenza e arrivo

vanno bene i grafi normali?

grafi normali per collegamenti multipli

singola strada, con la minima distanza

la strada più veloce potrebbe cambiare a seconda dell'orario

singola conduttura

nel flusso massimo non si vede che sono impegnate due condutture

definizione di grafo

grafo = insieme di nodi e insieme di archi

implicito in "insieme": no ripetizioni
un elemento può essere presente una volta sola al massimo

multiinsieme

multiinsieme: un insieme con ripetizioni

esempio: {1,2,4,2,1}
2 e 1 presenti due volte
1 presente una volta sola

multigrafo

grafo = insieme di nodi e insieme di archi
multigrafo = insieme di nodi e multiinsieme di archi

multigrafo, disegnato

più archi possibili fra gli stessi due nodi

multigrafo, implementazione

Python: package opzionale

alternativa: usare liste
ignorare l'ordine degli elementi

insieme

no elementi ripetuti, no ordine

multiinsieme

elementi ripetuti ammessi, no ordine

lista

elementi ripetuti ammessi, ordinati

estensioni del concetto di arco

arco

coppia di nodi

arco pesato

coppia di nodi
e un numero

iperarco

insieme di nodi

anche: iperarchi pesati…

ipergrafi

come i grafi
ma con gli iperarchi

esempio di ipergrafo?

un grafo e un ipergrafo

iperarchi orientati

arco:

da 1 a 2

iperarco:

da 1 a 2,5
oppure da 1,2 a 5

la destinazione può essere sempre singola
oppure no

cambiano diverse cose
esempio: la definizione di ciclo in un grafo non è più unica