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 .
Definición
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 que cubre el borde es el tamaño de un revestimiento 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.
Ejemplos de
- El conjunto de todas las aristas es una cobertura de aristas, asumiendo que no hay vértices de grado 0.
- El gráfico bipartito completo K m , n tiene un número máximo de cobertura de bordes ( m , n ).
Algoritmos
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 cubrir todos los vértices. [1] [2] En la siguiente figura, una coincidencia máxima está marcada con rojo; los bordes adicionales que se agregaron para cubrir 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).
Por otro lado, el problema relacionado de encontrar una cobertura de vértice más pequeña es un problema NP-difícil . [1]
Ver también
- Cubierta de vértice
- Cobertura del conjunto : el problema de la cobertura del borde es un caso especial del problema de la cobertura del conjunto: los elementos del universo son vértices y cada subconjunto cubre exactamente dos elementos.
Notas
- ↑ a b Garey y Johnson (1979) , p. 79, utiliza la cobertura de aristas y la cobertura de vértices como un ejemplo de un par de problemas similares, uno de los cuales puede resolverse en tiempo polinomial mientras que el otro es NP-difícil. Ver también p. 190.
- ^ Lawler, Eugene L. (2001), Optimización combinatoria: redes y matroides , Publicaciones de Dover, págs. 222-223, ISBN 978-0-486-41453-9.
Referencias
- Weisstein, Eric W. "Cubierta de borde" . MathWorld .
- Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 0-7167-1045-5.