Cubierta de borde
En teoría de grafos , una cobertura de aristas de una gráfica es un conjunto de aristas de modo que cada vértice de la gráfica incide al menos en una arista del conjunto. En informática , el problema de la 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 borde de un gráfico G es un conjunto de aristas C de tal manera que cada vértice en G es incidente con al menos un borde en C . El conjunto C se dice que es cubrir 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, se trata de una coincidencia perfecta : un juego M en el que cada vértice es incidente con exactamente una ventaja en M . Una combinación perfecta (si existe) es siempre una cobertura de borde mínima.
Se puede encontrar una cobertura 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, una coincidencia máxima está marcada con rojo; los bordes adicionales que se agregaron para cubrir los nodos no coincidentes están marcados con 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).