Pontes ou Arestas de corte
Summary
Pontes, também conhecidas como arestas de corte, são arestas em um grafo não orientado cuja remoção aumenta o número de componentes conexas do grafo.
Sendo o número de componentes conexas de um grafo , uma aresta e é considerada uma ponte se . Isso significa que o grafo resultante da remoção da aresta (denotado como ) tem mais partes desconectadas do que o grafo original.
Uma aresta é uma ponte se, e somente se, ela não faz parte de nenhum ciclo no grafo. Se uma aresta pertence a um ciclo, sua remoção não desconectará o grafo, pois ainda haverá um caminho alternativo entre seus vértices através do restante do ciclo.
Exemplo: Dado o grafo G abaixo:
As pontes do grafo G são: