Introduzione ai Grafi

Un insieme di nodi (vertici), che rappresentano gli oggetti in questione, e un insieme di archi (spigoli), che rappresentano la relazione tra due nodi.

Un grafo in cui ogni coppia di nodi è collegata da al massimo un arco.

Un grafo in cui ogni coppia di nodi è collegata da uno o più archi.

Un grafo in cui è specificata una direzione per ogni arco.

Un grafo in cui gli archi hanno un peso associato.

Un grafo in cui gli archi non hanno una direzione.

Un percorso che passa esattamente una volta per ogni arco del grafo.

Un cammino euleriano che inizia e termina nello stesso nodo.

In un grafo orientato, un arco (x, y) "parte" dal nodo x e "arriva" al nodo y.

In un grafo orientato, due nodi sono adiacenti se esiste un arco che li collega direttamente.

Un arco (x, y) è incidente da x in y se parte dal nodo x e arriva al nodo y.

Un arco (x, y) è incidente in y se "arriva" al nodo y.

Il nodo x è adiacente al nodo y se esiste un arco che parte dal nodo x e arriva al nodo y.

In un grafo orientato, un arco che "parte" dal nodo x e "arriva" al nodo y è incidente da x in y.

In un grafo orientato, un arco che "arriva" al nodo y è incidente in y.

Un nodo è adiacente ad un altro nodo se esiste un arco che li collega direttamente.

Un grafo in cui gli archi non hanno una direzione specifica. Ad esempio, l'arco tra A e B è lo stesso arco tra B e A.

Un grafo in cui gli archi hanno una direzione specifica. Ad esempio, l'arco da A a B è diverso dall'arco da B a A.

Un insieme di nodi in un grafo.

Un insieme di archi in un grafo.

Una rappresentazione di un grafo attraverso un insieme di coppie ordinate (nodo iniziale, nodo finale).

Una rappresentazione di un grafo attraverso un insieme di coppie non ordinate (nodo1, nodo2).

Relazione tra coppie ordinate. Implica un ordine specifico tra gli elementi.

Relazione tra coppie non ordinate. L'ordine degli elementi non è significativo.

Un grafo che contiene un sottoinsieme di nodi e archi del grafo originale. I nodi del sottografo devono essere contenuti nel grafo originale, e gli archi del sottografo devono connettere solo nodi che sono presenti nel sottografo.

La funzione che associa un peso reale ad ogni arco del grafo pesato.

Un numero infinito. In un grafo pesato, un peso infinito indica che non esiste un percorso tra i due nodi corrispondenti all'arco.

Un gruppo di nodi e archi che formano una struttura connessa all'interno di un grafo più grande.

Il nodo iniziale e finale coincidono, formando un percorso chiuso.

Una struttura dati che rappresenta un grafo usando una lista di adiacenza per ogni vertice. Ogni lista contiene i vertici adiacenti a quel vertice.

Una rappresentazione di un grafo usando una matrice in cui ogni elemento rappresenta il peso dell'arco tra due vertici.

Il peso dell'arco tra i vertici x e y.

Un metodo per rappresentare un grafo, dove ad ogni vertice x è associata la lista L(x) di tutti i vertici y a cui x è direttamente connesso.

Il peso dell'arco tra i vertici x e y nella matrice di adiacenza.

Un collegamento diretto tra due vertici in un grafo.

Un nodo in un grafo.

Un grafo in cui è possibile passare da un qualsiasi vertice a un qualsiasi altro vertice tramite una sequenza di archi

Una foresta è un grafo non orientato aciclico, cioè senza cicli. Una foresta può essere composta da uno o più alberi.

Un albero è un grafo non orientato connesso che non contiene cicli.

Un grafo aciclico è un grafo che non contiene cicli. Un ciclo è un percorso che inizia e termina nello stesso nodo, attraversando tutti i nodi almeno una volta.

La rappresentazione matriciale M(x, y) di un grafo non orientato mostra la presenza o l'assenza di un arco tra i nodi x e y. Se un arco esiste, la cella M(x, y) avrà valore 1, altrimenti sarà 0.

Gli algoritmi e le strutture dati sono strumenti fondamentali nell'informatica. Gli algoritmi sono sequenze di istruzioni ben definite che risolvono un problema, mentre le strutture dati sono modi di organizzare i dati per permettere un accesso efficiente.

Ugo de'Liguoro e András Horváth sono due autori di un libro di testo sul tema degli algoritmi e delle strutture dati.

Le pagine indicate nel testo indicano la sezione specifica del libro di testo dove si trova l'argomento in questione.