Cammini e Connessione Flashcards
Cammino p tra v0 e vj
Un cammino p tra il vertice v0 e vj di G, è una successione di vertici p=(v0…vj) tale che (vk,vk+1) appartiene a E per ogni k=0…j-1.
Lunghezza di un cammino, cammino semplice, cammino chiuso, cammino chiuso semplice (ciclo), cappio, grafo aciclico.
Lunghezza di un cammino l(p) è data dal numero di archi da cui è composto p.
Cammino semplice se i vertici di p sono distinti ad eccezione dei vertici iniziali e finali.
Cammino chiuso se v iniziale= v finale.
Cammino chiuso semplice si chiama ciclo.
Il cappio è un ciclo di lunghezza 1.
Grafo aciclico se non ha cicli di lunghezza >2
Se il grafo è orientato allora…cammini
Cammini orientati
Cammini semplici orientati.
Teo Potenza K esima della matrice di adiacenza
Il generico elemento della potenza kesima della matrice di adiacenza A di G, A^k(i,j), mi dice il numero di cammini di lunghezza k tra il vertice i e il vertice j.
Dim Potenza K esima della matrice di adiacenza
Guarda ipad
Sottografo
Dato G=(V,E), G’ è un sottografo se V’ e E’ sono sottoinsiemi di V ed E.
Connessione tra vertici, G connessi e G non connessi (componenti massimali connesse)
Due vertici sono connessi se esiste un cammino che li collega.
Un grafo è connesso se esiste un cammino tra ogni coppia di vertici del grafo.
Un grafo se non è connesso allora può essere scomposto in componenti connesse massimali.
Massimali perchè non esistono altri vertici del grafo che se aggiunti alla componente la facciano rimanere connesso.
Arco Ponte
Un arco di un grafo che se eliminato aumenterebbe il numero di componenti connesse del grafo.
Cammino minimo, d(u,v), infinito e 0, matrice delle distanze e diametro.
Cammino di lunghezza più breve che collega 2 vertici.
La lunghezza del cammino minimo tra u e v si chiama DISTANZA d(u,v).
d(u,v) vale infinito se u e v non sono connessi e 0 se u=v.
Matrice delle distanza: matrice delle lunghezze dei cammini minimi tra tutte le coppie di vertici.
Diametro: lunghezza massima di tutti i cammini minimi contenuti nel grafo.
Grafo Soggiacente Gs
Il grafo G se non si considerano l’orientamento dei suoi archi.
Grafo debolmente/fortemente connesso, Coppia di vertici fortemente/debolmente connessa.
G orientato debolmente connesso se il suo grafico soggiacente è connesso.
Due vertici a e b sono fortemente connessi se esiste un cammino orientato da a a b e uno da b a a.
G fortemente connesso se ogni sua coppia di vertici è fortemente connessa.
Peso del cammino e Cammino minimo per g pesati.
Il peso del cammino l(p) è dato dalla somma dei pesi degli archi che lo costituiscono.
Il cammino minimo per grafi pesati d(u,v) è dato dal cammino di peso più piccolo che collega i due vertici.
