Hispanopedia WikiEn matemáticas , una cobertura de ciclo de vértice (comúnmente llamada simplemente cobertura de ciclo ) de un grafo G es un conjunto de ciclos que son subgrafos de G y contienen todos los vértices de G.
Si los ciclos de la cubierta no tienen vértices en común, la cubierta se llama cubierta disjunta de vértices o, a veces, simplemente cubierta de ciclo disjunta . Esto a veces se conoce como cubierta de ciclo de vértice exacta . En este caso, el conjunto de los ciclos constituye un subgrafo generador de G. Una cubierta de ciclo disjunta de un grafo no dirigido (si existe) se puede encontrar en tiempo polinomial transformando el problema en un problema de búsqueda de una correspondencia perfecta en un grafo más grande. [1] [2]
Si los ciclos de la cubierta no tienen aristas en común, la cubierta se denomina cubierta de aristas disjuntas o simplemente cubierta de ciclo disjunto .
Existen definiciones similares para los dígrafos , en términos de ciclos dirigidos. Encontrar una cubierta de ciclo disjunto de vértices de un grafo dirigido también se puede realizar en tiempo polinomial mediante una reducción similar a la coincidencia perfecta . [3] Sin embargo, agregar la condición de que cada ciclo debe tener una longitud de al menos 3 hace que el problema sea NP-difícil . [4]
Propiedades y aplicaciones
Permanente
El permanente de una matriz (0,1) es igual al número de ciclos disjuntos de vértices de un grafo dirigido con esta matriz de adyacencia . Este hecho se utiliza en una prueba simplificada que muestra que calcular el permanente es #P-completo . [5]
Cubiertas de ciclo disjunto mínimo
Los problemas de encontrar un ciclo disjunto de vértices y aristas con un número mínimo de ciclos son NP-completos . Los problemas no están en la clase de complejidad APX . Las variantes para dígrafos tampoco están en APX. [6]
Véase también
- Cobertura de ciclo de aristas , una colección de ciclos que cubren todas las aristas de G
Referencias
- ^ David Eppstein . "Particionar un gráfico en ciclos nodales disjuntos".
- ^ Tutte, WT (1954), "Una breve demostración del teorema del factor para grafos finitos" (PDF) , Revista Canadiense de Matemáticas , 6 : 347–352, doi :10.4153/CJM-1954-033-3, MR 0063008, S2CID 123221074.
- ^ https://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (problema 1)
- ^ Garey y Johnson, Computadoras e intratabilidad, GT13
- ^ Ben-Dor, Amir y Halevi, Shai. (1993). "El permanente cero-uno es #P-completo, una prueba más simple". Actas del 2º Simposio de Israel sobre Teoría y Sistemas de Computación , 108-117.
- ^ Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximabilidad (1999) ISBN 3-540-65431-3 p.378, 379, citando a Sahni, Sartaj ; Gonzalez, Teofilo (1976), "Problemas de aproximación P-completos" (PDF) , Journal of the ACM , 23 (3): 555–565, doi :10.1145/321958.321975, MR 0408313, S2CID 207548581 .