Grafi¶

1.1 Grafi non orientati e orientati

Grafi semplici e multigrafi

Apri
1.2 Rappresentazioni di un grafo

La matrice di incidenza e la conservazione del flusso

Apri
1.3 Connettività

Apri
1.4 Alberi e foreste

Apri
1.5 Il rango della matrice di incidenza

Apri
1.6 Ricerca su grafi

L'albero predecessore · La visita in ampiezza sul grafo di riferimento · La ricerca approfondita sul grafo di riferimento · Utilizzo della ricerca

Apri

Prerequisiti

Algebra lineare: matrici, combinazioni lineari, vettori linearmente indipendenti e rango di una matrice.
Insiemi, relazioni e classi di equivalenza; la notazione \(O(\cdot)\) per il tempo di esecuzione di un algoritmo.
Non è necessaria alcuna conoscenza della teoria dei grafi: ogni nozione è definita in questo capitolo.

Obiettivi

Alla fine di questo capitolo sarai in grado di:

usare le nozioni di base dei grafi orientati e non orientati: adiacenza, grado, passeggiate, cammini e cicli;
rappresentare un grafo mediante una matrice di adiacenza, liste di adiacenza, una lista di archi o una matrice di incidenza nodo-arco, e confrontare lo spazio richiesto da ciascuna rappresentazione;
trovare le componenti connesse e le componenti fortemente connesse di un grafo;
riconoscere un albero attraverso caratterizzazioni equivalenti e calcolare il rango della matrice di incidenza;
eseguire la ricerca in ampiezza e in profondità, costruire l'albero dei predecessori e dimostrare che la ricerca individua i nodi raggiungibili in tempo \(O(|N|+|A|)\).

Avanti: 1.1 Grafi non orientati e orientati

Esercizi su questo capitolo: Grafi

Nel laboratorio interattivo: Ricerca su grafo: BFS e DFS.