Question

数学的染色问题

Answer 1

1) 区域 B
C
E 有 4P3 = 24 种涂法
设区色与区名相同
另一色为 M。Case 1 : 当区域 F 涂上颜色 B
而区域 G 涂上颜色 C
则区域 A 有非 B
E 的 2 种涂法
同理区域 D 有非 C
E 的 2 种涂法
共 2 * 2 = 4 种涂法。Case 2 : 当区域 F 涂上颜色 B
而区域 G 涂上颜色 M
则区域 A 有非 B
E 的 2 种涂法
区域 D 有非 C
E
G 的 1 种涂法(即涂B)
共 2 * 1 = 2 种涂法。Case 3 : 当区域 F 涂上颜色 M
而区域 G 涂上颜色 C
与 Case2 同理共 2 种涂法。Case 4 : 当区域 F 不为颜色 B
且区域 G 不为颜色 C
则区域 F
G 颜色有 (C
B)
(C
M)
(M
B) 的 3 种涂法
而区域 A 有非 B
E
F 的 1 种涂法
同理区域 D 有非 C
E
G 的 1 种涂法
共 3 * 1 * 1 = 3 种涂法。综上共 24 * (4 + 2 + 2 + 3) = 264 种涂法。 2)区域 B
C
E 有 5P3 = 60 种涂法
设区色与区名相同
另二色为 M
N。Case 1 : 当区域 F 涂上颜色 B
而区域 G 涂上颜色 C
则区域 A 有非 B
E 的 3 种涂法
同理区域 D 有非 C
E 的 3 种涂法
共 3 * 3 = 9 种涂法。Case 2 : 当区域 F 涂上颜色 B
而区域 G 涂上颜色 M 或 N
则区域 A 有非 B
E 的 3 种涂法
区域 D 有非 C
E
G 的 2 种涂法
共 3 * 2 = 6 种涂法。Case 3 : 当区域 F 涂上颜色 M 或 N
而区域 G 涂上颜色 C
与 Case2 同理共 6 种涂法。Case 4 : 当区域 F 不为颜色 B
且区域 G 不为颜色 C
则区域 F
G 颜色有 (C
B)
(C
M)
(C
N)
(M
B)
(M
N)
(N
M)
(N
B) 的 7 种涂法
而区域 A 有非 B
E
F 的 2 种涂法
同理区域 D 有非 C
E
G 的 2 种涂法
共 7 * 2 * 2 = 28 种涂法。综上共 60 * (9 + 6 + 6 + 28) = 2940 种涂法。 2012-08-01 23:40:22 补充： 修正: 综上共 60 * (9 + 6*2 + 6*2 + 28) = 3660 种涂法。