El equipo esta formado por:
- Karen Alduncin Ibarra (calif. esperada: 100)
- Kevin Darío Pérez Cuéllar (calif. esperada: 90)
- Ricardo Lopez Porras (calif. esperada: 80)
El Lenguaje que utilizaremos será C y Java.
El problema a analizar será vertex cover (cobertura de vértices) que es un problema NP-completo.
Este problema es muy utilizado en teoría de complejidad computacional para probar la pertenencia a la clase NP-Hard de otros problemas computacionales difíciles.
Por ejemplo:
- Clique
- Set covering
- Circuitos Hamiltonianos
La cobertura de vértices de un grafo no dirigido G = (V,E) es unsubconjunto S de V (el conjunto de vértices) tal que para cada aristaab del conjunto E, ya sea el vértice a o b pertenece a S.
Suponga un grafo no dirigido G = (V, E). Una cubierta de vértices para G es un subconjunto de vértices V' tal que todo lado de E es incidente en al menos un vértice de V'.
El problema de la cobertura de vértices consiste en determinar una cobertura con el mínimo número de vértices.
El problema de poner guardias en los extremos (vértices) de los pasillos (lados) para cubrirlos todos es un problema de cubierta de vértices; el problema abastecer una colonia con el menor número de luminarias también lo es.
Cada vértice cubre su arco incidente y se trata de buscar el conjunto de vértices que cubra todos los arcos. La idea es encontrar la cobertura de vértices de tamaño mínimo.
En el siguiente grafo, {1,3,5,6} es una cobertura de vértices de tamaño 4. Sin embargo, esta no es la cobertura mínima, porque existen las coberturas de vértices {245} {124} y,ambas de tamaño 3 que satisfacen la cobertura.
Para reducir el conjunto independiente de VERTEX COVER sólo tenemos que observar que un conjunto de nodos S es una cubierta de vértices del grafo G = (V, E) (es decir, S toca cada borde en E) si y sólo si los nodos restantes, VS, son un conjunto independiente de G .
Por lo tanto, para resolver una instancia (G, g), del grupo independiente, sólo tiene que buscar una cubierta de vértices de G con JV nodos j g. Si una cubierta de vértices existe, luego tomar todos los nodos no en él. Si no hay tal cubierta de vértices existe, entonces G no puede tener un conjunto independiente de tamaño de g.
Rango de vertices mayor de 100 para el caso de 100 vertices seria d= 0.5 y mmax = 100(100-1)/2 [4950]*0.05 = 247 aristas totales, con las formulas = mmax*d donde d= m / mmax , mmax = n(n-1)/2 para poder ejemplificar como un problema en un grafo no dirigido.
Referencias:
- cb.mty.itesm.mx/materias/tc3001/materiales/tc3001-14-combinatoria.pdf
- www.ing.ula.ve/~ibc/dyaa/c27NP.pdf
- www.nvc.vt.edu/gregwk/cs5104/assets/course_notes/course_notes_2006-04-20.pdf
- www.uv.es/~rmarti/paper/docs/heur1.pdf
- es.scribd.com/doc/63957577/37/OTROS-PROBLEMAS-NP-COMPLETOS-147
- www.cs.berkeley.edu/~vazirani/algorithms/chap8.pdf
- www.cs.uky.edu/~lewis/cs-heuristic/text/class/more-np.html
Ortografía fatal. Rollo extraño no necesario. Lo del problema de decisión no quedó claramente planteado. En lo de densidad hablan en una parte de 0.5 y en otra de 0.05 - uno es muy bajo y el otro es muy alto y no es consistente. 7 pts por el primer reporte.
ResponderEliminar