T - Teoria dei grafi Flashcards
a) Qual è la definizione di grafo?
b) Definire grafo semplice, orientato, non orientato
a) G := (V, E) dove V è un numero finito di vertici ed E è un numero finito di archi che definiscono una relazione BINARIA su V
b) semplice: se ammette cappi ma non ne ha
orientato: l’arco è una coppia ORDINATA di vertici
non orientato: l’arco è una coppia NON ordinata di vertici
Dato l’arco (a, b) ovvero a->b, definire incidenza e adiacenza.
Considerando l’arco (a, b) orientato si ha che è entrante/incidente in b, uscente da a , insistente su a-b. Questi aggettivi sono destinati ad archi orientati.
IN generale poi si ha che a,b sono adiacenti se e solo se esiste l’arco (a, b)
Come si calcola il grado di un vertice?
- G non orientato: degree(a) = num. archi incidenti
- G orientato: degree(a) = in_degree(a) + out_degree(a)
Definizione di cammino e di cammino semplice.
p è un cammino che da u va a u’ se esiste un insieme di vertici (v0, v1, …, vk) tali che u = v0, u’ = vk e per ogni i = 1, 2, …, k gli archi (v i-1, v i) appartengono all’insieme di archi E.
- u è raggiungibile da u’ se e solo se esiste un cammino p che da u vai a u’
Se tutti i vertici sono distinti, il cammino è semplice.
Definizione di connessione per un grafo non orientato. Definizione di componente connessa.
Un grafo non orientato è connesso se per ogni coppia di vertici vi, vk appartenenti all’insieme V esiste un cammino che va da vi a vj.
La componente connessa è un sottografo connesso e massimale. Quindi un grafo è non orientato e connesso quando di fatto c’è una sola componente connessa (che è massima) che lo compone -> corrispondono.
Definizione di connessione per un grafo orientato. Definizione di componente connessa.
Un grafo orientato è connesso se per ogni coppia di vertici vi, vk appartenenti all’insieme V esistono un cammino che va da vi a vj e un cammino che va da vj a vi.
Per i grafi orientati si parla di componente FORTEMENTE connessa. La componente fortemente connessa è un sottografo connesso e massimale. Quindi un grafo è orientato e connesso quando di fatto c’è una sola componente connessa (che è massima) che lo compone -> corrispondono.
Definizione di grafo completo. Numero di archi nel caso di un grafo completo orientato e non.
Un grafo è completo se per ogni coppia d vertici vi, vj appartenenti all’insieme V esiste l’arco (vi, vj) e appartiene a E.
Numero di archi:
- non orientato = binomiale (|V|, 2)
- orientato = |V| (|V| - 1)
Definizione di densità di un grafo.
Definizione di grafo denso, sparso, bipartito, pesato.
- densità: d(G) = |E grafo| / |E grafo completo|
- grafo denso: se |E| circa uguale a |V|^2
sparso: se |E| «_space;|V|^2
bipartito: G non orientato in cui i vertici possono essere divisi in due sottoinsiemi tali per cui, dati due vertici vi e vj, se vi appartiene a V1 allora avj appartiene a v2 e viceversa.
pesato: se agli archi è associato un valore detto peso
Definizione di albero, albero radicato e non (no proprietà).
Un albero è un grafo G = (V, E) non orientato.
Un albero libero o non radicato può presentarsi come:
- grafo non orientato, connesso, aciclico
- foresta: grafo non orientato, aciclico
Un albero radicato ha un nodo r detto radice che introduce la parentela.
Proprietà degli alberi radicati e non radicati.
Non radicati:
- Ogni coppia di nodi è connessa da un unico cammino semplice
- Per un albero connesso, la rimozione di un arco lo sconnette
- Albero connesso o aciclico: |E| = |V| - 1
Radicati:
- grado(T) = max di figli
- profondità(x) = lunghezza del cammino da r a x
- altezza(T) = max{profondità(x_i)}
Possibili rappresentazioni (linguaggio c) del nodo di un albero. Vantaggi e svantaggi.
1) struct che contiene: il campo chiave, il puntatore al padre e k puntatori ai figli (eventualmente NULL). Inefficiente per lo spazio, efficiente per il tempo di ricerca che è O(1)
2) struct che contiene: il campo chiave, il puntatore al padre, il puntatore al primo dei figli a sinistra, il puntatore al primo dei fratelli a destra. È efficiente per lo spazio ma inefficiente per il tempo che è O(n)
Caratteristiche degli alberi binari.
- Ogni nodo ha due figli quindi grado(T) = 2
- Se è completo: il numero di foglie è 2^h, il numero di nodi è la sommatoria con i che va da 0 a h di 2^i = 2^(h+1)-1
- Bilanciato: tutti i cammini radice-foglie sono di ugual lunghezza.
- se è completo è anche bilanciato, non è in generale vero il viceversa
