Топ-100
Indietro

ⓘ Ponte, teoria dei grafi. Nella teoria dei grafi, un ponte è un arco la cui eliminazione aumenta il numero di componenti connesse. Equivalentemente, un arco è un ..




Ponte (teoria dei grafi)
                                     

ⓘ Ponte (teoria dei grafi)

Nella teoria dei grafi, un ponte è 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 lanalisi della matrice di connessione.

                                     

1. 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.

                                     

2. Algoritmo per la ricerca di ponti

Un algoritmo con costo computazionale O | V | + | E | {\displaystyle O|V|+|E|} per trovare ponti in un grafo connesso fu inventato da Robert Tarjan nel 1974. Esiste inoltre una versione distribuita dellalgoritmo.

Algoritmo:

  • Creare un albero radicato T {\displaystyle T} dallalbero di copertura
  • Conta il numero di discendenti N D v {\displaystyle NDv} per quel nodo.
  • Per ogni nodo da v 1 {\displaystyle v_{1}} il nodo foglia dellalbero a 1 la radice esegui
  • Percorrere lalbero T {\displaystyle T} in pre-order e numerare i nodi. I nodi più vicini alla radice hanno un numero inferiore rispetto ai loro figli.
  • Per ogni w {\displaystyle w} tale che v → w {\displaystyle v\to w}: se L w ≥ w {\displaystyle Lw\geq w} and H w < w + N D w {\displaystyle Hw
  • Conta L v {\displaystyle Lv} e H v {\displaystyle Hv}
  • Trovare un albero di copertura minimo di G {\displaystyle G}