Algoritmi II

Un grafo $G$ è una coppia $(V,E)$ dove $V$ è un insieme di vertici ed $E$ un insieme di nodi; un grafo si dice

• semplice se ogni coppia di nodi è collegata con al massimo un arco, e non ci sono cappi
• diretto se gli archi sono orientati
• connesso se ogni coppia di nodi è collegata da una passeggiata
• fortemente connesso se per ogni coppia di vertici $x,y$ esiste un cammino da $x$ a $y$ e viceversa

Due nodi $x,y$ si dicono adiacenti ($x\sim y$) se sono collegati da un arco, e l'arco si dice incidente rispetto ai due nodi

Rappresentazione

Un grafo $G=(V,E)$ si può rappresentare tramite matrice di adiacenza o lista di adiacenza

Matrice di adiacenza

Siano $V_1,V_2,...,V_n$ i vertici del grafo, possiamo rappresentare il grafo come una matrice $v$ tale che

$$(v{)}_{ij}=\{\begin{array}{ll}1& \text{se }{V}_i\text{eˋ adiacente a }{V}_j\\ 0& \text{altrimenti}\end{array}$$

Per verificare se $V_i\sim V_j$ il costo è $O(1)$ la dimensione della matrice è $O(n^2)$ con

• $n=|V(G)|$

Lista di adiacenza

Siano $V_1,V_2,...,V_n$ i vertici del grafo, possiamo indicare per ogni nodo l'insieme dei suoi vicini

Per verificare se $V_i\sim V_j$ il costo è $O(n)$ la dimensione della matrice è $O(n+m)$, con

• $n=|V(G)|$
• $m=\sum _{v\in V(G)}\mathrm{deg}(v)=2|E(G)|$

Teoremi

Definizione

Una passeggiata in un grafo $(V,E)$ è definita come una sequenza $V_0{e}_1{V}_1{e}_2{V}_2{e}_3{V}_3$ dove $e_i$ collega $V_{i-1}$ a $V_i$

Definizione

Una passeggiata si dice euleriana se attraversa ogni arco del grafo esattamente una volta

Teorema di Eulero

$\exists$ una passeggiata euleriana $⟺$ il grafo è connesso ed esistono al massimo 2 vertici di grado dispari

Definizione

Un cammino è una passeggiata che non ripete vertici (quindi neanche archi)

Definizione

Un ciclo in un grafo è un sottografo connesso con ogni vertice di grado 2

Osservazione

Se $\exists$ una passeggiata da $x$ a $y⟹\exists$ un cammino da $x$ a $y$

si dimostra con l'algoritmo

DFS (depth first search)

#![allow(unused)]
fn main() {
            dfs(graph, y, visited)
        }
    }
}

fn dfs_iterative(graph: &[Vec<usize>], x: usize) -> Vec<bool> {
    let mut stack = Vec::from([x]);
    let mut visited = vec![false; graph.len()];
    let mut adjacent = vec![0; graph.len()];

    while let Some(&x) = stack.last() {
        if let Some(&y) = graph[x].get(adjacent[x]) {
            if !visited[y] {
                stack.push(y);
                visited[y] = true;
            }

            adjacent[x] += 1;
        } else {
            stack.pop();
}

Dimostrazione correttezza: bisogna dimostrare che

se $\exists$ un cammino da $x$ a $y⟹y\in \text{visited}$

per assurdo, supponiamo che $\exists y\mid x\to y\wedge y\notin \text{visited}$

Sia $i$ un indice $V_i\in \text{visited},V_{i+1}\notin \text{visited}$

$V_i\in \text{visited}⟹V_i$ è stato inserito nello stack $⟹$ ma se $V_i\in$ stack e $V_{i+1}\notin$ stack $⟹$ l'algoritmo non è stato eseguito correttamente (contraddizione!)

TODO: complessità $O(n+m)$

Definizione

L'albero di visita è un sottografo composto dagli archi che usiamo per raggiungere i vertici nuovi non ancora visitati

• è connesso
• è aciclico

Definizione

L'albero di visita di un grafo diretto è detto arborescenza

• diretto
• ogni arco orientato dalla radice alle foglie

Se $G$ è un graffo connesso $⟹\text{visited}$ contiene tutti i nodi del grafo

Se $G$ non è connesso $⟹\text{visited}$ è il componennte che contiene $X$

Ordine topologico

Consideriamo un progetto diviso in $X_1,X_2,...,X_n$ task, con dipendenze fra i vari task (Es. $X_1$ va eseguito dopo $X_2$ e $X_3$, e $X_3$ dopo $X_2$; in questo caso l'ordine sarebbe $X_2,X_3,X_1$)

Indicando i vertici con $X_1,X_2,...,X_n$ e gli archi con $(X_i,X_j)$ se $X_i$ dipende da $X_j$, una programmazione dei task corrisponde ad un ordine dei vertici con tutti gli archi da destra verso sinistra

Se il grafo ha un ciclo (diretto), non è possibile dare un ordine topologico

Dimostrazione

Suppponiamo per assurdo che esiste un tale ordine, allora uno dei vertici deve essere per forza l'ultimo nell'ordine; ma essendo ciclico esiste un arco che va da sinistra verso destra da uno dei vertici "centrali" della sequenza all'ultimo vertice, quindi tale ordine non esiste.

Definizione

Un grafo diretto ha un ordine topologico se $\exists$ un ordine deivertici con tutti gli ordini degli archi da destra verso sinistra

Proposizione

Se un grafo diretto ha la proprietà che ogni vertice ha almeno un arco uscente $⟹\exists$ un ciclo

stessa dimostrazione dell'algoritmo del primo giorno: se ogni vertice ha un arco uscente e i vertici sono finiti, alora prima o poi dovrà tornare... (creare un ciclo)

L'implicazione $⟸$ non è vera!

Corollario

Se \notexists un ciclo $⟹\exists$ un nodo senza archi uscenti

Soluzione naive

TODO: algoritmo $O(n(n+m))$ per trovare l'ordine topologico!

Soluzione con DFS