3. (4 puntos) El problema de la coloración de grafos: Un problema de coloración de grafos no dirigidos consiste en asign

[answerhappygod]

3 4 Puntos El Problema De La Coloracion De Grafos Un Problema De Coloracion De Grafos No Dirigidos Consiste En Asign 1 (75.6 KiB) Viewed 32 times

3. (4 puntos) El problema de la coloración de grafos: Un problema de coloración de grafos no dirigidos consiste en asignar colores a todos lo nodos del grafo de modo que no haya dos vertices adyacentes (veci- nos) que tengan el mismo color y como maximo se utilicen k colores para colorear el gráfo. Formalmente, dado un grafo G = (V, E) y un numero k, la tarea es decidir si el gráfo se puede colorear usando como máximo k colores de modo que dos vertices adyacentes no tengan el mismo color. Pruebe que 2-COLORACIÓN esta en P.