FANDOM


Grafo aciclicoModifica

2 Un grafo è ciclico se ha almeno un arco di tipo Backward.

Componenti connesse (per grafi non orientati)Modifica

3 Individuando le componenti connesse (= insieme massimale di tutti i vertici raggiungibili) degli alberi della visita in profondità, si può verificare se esiste almeno un cammino tra due nodi dati.

Connettività (per grafi che rappresentano una rete)Modifica

Bridge (= arco la cui rimozione disconnette il grafo)Modifica

6 Un arco Tree è un bridge se non esiste nessun arco Backward che collega un qualsiasi discendente a un qualsiasi antenato nell'albero della visita in profondità. Solo gli archi Tree possono essere dei bridge, perché l'esistenza di un arco Backward implica l'esistenza di un altro cammino che collega i due nodi.

Punti di articolazione (= vertice la cui rimozione disconnette il grafo)Modifica

7 Si distinguono due casi:

  • vertice radice del grafo: è un punto di articolazione se ha almeno due figli nell'albero della visita in profondità;
  • altro vertice: è un punto di articolazione se almeno un sottoalbero figlio di quel nodo non ha un arco Backward che lo collega a un nodo antenato.

DAGModifica

11 I DAG sono grafi orientati privi di cicli che rappresentano dei modelli di ordine parziale, dove gli archi sono dei vincoli di precedenza di esecuzione dei compiti: un compito è eseguibile solamente dopo il completamento dei precedenti, e così via → scheduling: azioni da svolgere in un certo ordine.

13 L'ordinamento topologico di un DAG è la riscrittura del DAG in una linea di vertici con il vincolo che tutti gli archi vadano da sinistra a destra o viceversa (inverso). Per effettuare l'ordinamento topologico, si ordinano i nodi per tempi di fine elaborazione di una visita in profondità, quindi si disegnano tutti gli archi secondo una visita topologica diretta/inversa del grafo.

Componenti fortemente connesse (per grafi orientati)Modifica

10 grafo trasposto = grafo con gli stessi vertici ma con gli archi di direzione inversa

24 Per trovare le componenti fortemente connesse si usa l'algoritmo di Kosaraju:

  1. si traspone il grafo;
  2. si esegue la visita in profondità sul grafo trasposto, calcolando i tempi di scoperta e di fine elaborazione;
  3. eseguendo la visita in profondità sul grafo originale per quei tempi di fine elaborazione decrescenti, si trovano man mano le componenti fortemente connesse;
  4. 27 s'interpreta il grafo in classi di equivalenza (= componenti fortemente connesse) secondo la proprietà di mutua raggiungibilità, cioè si ricostruisce un grafo semplificato considerando ogni componente fortemente connessa come un unico nodo rappresentativo e considerando solo gli archi che connettono componenti fortemente connesse.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale