8B Teoria dei grafi definizioni Flashcards
Cos’è un grafo SEMPLICE?
Un grafo SEMPLICE G=(V,E) consiste di un insieme non vuoto V di elementi chiamati vertici (o nodi) e di un insieme finito E di coppie non ordinate di elementi distinti di V. V = vertices, E = edges
Non consente archi multipli e non ammette loop.
Un esempio di un grafo semplice?
G = (V, E)
V = { 1, 2, 3, 4 }
E = { {1,2}, {2,4} }
Cos’è un grafo?
Un grafo G=(V,E) consiste di un insieme non vuoto V di elementi chiamati vertici (o nodi) e di un insieme finito E di coppie non ordinate di elementi di V.
V = vertices, E = edges
Consente archi multipli e loop.
Un esempio di un grafo?
G = (V, E)
V = { 1, 2, 3, 4 }
E = { {1,2}, {2,4}, {3, 3} anello/self-loop }
Due grafi G1 e G2 sono isomorphi se…
esiste una corrispondenza uno-a-uno tra i vertici di G1 e i vertici G2 e il numero di archi tra i vertici di G1 è uguale a quello dei corrispondenti vertici di G2
Due vertici sono adiacenti se…
…esiste un arco che li collega
Due archi sono adiacenti se…
… hanno un vertice in comune
Grado di un nodo, deg(v) è…
deg(v) = il numero di archi incidenti al nodo v
Cosa sono nodi finali?
Nodi finali hanno grado 1
Cos’è un nodo isolato?
Un nodo isolato ha grado 0
Qual’è il grado di un nodo che ha solo un anello (self-loop)?
Grado 2
Cos’è un sottografo di grafo G?
Un grafo che può essere ottenuto da G rimuovendo nodi/archi da G
Cosa dimostra una lista di adiacenza?
Per ogni vertice del grafo, mostra i vertici ad esso collegati.
Ha V righe, e i vertici adiacenti ad ogni vertice sono nominati
Cosa dimostra una matrice di adiacenza?
Per ogni coppia di vertici del grafo, indica se esiste uno (o più) arci tra di essi.
Ha V righe e V colonne e dà il numero di archi
Cos’è una matrice di incidenza?
Ha ‘V’ righe e ‘E’ colonne, con ‘1’ se un vertice è incidente a un arco, altrimenti ‘0’.
Cos’è un grafo completo Kn = (V, E) ?
È un grafo semplice dove V = n e ogni coppia di vertici è adiacente
In un grafo completo Kn, come si calcola E?
E = n ( n - 1) / 2
Cos’è un grafo regolare?
Un grafo regolare è un grafo dove ogni nodo a grado (degree) r.
Un grafo completo Kn è anche …
…un grafo regolare di grado n-1
WALK
Una passeggiata in un grafo G è …
una sequenza finita di archi nella forma
v0 -> v1 -> … -> vm
(edges can be repeated &
vertices can be repeated)
Cos’è la lunghezza della passeggiata?
Il numero di archi
TRAIL
Una caTena è …
una passeggiata che attraversa archi diversi
edges can NOT be repeated &
vertices can be repeated
Cos’è un CLOSED WALK?
Una passeggiata in cui v0 = vm
PATH
Cos’è un cammino?
una catena dove anche i vertici sono distinti
edges can NOT be repeated &
vertices can NOT be repeated
Cos’è un grafo CONNESSO?
Se e soltanto se esiste un cammino tra ogni coppia di nodi
(every node reachable)
Cosa sono le componenti connesse in un grafo?
Le componenti connesse sono sottoinsiemi massimi di vertici in cui ogni coppia di vertici è collegata da un percorso. In ogni componente connessa esiste un cammino tra qualsiasi coppia di vertici.
G è un grafo Euleriano se e soltanto se…
…i nodi hanno tutti grado pari
