Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Il cammino di un grafo G è una successione di vertici, in cui ogni coppia di vertici appartiene all’insieme dei lati:

 Cammino semplice: quando non si passa mai sugli stessi nodi;

 Ciclo: è un cammino in cui si inizia e si finisce con lo stesso nodo;

 Ciclo semplice: è un ciclo in cui non si ripetono i nodi, tranne il primo e l’ultimo (che devono coincidere).

Un grafo è “connesso” quando tutti i vertici sono collegati da almeno un lato, quindi non esistono vertici isolati.

Un grafo “non connesso” è quando almeno un vertice è isolato.

La partizione del grafo è detta anche “componente del grafo” ed è la somma o unione di componenti connesse.

Visite sui grafi

La visita in ampiezza è una procedura di attraversamento del grafo, consiste nell’inserimento di una coda (che è una

pila a doppia entrata) da un lato i nodi raggiunti (partendo da un nodo sorgente) e dall’altro lato i nodi adiacenti a

quello raggiunto ma non ancora presenti nella coda. Questa procedura produrrà in uscita un albero di copertura che

indicherà uno dei tanti cammini possibili per visitare il grafo (cambia in base al nodo sorgente).

inserimento dei nodi visitati ins. dei nodi adiacenti a

Coda quello visitato

La visita in profondità è una procedura di attraversamento del grafo, consiste nell’ inserimento dei nodi visitati (che

hanno più percorsi) in una pila, quindi partendo da un nodo sorgente trova un cammino verso il nodo più lontano e,

una volta raggiunto questo nodo (il quale ha tutti i nodi adiacenti già aggiunti), procede a ritroso inserendo nuovi

cammini (sui bivii incontrati) per raggiungere tutti gli altri nodi non ancora inseriti. In questo caso viene a formarsi una

foresta di copertura del grafo di ingresso. 8

4

1 6

2 3 5 7

Ordine visita: 1, 2, 3, 5(aggiunto alla pila), 6(aggiunto alla pila), 7(ultimo), tolgo 6 dalla pila e visito 8(ultimo), tolgo 5

dalla pila e visito 4(ultimo); la pila è vuota quindi ogni nodo è stato inserito.

Liste di adiacenza

E’ una rappresentazione dei grafi. Si mettono tutti i vertici in colonna e a fianco di ognuno di essi si mettono tutti i

vertici adiacenti a quello incolonnato. Vi sono tre casi:


ACQUISTATO

3 volte

PAGINE

20

PESO

1.07 MB

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
A.A.: 2014-2015

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher LordMatty di informazioni apprese con la frequenza delle lezioni di Algoritmi e Strutture Dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Insubria Como Varese - Uninsubria o del prof Massazza Paolo.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in informatica

Fondamenti di Informatica 1 - Excel
Dispensa
Basi di Dati - Domande e Risposte
Esercitazione
Algebra e Geometria - Teoremi e dimostrazioni
Appunto
Algebra e Geometria - appunti intero corso, anno 1°
Appunto