Arista de corte
En teoría de grafos, un puente, arista de corte o istmo es una arista que al ser eliminada en un grafo incrementa el número de componentes conexas de éste. Equivalentemente, una arista es un puente si y sólo si no está contenida en ningún ciclo.
Un grafo sin puentes es equivalente a un grafo conexo con conectividad 2.
Un importante problema abierto que involucra puentes es el llamado Cycle Double Cover Conjecture ("Conjetura del Ciclo de Doble Cobertura"),[1] propuesto por Seymour y Szekeres (1978 y 1979, independientemente), que establece que todo grafo sin puentes admite un conjunto de ciclos que contiene cada arista exactamente dos veces.
Véase también
Referencias
- Béla Bollobás, Modern graph theory, GTM 184, Springer Verlag, 1998. Página 6.
| Control de autoridades |
|
|---|
Datos: Q2532492