Question

Seven foreign diplomats need to be driven to the airport, but some cannot be transported together. The chart below has X's for diplomats that cannot be together. AB C D E X A XX BX F G X X X x X CX D X EXX F XXX GXXX XXX X X (a) Sketch a conflict graph for this problem. (b) Find the minimum number of colors required to color the vertices of this graph. Write the color numbers near the vertices in your graph. (c) List the groups in which the diplomats should be transported.

Answer 1

Solution:

Given data:

Seven foreign diplomats need to be driven to the airport.

The chart below has 'x' s for diplomats that cannot be together.

Answer:

(a) Draw a graph whose vertices are the seven diplomats and

there is an edge between two of them if and only if they cannot be transported together

B A C G D F E

(b) Since A,B and G form a complete graph on 3 vertices then we need

at least 3 colors.

2 1 A 2 3 G D 3 1 F 3 E

Since we were able to find a 3-coloring (as shown above) then the minimum number

of colors needed is 3.

(c)

Group1: A and E

Group 2: B and C

Group 3: D, F and G

please give me thumbup.....