Cubierta de borde
En la teoría de grafos , una cubierta de borde de un gráfico es un conjunto de bordes tal que cada vértice del gráfico incide en al menos un borde del conjunto. En informática , el problema de cobertura de borde mínima es el problema de encontrar una cobertura de borde 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, una cubierta de arista de un grafo G es un conjunto de aristas C tal que cada vértice en G incide con al menos una arista en C. Se dice que el conjunto C cubre los vértices de G. La siguiente figura muestra ejemplos de revestimientos de bordes en dos gráficos.
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 es el tamaño de un recubrimiento de borde mínimo. La siguiente figura muestra ejemplos de recubrimientos de bordes mínimos.
Tenga en cuenta que la figura de la derecha no es solo una cubierta de borde, sino también una coincidencia . En particular, es un emparejamiento perfecto : un M coincidente en el que cada vértice incide con exactamente una arista en M. Un emparejamiento perfecto (si existe) es siempre un mínimo recubrimiento de cantos.
Se puede encontrar una cubierta de borde más pequeña en tiempo polinomial encontrando una coincidencia máxima y extendiéndola con avidez para que todos los vértices estén cubiertos. [1] [2] En la siguiente figura, se marca en rojo una coincidencia máxima; los bordes adicionales que se agregaron para cubrir los nodos no coincidentes están marcados 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 bordes adicionales).