En teoría de grafos , una cobertura de aristas de un grafo es un conjunto de aristas tal que cada vértice del grafo incide en al menos una arista del conjunto. En informática , el problema de cobertura mínima de aristas es el problema de 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 se puede resolver en tiempo polinomial .
Formalmente, un recubrimiento de aristas de un grafo G es un conjunto de aristas C tales que cada vértice de G incide con al menos una arista de C. Se dice que el conjunto C cubre los vértices de G. La siguiente figura muestra ejemplos de recubrimientos de aristas en dos grafos (el conjunto C está marcado en rojo).
Un recubrimiento de borde mínimo es un recubrimiento de borde del tamaño más pequeño posible. El número de recubrimiento de borde ρ ( G ) es el tamaño de un recubrimiento de borde mínimo. La siguiente figura muestra ejemplos de recubrimientos de borde mínimos (nuevamente, el conjunto C está marcado en rojo).
Nótese que la figura de la derecha no es solo un cubrimiento de aristas sino también un emparejamiento . En particular, es un emparejamiento perfecto : un emparejamiento M en el que cada vértice incide exactamente con una arista en M. Un emparejamiento perfecto (si existe) es siempre un cubrimiento de aristas mínimo.
Se puede encontrar una cobertura de aristas más pequeña en tiempo polinomial al encontrar una coincidencia máxima y extenderla con avidez para que todos los vértices estén cubiertos. [1] [2] En la siguiente figura, una coincidencia máxima está marcada en rojo; las aristas adicionales que se agregaron para cubrir los nodos no coincidentes están marcadas en azul. (La figura de la derecha muestra un gráfico en el que una coincidencia máxima es una coincidencia perfecta ; por lo tanto, ya cubre todos los vértices y no se necesitaron aristas adicionales).
Por otra parte, el problema relacionado de encontrar la cobertura de vértice más pequeña es un problema NP-difícil . [1]
Mirando la imagen ya se hace obvio por qué, para una cobertura de aristas mínima dada y una coincidencia máxima , siendo y el número de aristas en y respectivamente, tenemos: [3] . De hecho, contiene una coincidencia máxima, por lo que las aristas de se pueden descomponer entre las aristas de una coincidencia máxima, que cubren vértices, y las otras aristas que cubren cada una otro vértice. Por lo tanto, como cubre todos los vértices, tenemos dando la igualdad deseada.
