Vai al contenuto principale
← OlimpiApp Olimpico

Informatica · Grafi

Componenti senza i ponti in un grafo con due triangoli

Un grafo non orientato connesso ha vertici $\{A, B, C, D, E, F, G\}$ e archi AB, BC, CA, CD, DE, EF, FD, EG. Se si rimuovessero simultaneamente tutti gli archi che sono ponti (cioè la cui rimozione singola disconnetterebbe il grafo), in quante componenti connesse si spezzerebbe il grafo risultante?