anti-coordination problem
·
The wishy-washy way to motivate graph coloring is to claim that many problems can be expressed as an “anti-coordination problem,” where you win when no agent in the system behaves the same as any of their neighbors. A totally made up example is radio frequencies. Radio towers pick frequencies to broadcast, but if nearby towers are broadcasting on the same frequency, they will interfere. So the vertices of the graph are towers, nearby towers are connected by an edge, and the colors are frequencies.
Обратные ссылки
programmer introduction to math
[!error] В общем, я не справился с книжкой, хотя в начале было интересно сколько всего...