作者nowar100 (抛砖引玉)
看板Grad-ProbAsk
标题[理工] [DM]-chromatic polynomial
时间Wed Jul 22 21:05:19 2009
今天如果有个图长这样， ˙─˙ ，对四点着色，求着色多项式？
│ │
˙─˙
<法一>
根据 P(G,λ) = P(G-e,λ) - P(G．e,λ) ，现在把 e 当成是最下面的那个边
˙─˙ ˙─˙
│ │ ╲╱
˙ ˙ ˙
3
原式 = λ(λ-1) - λ(λ-1)(λ-2)
2
= λ(λ-1)(λ - 3λ + 3)
这是小黄书上写法
<法二>
这是我的想法，逐一讨论，先讨论左上点，有λ种选择
接着讨论右上，有λ-1 种
讨论左下，有λ-1 种
最後讨论右下， 这时候分成两种情况讨论
i) 右上=左下时，此时右下有λ-1 种可选择
ii) 右上=/=左下时，此时右下有λ-2 种可选择
3 2
照以上讨论，P(G,λ) = λ(λ-1) + λ(λ-1) (λ-2)
2
= λ(λ-1) (2λ- 3)
神奇了，虽然答案皆一样，λ=2，不过式子却不同
所以同一题目的 chromatic polynomial 有可能不唯一吗？
麻烦解答一下罗，谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.93.39
1F：→ doom8199:第二题讨论是对的，但列式不对: 07/22 21:11
2F：→ doom8199:λ(λ-1)*1*(λ-1) + λ*(λ-1)(λ-2)^2 07/22 21:12
3F：→ nowar100:请问为什麽^ 是*1 考虑左下的时候不能跟左上同样不是吗 07/22 21:27
4F：→ doom8199:先填左上，有λ种填法，然後讨论 右上和左下是否同色 07/22 21:32
5F：→ doom8199:<1>同色:先填右上，有(λ-1)种，然後左下因为与右上相同 07/22 21:35
6F：→ doom8199:所以只有1种，接着填左下时就有 (λ-1) 种 07/22 21:36
7F：→ doom8199:<2>不同色: 也是类似的讨论 07/22 21:36
8F：→ doom8199: 右 ---> 打错字 OTZ 07/22 21:37
9F：→ nowar100:懂了 谢谢您 07/22 21:39
10F：→ nowar100:所以列式应该是唯一的才对 07/22 21:39
11F：→ doom8199:不过法一的扣除法我倒是第一次看过 ...离散学太少了XD 07/22 21:42