Arista de corte
De Wikipedia, la enciclopedia libre
En teoría de grafos, un puente, arista de corte o istmo es una arista que al eliminarse de un grafo incrementa el número de componentes conexos de éste. Equivalentemente, una arista es un puente si y sólo si no está contenido 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.
[editar] Véase también
[editar] Referencias
- Béla Bollobás, Modern graph theory, GTM 184, Springer Verlag, 1998. Página 6.
