Grafi Parte 1 Flashcards
Grafo Orientato
Coppia di insiemi V e E:
- V insieme dei vertici non vuoto e
- E insieme degli archi orientati in V (coppie ordinate di elementi di V non per forza distinti.)
Funzione del Successore Gamma
Data la funzione gamma da V ->a V, l’immagine di x attraverso a gamma è y tale che x,y appartiene a E.
Diciamo che x è il predecessore di y e y è il successore di x.
Definizione alternativa grafo orientato
Coppia di insiemi V e Gamma:
- V insieme dei vertici non vuoto.
- Gamma mappatura da V a se stesso.
Grafo non orientato
Coppia di insiemi V e E:
- V insieme dei vertici non vuoto e
- E insieme degli archi non orientati in V (coppie non ordinate di elementi di V non per forza distinti)
Arco incidente
Dato l’arco e=(x,y) di E, diciamo che e è incidente sui vertici x e y.
(o unisce x e y)
Arco uscente e arco entrante
Arco uscente da un vertice x se x è l’origine di un arco e di E.
Arco entrante in un vertice x se x è la destinazione di un arco e di E.
Ordine e Dimensione di un Grafo
|V| ordine di un grafo: numero di vertici del grafo.
|E| dimensione di un grafo: numero di archi del grafo.
2 vertici adiacenti e Vicinato
2 vertici sono adiacenti se sono collegati da almeno un arco.
Il vicinato N(x) di un vertice x è l’insieme dei vertici adiacenti ad x. (vicinato entrante e uscente se g orientato)
Multigrafo, archi multipli e cappi
Un grafo che contiene più archi di E aventi gli stessi vertici finali si chiama multigrafo.
Arco multiplo o parallelo se ci sono più archi che collegano gli stessi due vertici.
Loop o Cappio se un arco collega un vertice a se stesso.
Grafo semplice
Grafo che non contiene archi multipli o cappi.
Grado di un vertice deg, deg in e deg out
Se g non è orientato, il grado di un vertice x è dato dal numero di archi incidenti in x (il cappio vale due): deg(x).
Se g è orientato:
- il grado uscente di un vertice x è dato dal numero di archi uscenti da x: degout(x).
- il grado entrante di un vertice x è dato dal numero di archi entranti in x: degin(x).
Grado e Dimensione Massima (g non orientato semplice)
Grado massimo di un vertice x è n-1.
Dimensione max di un g non orientato semplice è n(n-1)/2 (lo ricavo da lemma strette di mano)
Grafo Completo (non orientato semplice)
Un g non orientato semplice si dice completo Kn se ogni vertice ha grado massimo ovvero è adiacente a tutti gli altri vertici.
Per ogni vertice deg(v)=n-1.
Dimensione di g completo: n(n-1)/2
Grafo Pesato
G si dice pesato se esiste una funzione w:E -> R+ che assegna un peso w(e) ad ogni arco e di E.
Grado di un vertice in un grafo pesato
Se g pesato non è orientato: il grado pesato di un vertice x è la somma dei pesi di tutti gli archi incidenti in x: STR(x).
Se g pesato è orientato:
- il grado pesato entrante di x è la somma dei pesi degli archi entranti in x: strin(x).
- il grado pesato uscente di x è la somma dei pesi degli archi uscenti da x: strout(x).
