MATH2000 Study Guide - A Roads In Zone 3 Of The Great Britain Numbering Scheme, Planar Graph, Hypercube Graph
Document Summary
2004: hubert keeps (cid:12)ve varieties (a, b, c, d, e) of snakes in boxes in his apartment. Some varieties attack other varieties, and can"t be kept together. In the table, an asterisk indicates that varieties can"t be kept together. Construct a graph with varieties of snakes as vertices, and edges joining varieties which cannot be kept together. Then the minimum number of boxes required is the chromatic number of the graph. Hence the minimum number of boxes required is three. B (cid:3) (cid:0) (cid:3) (cid:0) (cid:0) (cid:3) (cid:3) (cid:0) (cid:3) (cid:0) D (cid:3) (cid:0) (cid:3) (cid:0) (cid:3) (cid:3) (cid:0) (cid:0) (cid:3) (cid:0) Recall that a colouring of a graph is an assignment of a colour (from some set of available colours) to each vertex, with the condition that no two adjacent vertices may receive the same colour. Pg((cid:21)) is a polynomial with integer coe(cid:14)cients. (i ) g = k6 =
