Friday, October 28, 2011

Two colors

Given a undirect graph G=(N, E) a two colour scheme assigns to each node either the colour black or white. A node is diverse if it has the opposite colour of at least half of its neighbours. How can you assign a diverse colour to all the nodes in a graph?

tricky one
Pubblicato da a
Reazioni: 

1 commenti:

  1. 1. Colour the nodes in any way you want. Could be, e.g., all white.
    2. As long as you see a node that is not diverse, change its colour to the opposite.

    This will end at some point because, every time you do step 2, you strictly decrease the number of edges connecting nodes of the same colour. There's only a finite number of them, so this gives an upper bound on the number of steps.

    ReplyDelete

Subscribe to: Post Comments (Atom)