| 释义 |
graph colouring graph colouring (application)A constraint-satisfaction problem often usedas a test case in research, which also turns out to beequivalent to certain real-world problems (e.g. register allocation). Given a connected graph and a fixed number ofcolours, the problem is to assign a colour to each node,subject to the constraint that any two connected nodes cannotbe assigned the same colour. This is an example of anNP-complete problem.
See also four colour map theorem. |