tina0624
幼苗
共回答了21个问题采纳率:90.5% 举报
"我想的是先确定顶点的颜色,有4种选择," 下面继续:
先确定顶点的颜色,有4种选择. 然后问题转化成三种色用在下面的五个点上.
设 f(n) 是三种色用在圆环上的n个点 使得相邻异色的个数.
f(3) = 6, f(4) = 18. 然后一般有
f(n+2) = f(n+1) + 2f(n), n>= 3
证明: 对n+2个点的, 指定一个点 a2, 两旁分别称 a1, a3. 去掉a2, 成n+1个点,如果 a1, a3 异色, 成为 f(n+1) 之一. 如果 a1,a3同色, 合并a1,a3, 成为 n个点, 但这时, 因为 a1,a3同色, 所以 有两个选择染色方法, 别的都相同,只有 a2 不同. 去掉a2 合并a1,a3, 后成为 相同的n个点染色方法. 所以总数是 2f(n).
于是 f(5)= 18+2*6=30
总数为 4×30 = 120
1年前
11