FANDOM


Nota disambigua
Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 4. Grafi e alberi.
Blue Glass Arrow RTL  3. Gli algoritmi di ordinamentoCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  5. La ricorsione
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

GrafiModifica

2 G = (V, E):

  • V = insieme finito dei vertici/nodi
  • E = insieme finito di archi, che mette coppie di vertici in relazione (binaria)
  • grafo non orientato: non esiste un verso di percorrenza
  • grafo orientato: un arco può essere percorso in un solo verso

3-4 cappio = arco che ritorna sul vertice di partenza (solo nei grafi orientati)

5 Due vertici si dicono tra loro adiacenti se sono connessi da un arco.

6 grado di un vertice = numero di archi che insistono su quel vertice
per i grafi orientati: in_degree (entranti), out_degree (uscenti)

7 Esiste un cammino tra due vertici se esiste una sequenza di vertici per cui il primo vertice è uguale a uno dei due vertici e l'ultimo è uguale all'altro vertice, e se esiste una sequenza di k archi.

cammino semplice = non ripassa mai su un nodo già passato → i vertici sono tutti distinti.

9 ciclo o cammino chiuso = il vertice di partenza e di arrivo coincidono
caso particolare: cappio = ciclo di lunghezza 1

grafi aciclico = privo di cicli → se si ha bisogno che l'elemento precedente sia chiuso prima di passare al successivo, si deve verificare che non ci siano cicli che impediscono l'avvio.

10 grafo connesso = se si prende una qualsiasi coppia di vertici, esiste sempre un cammino che connette tale coppia (solo nei grafi non orientati).

componente connessa = è il sottografo massimale[1] di un grafo per cui tutti i vertici sono mutualmente connessi (solo nei grafi non orientati).

11 Nei grafi orientati la raggiungibilità in un senso non implica la raggiungibilità nell'altro. grafo fortemente connesso = ogni coppia di vertici è raggiungibile in entrambi i sensi

14 grafo completo = esistono tutti gli archi per tutte le coppie di vertici:

  • nei grafi non orientati: \left| E \right| = \frac{\left(\left|V\right| - 1\right) \cdot \left| V \right|}{2}
  • nei grafi orientati: \left| E \right| = \left(\left|V\right| - 1\right) \cdot \left| V \right|

dove:

  • \left|E\right| è il numero di archi;
  • \left|V\right| è il numero di vertici;
  • \left|V\right| - 1 è il numero di archi per ogni vertice.

13 \left|E\right| può crescere al più con il quadrato di \left|V\right|:

  • nei grafi densi: \left|E\right| \cong \left| V^2 \right|
  • nei grafi sparsi: \left|E\right| \ll \left| V^2 \right|

15 grafo pesato: una funzione che riceve in input una coppia di nodi e restituisce il peso della coppia (generalmente un numero intero).

AlberiModifica

25 albero non radicato = grafo non orientato, connesso, aciclico (no nodi in particolare)

foresta = insieme di alberi

Proprietà

G albero non radicato:

  • ogni coppia di nodi è connessa da un solo cammino semplice;
  • G connesso: rimuovere qualsiasi arco comporta sconnettere il grafo;
  • \left|E\right| = \left|V\right| - 1;
  • G aciclico: aggiungere un arco comporta introdurre un ciclo.

Alberi radicatiModifica

27 Si individua il nodo radice r → si stabiliscono delle relazioni padre-figlio tra le coppie di vertici (1 arco).

Se y ∈ cammino da r a xy antenato, x discendente (più archi). L'antenato è proprio se xy.

Casi particolari:

  • radice: no padre
  • foglie: no figli
29 Proprietà
  • grado = numero massimo di figli;
  • profondità x = lunghezza del cammino da r (livello);
  • altezza h = profondità massima.

Alberi binariModifica

30 albero binario = albero con grado 2 (ogni nodo può avere 0, 1 o 2 figli). Definizione risorsiva:

  • insieme di nodi vuoto (foglia)
  • radice, sottoalbero sinistro, sottoalbero destro

31 albero binario completo = ogni nodo o è una foglia o ha 2 figli:

  • numero di foglie: 2^h
  • numero di nodi: \sum_{i=0}^h 2^i = 2 ^ {h+1} - 1[2]

32 albero binario bilanciato = tutti i cammini radice-foglia hanno uguale lunghezza (non c'è una foglia più vicina di altre alla radice). Un albero completo è sempre bilanciato (ma non viceversa).

33 albero binario quasi bilanciato = c'è al massimo uno scarto di una unità di lunghezza

NoteModifica

  1. massimale: è il più grande dei sottoinsiemi per cui vale questa proprietà, cioè quello che comprende più vertici connessi possibile.
  2. Si ricorda la serie geometrica: \sum_{i=0}^h x^i = {x ^ {h+1} - 1 \over x - 1}
Blue Glass Arrow RTL  3. Gli algoritmi di ordinamentoCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  5. La ricorsione

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