Cubierta de borde

En teoría de grafos , una cobertura de aristas de un grafo es un conjunto de aristas tal que cada vértice del grafo es un extremo de al menos una arista del conjunto. En informática , el problema de la cobertura mínima de aristas consiste en encontrar una cobertura de aristas de tamaño mínimo. Es un problema de optimización que pertenece a la clase de problemas de cobertura y puede resolverse en tiempo polinomial .

Formalmente, una cobertura de aristas de un grafo G es un conjunto de aristas C tal que cada vértice de G incide en al menos una arista de C. Se dice que el conjunto C cubre los vértices de G. La siguiente figura muestra ejemplos de coberturas de aristas en dos grafos (el conjunto C está marcado en rojo).

Un recubrimiento de aristas mínimo es aquel del tamaño más pequeño posible. El número de recubrimiento de aristas ρ ( G ) representa el tamaño de un recubrimiento de aristas mínimo. La siguiente figura muestra ejemplos de recubrimientos de aristas mínimos (el conjunto C está marcado en rojo).

Nótese que la figura de la derecha no es solo una cobertura de aristas, sino también un emparejamiento . En particular, es un emparejamiento perfecto : un emparejamiento M en el que cada vértice incide con exactamente una arista de M. Un emparejamiento perfecto (si existe) es siempre una cobertura de aristas mínima.

Se puede encontrar una cobertura de aristas mínima en tiempo polinomial hallando un emparejamiento máximo y extendiéndolo vorazmente hasta cubrir todos los vértices. ^{[ 1 ] [ 2 ]} En la siguiente figura, el emparejamiento máximo está marcado en rojo; las aristas adicionales que se añadieron para cubrir los nodos no emparejados están marcadas en azul. (La figura de la derecha muestra un grafo en el que el emparejamiento máximo es un emparejamiento perfecto ; por lo tanto, ya cubre todos los vértices y no se necesitaron aristas adicionales).

Por otro lado, el problema relacionado de encontrar una cobertura de vértices mínima es un problema NP-difícil . ^{[ 1 ]}

Al observar la imagen, ya resulta obvio por qué, para una cobertura mínima de borde dada${\displaystyle C}$y coincidencia máxima${\displaystyle M}$, dejando${\displaystyle c}$y${\displaystyle m}$sea ​​el número de aristas en${\displaystyle C}$y${\displaystyle M}$respectivamente, tenemos: ^{[ 3 ]}${\displaystyle |V|=c+m}$. En efecto,${\displaystyle C}$contiene una coincidencia máxima, por lo que los bordes de${\displaystyle C}$puede descomponerse entre el${\displaystyle m}$bordes de un ajuste máximo, cubriendo${\displaystyle 2m}$vértices y el${\displaystyle cm}$otros bordes que cubren cada uno otro vértice. Por lo tanto, como${\displaystyle C}$cubre todo el${\displaystyle |V|}$vértices, tenemos${\displaystyle |V|=2m+(cm)}$brindando la igualdad deseada.

• cobertura de vértices
• Recubrimiento de conjuntos : el problema del recubrimiento de aristas es un caso especial del problema del recubrimiento de conjuntos: los elementos del universo son vértices, y cada subconjunto cubre exactamente dos elementos.

• Weisstein, Eric W. "Edge Cover" . MathWorld .
• Garey, Michael R.; Johnson , David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, ISBN 0-7167-1045-5.