Ponte (teoria dei grafi)

Un grafo con 6 ponti (marcati in rosso)

Un grafo non orientato senza ponti

Nella teoria dei grafi, un ponte (conosciuto anche come bridge, cut-edge, cut arc o istmo) è un arco la cui eliminazione aumenta il numero di componenti connesse. Equivalentemente, un arco è un ponte se e solo se non è contenuto in nessun ciclo.

Un grafo senza ponti è equivalente a un grafo con grado di connettività pari a 2 per ogni componente non banale. Un ponte può essere individuato anche tramite l'analisi della matrice di connessione.

La congettura Cycle double cover

Un importante problema aperto che riguarda i ponti è la congettura cycle double cover proposta da Seymour e Szekeres (1978 e 1979, indipendentemente), la quale dice che ogni grafo senza ponti ammette un insieme di cicli che contengono ogni arco esattamente due volte.

Algoritmo per la ricerca di ponti

Un algoritmo con costo computazionale $O(|V|+|E|)$ per trovare ponti in un grafo connesso fu inventato da Robert Tarjan nel 1974. Esiste inoltre una versione distribuita dell'algoritmo.

Algoritmo:

1. Trovare un albero di copertura minimo di $G$
2. Creare un albero radicato $T$ dall'albero di copertura
3. Percorrere l'albero $T$ in pre-order e numerare i nodi. I nodi più vicini alla radice hanno un numero inferiore rispetto ai loro figli.
4. Per ogni nodo da $v_1$ (il nodo foglia dell'albero) a 1 (la radice) esegui:
   1. Conta il numero di discendenti $ND(v)$ per quel nodo.
   2. Conta $L(v)$ e $H(v)$
   3. Per ogni $w$ tale che $v\to w$: se $L(w)\ge w$ and $H(w)<w+ND(w)$ allora $(v,w)$ è un ponte.

Definizioni: Un arco tra il nodo $v$ e $w$ che non appartiene all'albero è indicato da $v--w$. Un arco dell'albero con $v$ come padre è indicato da $v\to w$.

$ND(v)=1+\sum _{v\to w}ND(w)$ dove $v$ è il nodo padre di $w$.

$ND(v)$ è il numero dei discendenti di $v$(incluso se stesso) nell'albero di copertura radicato.

$L(v)=\min (\{v\}\cup \{L(w)\mid v\to w\}\cup \{w\mid v--w\})$

$H(v)=\max (\{v\}\cup \{H(w)\mid v\to w\}\cup \{w\mid v--w\})$

$L(v)$ e $H(v)$ sono le etichette dei nodi con l'etichetta di preordine minore e maggiore raggiungibile da $v$ attraverso il sottoalbero con radice $v$, e al massimo un arco che non appartiene all'albero.

Questo algoritmo funziona perché $LD(v)$, $H(v)$ e $L(v)$ possono tutti essere calcolati per un nodo $v$ fornito, e di conseguenza conosciamo i loro valori su tutto il sottoalbero radicato in $v$. Inoltre, se e solo se l'arco $v\to w$ è un ponte, allora è chiaro che nel sottoalbero radicato in $w$, deve essere impossibile raggiungere qualunque nodo che non è un discendente di $w$. Questo è facile da verificare perché il sottoalbero radicato in $w$ (cioè tutti i discendenti di w) consiste di tutti i nodi $\{w,w+1,\dots ,w+ND(w)-1\}$ quindi possiamo semplicemente controllare se $L(w),H(w)$ sono in questo insieme oppure no per verificare se un arco è un ponte.

Ponti negli alberi

Un arco $E=uv$ di un albero $T$ è un ponte in $T$ se e solo se il grado dei nodi $u$ e $v$ è maggiore di 1. I ponti sono anche definiti per i grafi orientati

Bibliografia

• Béla Bollobás, Modern graph theory, GTM 184, Springer Verlag, 1998. Page 6.
• Template:Cita pubblicazione