Listado de Ejercicios Nº5

Grafos y Algoritmos

 

Bienvenidos a Grafos y Algoritmos

 

 

SE DEFINEN LOS 3 PROBLEMAS SIGUIENTES:

CLQD: Dado un grafo G y un entero k, ¿existe alguna clique de tamaño k en G?

CLKO: Dado un grafo G, encuentre la cardinalidad de la clique máxima en G.

CLKC: Dado un grafo G, encuentre una clique de tamaño máximo en G.
    1. Pruebe que los 3 problemas son polinomialmente equivalentes.

CLQD º Pt CLKO º Pt CLKC
    1. CLQD º Pt CLKO

      2. è CLQD £ Pt CLKO Ù CLKO £ Pt CLQD

      función CLQD(G,k) función CLKO(G)

      si CLKO(G) ³ k kç 2

      return true mientras CLQD(G,k) hacer

      sino kç k+1

      false return k-1

    2. CLKO º Pt CLKC

è CLKO £ Pt CLKC Ù CLKC £ Pt CLKO

funcion CLKO(G) función CLKC(G)

retornar el tamaño k* ç CLKO(G)

de CLKC(G) para cada nodo v

si (CLKO(G-{v})=k*

entonces G ç G-{v}

retornar G
    1. Pruebe que los problemas CLKO y CLKC son decisión-reducibles.

      2. Por a) CLQD º Pt CLKO º Pt CLKC

      è CLKO y CLKC son decisión-reducibles.

    2. Pruebe que el problema CLQD pertenece a la clase NP.

      3. -problema de decisión: SI

      -polinomialmente verificables: SI

      -ver si el grafo es completo è n2

      -ver que las aristas pertenecen al grafo è n2

    3. Si asume que el problema CLQD es NP-completo, ¿qué puede concluir de los demás problemas?

      4. è CLKO es NP-hard porque CLQD £ Pt CLKO

      è CLKC es NP-hard porque CLQD £ Pt CLKC

    4. El siguiente problema:¿es la clique máxima de G de tamaño k? es NP.

-es de decisión: SI

-prueba verificable en teimpo polinomial: NO

-no se puede verificar que existe una clique de tamaño k+1.

è el problema Ï a NP

 

SE DEFINEN LOS SIGUIENTES 4 PROBLEMAS:

3COL: Dado un grafo G, ¿puede G ser coloreado con 3 colores?

COLD: Dados un grafo G y un entero k, ¿puede G ser coloreado con k colores?

COLO: Dado un grafo G, encuentre el número cromático de G.

COLC: Dado un grafo G, encuentre la coloración optima de G.
    1. Pruebe que estos 4 problemas son polinomialmente equivalentes.

3COL º Pt COLD º Pt COLO º Pt COLC
    1. 3COL º Pt COLD

      2. 3COL £ Pt COLD Ù COLD£ Pt 3COL

      funcion 3COL(G) analizamos COLD

      si COLD(G,3) entonces -problema de decisión

      retornar true -es NP

      sino -3COL es reducible a COLD

      retornar false è es NP-completo

    2. COLD º Pt COLO

      3. COLD£ Pt COLO Ù COLO£ Pt COLD

      función COLD(G,k) función COLO(G)

      if COLO(G) £ k kç n

      then return true while COLD(G,k) do kç k-1

      else return false. Return k+1

    3. COLO º Pt COLC

COLO£ Pt COLC Ù COLC£ Pt COLO

función COLO(G) agregar Ac que no cambien el número

kç número de colores cromático, pintar nodos no adyacentes

utilizados en la del mismo color.

coloración. función COLC(G)

COLC(G) k* = COLO(G)

para cada q Î Ac

si COLO(G+{q }) = k*

entonces Gç G+{q }
    1. Pruebe que los problemas COLO y COLC son decisión-reducibles

      2. Por a) 3COL º Pt COLD º Pt COLO º Pt COLC

      è COLO y COLC son decisión.reducibles.

    2. Si asume que el problema 3COL es NP-completo, ¿qué puede concluir de los demás problemas?

      3. COLO y COLC son NP-hard

    3. El problema: el número cromático de G=k, ¿es un problema NP?.

No es problema NP, el rpoblema es equivalente a COLD; por lo tanto es NP-hard.

 

 
Bienvenidos a Grafos y Algoritmos
 
Menú Principal