Ponte (teoria dei grafi)

Da Wikipedia, l'enciclopedia libera.
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[modifica | modifica wikitesto]

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]

Algoritmo per la ricerca di ponti[modifica | modifica wikitesto]

Un algoritmo con costo computazionale 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
  2. Creare un albero radicato dall'albero di copertura
  3. Percorrere l'albero 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 (il nodo foglia dell'albero) a 1 (la radice) esegui:
    1. Conta il numero di discendenti per quel nodo.
    2. Conta e
    3. 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[modifica | modifica wikitesto]

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 [4]

Note[modifica | modifica wikitesto]

  1. ^ Cycle double cover
  2. ^ "A note on finding the bridges of a graph", Robert Endre Tarjan, Information Processing Letters, Aprile 1974 pp160-161.
  3. ^ David Pritchard
  4. ^ 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).

Bibliografia[modifica | modifica wikitesto]

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