Arista de corte

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Un grafo con 6 aristas de corte (marcadas en rojo).

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.

Véase también[editar]

Referencias[editar]