domingo, 2 de enero de 2011

Problema del dia (2 de Ene)

Se tiene un grafo $G$ con $n$ vértices, todos pintados de blanco o de negro. En cada paso, se escoge un vértice y se cambia el colo de ese vértice y todos los adyacentes a él. Demuestra que si la gráfica  comienza completamente blanca, se puede hacer completamente negra.

3 comentarios:

  1. Ammm .... entiendo la grafica como una punticula no?? y como vértices adyacentes a los 8 puntos que lo rodean, suponiendo que el punto no es una frontera??

    ResponderBorrar
  2. Emm, no, grafica = grafo. Vertices adyacentes = vertices unidos por una arista.

    ResponderBorrar
  3. Sugerencia:
    Utiliza inducción sobre n.

    ResponderBorrar