thumb|Un grafo con 6 ponti (marcati in rosso) thumb|upright=0.6|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 per trovare ponti in un grafo connesso fu inventato da Robert Tarjan nel 1974."A note on finding the bridges of a graph", Robert Endre Tarjan, Information Processing Letters, Aprile 1974 pp160-161. Esiste inoltre una versione distribuita dell'algoritmo.
Algoritmo: Trovare un albero di copertura minimo di Creare un albero radicato dall'albero di copertura Percorrere l'albero in pre-order e numerare i nodi. I nodi più vicini alla radice hanno un numero inferiore rispetto ai loro figli. Per ogni nodo da (il nodo foglia dell'albero) a 1 (la radice) esegui: Conta il numero di discendenti per quel nodo. Conta e Per ogni tale che : se and allora è un ponte.
Definizioni: Un arco tra il nodo e che non appartiene all'albero è indicato da . Un arco dell'albero con come padre è indicato da .
dove è il nodo padre di .
è il numero dei discendenti di (incluso se stesso) nell'albero di copertura radicato.
e sono le etichette dei nodi con l'etichetta di preordine minore e maggiore raggiungibile da attraverso il sottoalbero con radice , e al massimo un arco che non appartiene all'albero.
Questo algoritmo funziona perché , e possono tutti essere calcolati per un nodo fornito, e di conseguenza conosciamo i loro valori su tutto il sottoalbero radicato in . Inoltre, se e solo se l'arco è un ponte, allora è chiaro che nel sottoalbero radicato in , deve essere impossibile raggiungere qualunque nodo che non è un discendente di . Questo è facile da verificare perché il sottoalbero radicato in (cioè tutti i discendenti di w) consiste di tutti i nodi quindi possiamo semplicemente controllare se sono in questo insieme oppure no per verificare se un arco è un ponte.
Ponti negli alberi Un arco di un albero è un ponte in se e solo se il grado dei nodi e è maggiore di 1. I ponti sono anche definiti per i grafi orientati Rao, S.B.; Ramachandra Rao, A. Il numero di ponti e punti di articolazione in un grafo fortemente orientato. (English) Acta Math. Acad. Sci. Hung. 22, 411-421 (1972).
Note
Bibliografia Béla Bollobás, Modern graph theory, GTM 184, Springer Verlag, 1998. Page 6.
Categoria:Connettività dei grafi