En teoría de Grafos , una cobertura de aristas de un grafo es un conjunto de aristas donde cada vértice del grafo es incidente en al menos en una arista del conjunto. En ciencias de la computación, el problema de la cobertura mínima de arista es el problema de encontrar una cobertura de aristas de tamaño mínimo. Este es un problema de optimización que pertenece a la clase de problemas de cobertura y puede resolverse en tiempo polinomial.
Definición
Formalmente, una cobertura de aristas sobre el grafo G es un conjunto de aristas C donde cada vértice es incidente con al menos una arista en C. Se dice que el conjunto Ccubre los vértices de G. La siguiente imagen muestra ejemplos de cobertura de aristas en dos grafos.
Una cobertura de aristas mínima es una cobertura de aristas del menor tamaño posible. El número de cubrimiento de aristas es el tamaño de una cobertura de aristas mínima. La siguiente imagen muestra ejemplos de la cobertura de aristas mínima.
Notar que en la figura de la derecha no solo es una cobertura de aristas si no también un matching. En particular, es un matching perfecto: un maching M en donde cada vértice es incidente con exactamente una arista en M. Un matching perfecto es siempre una cobertura de aristas mínima.
cobertura, aristas, teoría, grafos, cobertura, aristas, grafo, conjunto, aristas, donde, cada, vértice, grafo, incidente, menos, arista, conjunto, ciencias, computación, problema, cobertura, mínima, arista, problema, encontrar, cobertura, aristas, tamaño, míni. En teoria de Grafos una cobertura de aristas de un grafo es un conjunto de aristas donde cada vertice del grafo es incidente en al menos en una arista del conjunto En ciencias de la computacion el problema de la cobertura minima de arista es el problema de encontrar una cobertura de aristas de tamano minimo Este es un problema de optimizacion que pertenece a la clase de problemas de cobertura y puede resolverse en tiempo polinomial Definicion EditarFormalmente una cobertura de aristas sobre el grafo G es un conjunto de aristas C donde cada vertice es incidente con al menos una arista en C Se dice que el conjunto C cubre los vertices de G La siguiente imagen muestra ejemplos de cobertura de aristas en dos grafos Una cobertura de aristas minima es una cobertura de aristas del menor tamano posible El numero de cubrimiento de aristas r G displaystyle rho G es el tamano de una cobertura de aristas minima La siguiente imagen muestra ejemplos de la cobertura de aristas minima Notar que en la figura de la derecha no solo es una cobertura de aristas si no tambien un matching En particular es un matching perfecto un maching M en donde cada vertice es incidente con exactamente una arista en M Un matching perfecto es siempre una cobertura de aristas minima Vease tambien EditarCobertura de vertices Problema de la cobertura de verticesReferencias EditarWeisstein Eric W Edge Cover En Weisstein Eric W ed MathWorld en ingles Wolfram Research Garey Michael R Johnson David S 1979 Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman ISBN 0 7167 1045 5 Datos Q594001 Obtenido de https es wikipedia org w index php title Cobertura de aristas amp oldid 144550171, wikipedia, wiki, leyendo, leer, libro, biblioteca,
