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 sorgente]

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 sorgente]

Un algoritmo con costo computazionale 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 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) \geq 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, \ldots, 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[modifica | modifica sorgente]

Un arco E = u v 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 [4]

Note[modifica | modifica sorgente]

  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 sorgente]

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