Cobertura d'arestes
En teoria de Grafos , una cobertura d'arestes d'un grafo és un conjunt d'arestes a on cada vèrtiç del grafo és incident en a lo manco en una aresta del conjunt. En ciències de la computació, el problema de la cobertura mínima d'aresta és el problema de trobar una cobertura d'arestes de tamany mínim. Est és un problema d'optimisació que pertany a la classe de problemes de cobertura i pot resoldre's en temps polinomial.
Definició
Formalment, una cobertura d'arestes sobre el grafo G és un conjunt d'arestes C a on cada vèrtiç és incident en a lo manco una aresta en C. Es diu que el conjunt C cobrix els vèrtiços de G. La següent image mostra eixemples de cobertura d'arestes en dos grafos.
Una cobertura d'arestes mínima és una cobertura d'arestes del menor tamany possible. El número de cubrimiento d'arestes és el tamany d'una cobertura d'arestes mínima. La següent image mostra eixemples de la cobertura d'arestes mínima.
Notar que en la figura de la dreta no solament és una cobertura d'arestes si no també un matching. En particular, és un matching perfecte: un maching M en a on cada vèrtiç és incident en exactament una aresta en M. Un matching perfecte és sempre una cobertura d'arestes mínima.
Vore també
Referències
- Edge Cover en MathWorld.
- .
- Este artícul conté una traducció derivada de «Cobertura de aristas» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.