Teoria dei Grafi

Teorema: l'algoritmo di Prim calcola correttamente un minimo albero ricoprente.

Dimostrazione: sfruttando il teorema(1) è sufficiente dimostrare che il generico passo dell'algoritmo di Prim è una applicazione della regola del taglio. Infatti, sia l'albero blu T prima del generico passo. L'algoritmo fino ad ora ha colorato di blu tutti e soli gli archi di T. Considerando il taglio che separa T dal resto del grafo: l'arco scelto dal passo di Prim è esattamente l'arco dal costo minimo in tale taglio per cui risulta una colorazione in base alla regola del taglio.

Foresta: è un grafo non orientato nel quale due vertici qualsiasi sono connessi al più da un cammino. Una foresta risulta costituita da una unione disgiunta di alberi che costituiscono le componenti connesse massimali del grafo.

Algoritmo di Kruskal

L'algoritmo di Kruskal è

Un algoritmo greedy per il calcolo del minimo albero ricoprente per un grafo. Nell'algoritmo di Kruskal gli archi blu costituiscono una foresta di alberi. Durante la sua esecuzione, l'algoritmo di Kruskal mantiene la foresta di alberi blu, inizialmente costituita da alberi disgiunti ciascuno dei quali composto da un solo nodo. Per ciascun arco del grafo si applica il passo:

1. Se l'arco ha entrambi gli estremi nello stesso albero blu, coloralo di rosso.
2. Altrimenti coloralo di blu.

Quando l'algoritmo avrà esaminato tutti gli archi del grafo restituirà l'albero formato dagli archi blu.

Pseudocodice:

public Grafo<ArcoPesato> kruskal(){ // theta( m n) || (union find) theta(m lg n)
    ArcoPesato[] archi = generaArchiOrdinati(); // theta(m lg n) || theta(n^2 + m lg n)
    int inseriti = 0;
    GrafoLista<ArcoPesato> albero = new GrafoLista<ArcoPesato>(n());// creare union find - theta(n)//theta (m + n lg n)
    for(int i=0; i < archi.length; i++){
        if(inseriti == n()-1) break;
        ArcoPesato arco = archi[i];
        int u = arco.getNodoU();
        int v = arco.getNodoV();
        if(!albero.connessi(u, v)){
            albero.aggiungiArco(arco);
            albero.union(u, v);
            inseriti++;
        }
    }
    return albero;
}

Una sua implementazione in java:

public class GrafoLista<T> implements Grafo<T> {
    private int n;
    private List<List<Arco<T>>> adiacenze;
    
    public GrafoLista(int n){
        this.n = n;
        adiacenze = new ArrayList<>();
        for(int i=0; i < n; i++){
            adiacenze.add(new ArrayList<>());
        }
    }
    
    public void aggiungiArco(Arco<T> arco){
        int u = arco.getNodoU();
        int v = arco.getNodoV();
        adiacenze.get(u).add(arco);
        adiacenze.get(v).add(arco);
    }
    
    public boolean connessi(int u, int v){
        for(Arco<T> arco : adiacenze.get(u)){
            if(arco.getNodoU() == v || arco.getNodoV() == v){
                return true;
            }
        }
        return false;
    }
    
    public void union(int u, int v){
        // implementazione dell'union find
    }
    
    // altre implementazioni dei metodi dell'interfaccia Grafo
}

(i<archi.length)&& (inseriti<n()-1); i++){ // m volte
    <List<Integer> lista = albero.depthFirstSearch(archi[i].getIn()); // theta(n) || theta (n^2)
    if (!lista.contains(archi[i].getFin())){ // theta(1)
        albero.aggiungiArco(archi[i]); // theta(1)
        inseriti++; // theta(1)
    }
}
if (inseriti==n()-1)
    return albero;
return null;

Teorema : L'algoritmo di Kruskal calcola correttamente un minimo albero ricoprente.

Dimostrazione : in base al teorema(1) è sufficiente dimostrare che l'algoritmo di Kruskal è una applicazione del metodo goloso. Ricordando che gli archi vengono esaminati in ordine non decrescente, quando l'algoritmo di Kruskal esamina l'arco esso non è stato ancora colorato mentre tutti gli archi di tale che sono stati già colorati. Sie G costo(e costo(e)ha che:

Se l'arco ha entrambi gli estremi nello stesso albero blu, allora induce un ciclo in tale e albero blu: tale ciclo

non contiene archi rossi ed è l'arco di costo massimo in tale ciclo. Allora l'algoritmo colora di rosso tale arco in base alla regola del ciclo. Se l'arco ha gli estremi in due diversi alberi, allora attraversa un taglio che separa tali alberi. Osserviamo che è il primo arco che attraversa tale taglio ad essere considerato dall'algoritmo: è quindi l'arco di costo minimo in un taglio che non contiene archi blu e l'algoritmo di Kruskal colora correttamente di blu in base alla regola del taglio.

Cammino minimo= (N,Definizione : Sia un grafo orientato pesato sugli archi, dove la funzione di G E, λ): →peso è tale che . Un cammino (di costo) minimo fra una coppia di vertici λ E R x y* connessi in è un cammino che ha un costo minore o uguale a quello di ogni altro G πx,y cammino tra gli stessi vertici, cioè tale che πx,y * ) = min )λ(π λ(πx,yx,y ⊆Gπ

Nell'associare ad ogni vertice un attributo d(s, v) chiamata stima di cammino minimo che costituisce un limite superiore al peso di cammino minimo tra il nodo s e la radice. Tale stima sarà man mano diminuita ripetutamente fino a convergere con il reale peso del cammino minimo tra s e v.

GLi attributi sono inizializzati a −∞.

Pseudocodice:

Algoritmo di Dijkstra

L'algoritmo di Dijkstra è un algoritmo di calcolo di un albero di cammini minimi per un grafo G = (N, E, λ) dove la funzione costo è definita. Sia T un albero di cammini minimi radicato nel nodo s, ma tale che non includa tutti i vertici raggiungibili da s. Allora l'arco con costo minimo (v, u) che minimizza la quantità d(s, v) + λ(v, u) appartiene a un cammino minimo da s a u.

Dimostrazione: Supposto per assurdo che l'arco non appartenga a un cammino minimo.

x) λ(x, y) d(s, u) λ(u, v)e allora ∗ ∗= + + ) ≥ + + )d(s, v) d(s, x) λ(x, y) λ(π d(s, u) λ(u, v) λ(πyv yvTeoria dei Grafi 13∗ ) ≥ 0Infine, poichè gli archi sono non negativi ho . Questo ci porta allaλ(πyvcontraddizione: □∗= ) ≥ + >d(s, v) λ(π d(s, u) λ(u, v) d(s, v)svDetto ciò Dijkstra per calcolare l'albero dei cammini del grafo , posto che abbia nodi,G G n(n − 1)applica volte il seguente passo:Segli un arco con e che minimizza(u, ∈ ) ∈ )/v) u N(T v N(Teffettua il rilassamento+ = +d(s, u) λ(u, v), d(s, v) d(s, u) λ(u, v),e aggiungilo a T.Pseudocodice:Implementazione:public List<Double> dijkstra(int nodoPartenza){ Double[] distanze=new Double[n];for(int i=0;i<n;i++)distanze[i]=Double.POSITIVE_INFINITY;boolean[] raggiunti=new boolean[n];for(int i=0;i<n;i++)raggiunti[i]=false;distanze[nodoPartenza]=0.0;int