Revestimiento de costillas
Una cubierta de borde de un gráfico es un conjunto de bordes C tal que cada vértice del gráfico incide en al menos un borde desde C .
La siguiente figura muestra la cobertura de los bordes de dos gráficos.
La cubierta de borde más pequeña es la cubierta de borde más pequeña. El número de bordes en la cubierta de borde más pequeña de un gráfico se denomina número de cubierta de borde y se denota por (en el libro de Swami, Thulaliramana - ). La siguiente figura muestra ejemplos de las cubiertas de borde más pequeñas.
Tenga en cuenta que la portada del gráfico de la derecha no es solo una portada de borde, sino también un archivo . Además, este emparejamiento es un emparejamiento perfecto : cada vértice en él incide exactamente en un borde del emparejamiento. Una combinación perfecta (si existe) es siempre la cubierta de borde más pequeña.
La tarea de encontrar la cobertura de borde más pequeña es un problema de optimización , pertenece a la clase de problemas de cobertura y se puede resolver en tiempo polinomial .
Ejemplos
- Si no hay vértices aislados en el gráfico (es decir, vértices con grado 0), entonces el conjunto de todos los bordes es una cubierta de borde (¡pero no necesariamente el más pequeño!). Si hay vértices aislados, no hay cobertura de borde en este gráfico.
- El grafo bipartito completo K m , n tiene el número de cobertura de borde max( m , n ).
Propiedades
- De acuerdo con la segunda identidad de Gallai , en un gráfico sin vértices aislados, el número total de aristas en la cubierta de borde más pequeña y la coincidencia más grande es igual al número de vértices en el gráfico.
Algoritmos
La cobertura de borde más pequeña se puede encontrar en tiempo polinomial al encontrar la coincidencia más grande y luego agregar bordes usando un algoritmo codicioso para cubrir los vértices restantes [1] [2] . En la siguiente figura, la coincidencia más grande se muestra en rojo. Los bordes adicionales que se agregan para cubrir los vértices descubiertos se muestran en azul (en el gráfico de la derecha, la coincidencia más grande es una coincidencia perfecta en la que todos los vértices ya están cubiertos, por lo que no hay necesidad de bordes adicionales).
Véase también
- Problema de cobertura de vértices
- El problema de cobertura de conjuntos : el problema de cobertura de bordes es un caso especial del problema de cobertura de conjuntos: los elementos de la población son vértices y cada subconjunto cubre exactamente dos elementos.
Notas
- ↑ Garey y Johnson ( Garey, Johnson 1979 ), página 79, usan la cobertura de aristas y la cobertura de vértices como ejemplo de un par de problemas similares, uno de los cuales puede resolverse en tiempo polinomial y el otro es NP-difícil. Consulte también la página 190.
- ↑ Lawler, 2001 , pág. 222–223.
Literatura
- Weisstein, Eric W. Edge Portada (inglés) en el sitio web de Wolfram MathWorld .
- Michael R. Garey, David S. Johnson. Computadoras e intratabilidad: una guía para la teoría de la integridad NP . - WH Freeman, 1979. - ISBN 0-7167-1045-5 .
- Eugene L. Lawler. Optimización combinatoria: redes y matroides. - Publicaciones de Dover, 2001. - ISBN 978-0-486-41453-9 .
- M. Swami, K. Thulasiraman. 9.2 Revestimientos de cantos // Grafos, redes y algoritmos. - M. : "Mir", 1984. - S. 179-180.