Cobertura de vertices (puntos extra)

Tema del proyecto 5 no estoy muy seguro si alguien lo explico en clase pero aqui se los pongo en mi blog Cobertura de vertices.

En ciencias de la computación, el Problema de la cobertura de vértices es un problema NP-completo, que pertenece a los 21 problemas NP-completos de Karp. Es muy utilizado en teoría de complejidad computacional para probar la pertenencia a la clase NP-hard de otros problemas computacionales difíciles.

La cobertura de vértices de un grafo no dirigido G = (V,E) es un subconjunto S de V (el conjunto de vértices) tal que para cada arista ab del conjunto E, ya sea el vértice a o b pertenece a S.

Ejemplo:

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 {2,4,5} y {1,2,4}, ambas de tamaño 3.

El Problema de cobertura de vértices es un problema de optimización que consiste en encontrar una cobertura de vértices de tamaño k en un grafo dado.

ENTRADA: Grafo G.

SALIDA: El menor número k tal que exista una cobertura de vértices S para G de tamaño k.

Equivalentemente, el problema puede definirse como un problema de decisión:

ENTRADA: Grafo G y un entero positivo k.

PREGUNTA: ¿Existe una cobertura de vértices S para G de tamaño menor o igual a k?

La cobertura de vértices está estrechamente relacionada con el Problema del conjunto independiente. Un conjunto de vértices S es una cobertura de vértices si y sólo si su complemento es un conjunto independiente. Así, un grafo con n vértices tiene una cobertura de vértices de tamaño k si y sólo si el grafo tiene un conjunto independiente de tamaño n-k. En este sentido, cada uno de estos problemas es dual al otro.

NOTA: deje los hipervinculos para mas referencias, maestra si cree que la entrada es muy pobre con gusto explicare este tema en asesorias.

http://es.wikipedia.org/wiki/Problema_de_la_cobertura_de_v%C3%A9rtices

RESPUESTA AL EXAMEN "GRAFOS" (puntos extra)

Hola buenas tarde mi nombre es Gustavo adolfo salas coronado y esta es una respuesta al examen ordinario que es del problema de grafos.

·Demuestre que el grafo simple no dirigido definido por las siguientes aristas en formato (inicial, final) es plano: (1,2), (1,3), (1,4), (2,4),(2,6),(3,5), (3,6), (4,5) (5,6).

El grafo es plano ya que ninguno de sus vertices se intersectan.

Diametro: 2
Grado: 3
impresion : 6,5,4,2,1,3

PROYECTO #5

Algoritmo de Floyd-Warshall.

Hola a todos mi nombre es Gustavo Adolfo Salas Coronado de la clase de los jueves de v1 a v3 y este es mi proyecto y explicare cada uno de los puntos requeridos:

1- Problema que este algoritmo resuelve.

El algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino minimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programacion dinamica.

2.- Definicion formal.

Pues el algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo V³ comparaciones (esto es notable considerando que puede haber hasta V² aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima, por lo tanto es un algoritmo de OPTIMIZACION.

3.-La complejidad computacional de este algoritmo es de tipo P determinista ya que puede ser resuelto por una maquina turing determinista en tiempo polinomico.

4.-Pseudocodigo.

Inicializar
D = A ' matriz de distancias = matriz de arcos

si i=j o Dij= infinito entonces Pi,j = nulo sino Pi,j=i 'matriz de caminos

for k = 1 to V
for i = 1 to V
for j = 1 to V
Di,j = min(Di,j , Di,k + Dk,j )
si min = Di,k + Dk,j entonces
Pi,j = Pk,j
fin

5.- Analisis asintotico.

Si utilizamos matrices booleanas, para encontrar todos los n² de desde se necesita hacer 2n² operaciones binarias. Debido a que empezamos con y computamos la secuencia de n matrices booleanas , , ..., , el número total de operaciones binarias es de . Por lo tanto, la complejidad del algoritmo es Θ(n³) y puede ser resuelto por una maquina determinista de turing en tiempo polinomico.

6.- EJEMPLO.

Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias:

Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio.

1ª Iteración: nodo intermedio = 1

La matriz es simétrica, por lo que solamente hará falta calcular el triangulo superior de las distancias.

d₂₃ = min(d₂₃, d₂₁ + d₁₃) = 8

d₂₄ = min(d₂₄, d₂₁ + d₁₄) = 4

d₂₅ = min(d₂₅, d₂₁ + d₁₅) = 9

d₂₆ = min(d₂₆, d₂₁ + d₁₆) =

d₃₄ = min(d₃₄, d₃₁ + d₁₄) = 6

d₃₅ = min(d₃₅, d₃₁ + d₁₅) = 7

d₃₆ = min(d₃₆, d₃₁ + d₁₆) = 1

d₄₅ = min(d₄₅, d₄₁ + d₁₅) =

d₄₆ = min(d₄₆, d₄₁ + d₁₆) = 4

d₅₆ = min(d₅₆, d₅₁ + d₁₆) =

La matriz de distancia después de esta iteración es:

2ª Iteración: nodo intermedio = 2

d₁₃ = min(d₁₃, d₁₂ + d₂₃) = 5

d₁₄ = min(d₁₄, d₁₂ + d₂₄) = 1

d₁₅ = min(d₁₅, d₁₂ + d₂₅) = 12

d₁₆ = min(d₁₆, d₁₂ + d₂₆) =

d₃₄ = min(d₃₄, d₃₂ + d₂₄) = 6

d₃₅ = min(d₃₅, d₃₂ + d₂₅) = 7

d₃₆ = min(d₃₆, d₃₂ + d₂₆) = 1

d₄₅ = min(d₄₅, d₄₂ + d₂₅) = 13

d₄₆ = min(d₄₆, d₄₂ + d₂₆) = 4

d₅₆ = min(d₅₆, d₅₂ + d₂₆) =

La matriz de distancia después de esta iteración es:

3ª Iteración: nodo intermedio = 3

d₁₂ = min(d₁₂, d₁₃ + d₃₂) = 3

d₁₄ = min(d₁₄, d₁₃ + d₃₄) = 1

d₁₅ = min(d₁₅, d₁₃ + d₃₅) = 12

d₁₆ = min(d₁₆, d₁₃ + d₃₆) = 6

d₂₄ = min(d₂₄, d₂₃ + d₃₄) = 4

d₂₅ = min(d₂₅, d₂₃ + d₃₅) = 9

d₂₆ = min(d₂₆, d₂₃ + d₃₆) = 9

d₄₅ = min(d₄₅, d₄₃ + d₃₅) = 13

d₄₆ = min(d₄₆, d₄₃ + d₃₆) = 4

d₅₆ = min(d₅₆, d₅₃ + d₃₆) = 8

La matriz de distancia después de esta iteración es:

4ª Iteración: nodo intermedio = 4

d₁₂ = min(d₁₂, d₁₄ + d₄₂) = 3

d₁₃ = min(d₁₃, d₁₄ + d₄₃) = 5

d₁₅ = min(d₁₅, d₁₄ + d₄₅) = 12

d₁₆ = min(d₁₆, d₁₄ + d₄₆) = 5

d₂₃ = min(d₂₃, d₂₄ + d₄₃) = 8

d₂₅ = min(d₂₅, d₂₄ + d₄₅) = 9

d₂₆ = min(d₂₆, d₂₄ + d₄₆) = 8

d₃₅ = min(d₃₅, d₃₄ + d₄₅) = 7

d₃₆ = min(d₃₆, d₃₄ + d₄₆) = 1

d₅₆ = min(d₅₆, d₅₄ + d₄₆) = 8

La matriz de distancia después de esta iteración es:

5ª Iteración: nodo intermedio = 5

d₁₂ = min(d₁₂, d₁₅ + d₅₂) = 3

d₁₃ = min(d₁₃, d₁₅ + d₅₃) = 5

d₁₄ = min(d₁₄, d₁₅ + d₅₄) = 1

d₁₆ = min(d₁₆, d₁₅ + d₅₆) = 5

d₂₃ = min(d₂₃, d₂₅ + d₅₃) = 8

d₂₄ = min(d₂₄, d₂₅ + d₅₄) = 4

d₂₆ = min(d₂₆, d₂₅ + d₅₆) = 8

d₃₄ = min(d₃₄, d₃₅ + d₅₄) = 6

d₃₆ = min(d₃₆, d₃₅ + d₅₆) = 1

d₄₆ = min(d₄₆, d₄₅ + d₅₆) = 4

La matriz de distancia después de esta iteración es:

6ª Iteración: nodo intermedio = 6

d₁₂ = min(d₁₂, d₁₆ + d₆₂) = 3

d₁₃ = min(d₁₃, d₁₆ + d₆₃) = 5

d₁₄ = min(d₁₄, d₁₆ + d₆₄) = 1

d₁₅ = min(d₁₅, d₁₆ + d₆₅) = 12

d₂₃ = min(d₂₃, d₂₆ + d₆₃) = 8

d₂₄ = min(d₂₄, d₂₆ + d₆₄) = 4

d₂₅ = min(d₂₅, d₂₆ + d₆₅) = 9

d₃₄ = min(d₃₄, d₃₆ + d₆₄) = 5

d₃₅ = min(d₃₅, d₃₆ + d₆₅) = 7

d₄₅ = min(d₄₅, d₄₆ + d₆₅) = 12

La matriz de distancia después de esta iteración es:

Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mínimo entre 2 vértices cualesquiera del grafo será el obtenido en la matriz final. En este caso, el camino mínimo entre 3 y 4 vale 5.

7. APLICACIONES

El algoritmo de Floyd-Warshall puede ser utilizado para resolver los siguientes problemas, entre otros:

• Camino mínimo en grafos dirigidos(algoritmo de Floyd).
• Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo de Warshall. El grafo es un grafo no ponderado y representado por una matriz booleana de adyacencia. Entonces la operación de adición es reemplazada por la conjunción lógica(AND) y la operación menor por la disyunción lógica (OR).
• Encontrar una expresión regular dada por un lenguaje regular aceptado por un autómata finito (algoritmo de Kleene).
• Inversión de matrices de números reales(algoritmo de Gauss-Jordan).
• Ruta optima. En esta aplicación es interesante encontrar el camino del flujo máximo entre 2 vértices. Esto significa que en lugar de tomar los mínimos con el pseudocodigo anterior, se coge el máximo. Los pesos de las aristas representan las limitaciones del flujo. Los pesos de los caminos representan cuellos de botella; por ello, la operación de adición anterior es reemplazada por la operación mínimo.
• Comprobar si un grafo no dirigido es bipartito.

BIBLIOGRAFIA.

http://personales.upv.es/arodrigu/grafos/FloydWarshall.htm
http://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall#Ejemplo