Page 1 of 1
3. (4 puntos) El problema de la coloración de grafos: Un problema de coloración de grafos no dirigidos consiste en asign
Posted: Fri Jul 08, 2022 6:39 am
by 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 34 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.