Ponte (teoria dei grafi)

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.

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.^[1]

Un algoritmo con costo computazionale ${\displaystyle O(|V|+|E|)}$ per trovare ponti in un grafo connesso fu inventato da Robert Tarjan nel 1974.^[2] Esiste inoltre una versione distribuita dell'algoritmo. ^[3]

Algoritmo:

1. Trovare un albero di copertura minimo di ${\displaystyle G}$
2. Creare un albero radicato ${\displaystyle T}$ dall'albero di copertura
3. Percorrere l'albero ${\displaystyle 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 ${\displaystyle v_{1}}$ (il nodo foglia dell'albero) a 1 (la radice) esegui:
   1. Conta il numero di discendenti ${\displaystyle ND(v)}$ per quel nodo.
   2. Conta ${\displaystyle L(v)}$ e ${\displaystyle H(v)}$
   3. Per ogni ${\displaystyle w}$ tale che ${\displaystyle v\to w}$: se ${\displaystyle L(w)\geq w}$ and ${\displaystyle H(w)<w+ND(w)}$ allora ${\displaystyle (v,w)}$ è un ponte.

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

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

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

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

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

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

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

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

• Béla Bollobás, Modern graph theory, GTM 184, Springer Verlag, 1998. Page 6.
• Robert Endre Tarjan, A note on finding the bridges of a graph, in Information Processing Letters, vol. 2, n. 6, pp. 160–161, DOI:10.1016/0020-0190(74)90003-9.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica