Pontes ou Arestas de corte §

---

Abstract

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:

Referências §

---

Teoria dos Grafos - Pontes e pontos de articulação