2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics [2020/05/21 17:29] wzx27 |
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics [2020/05/21 17:43] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 80: | 行 80: | ||
| $m$种颜色染正$n$边形，但有限制条件颜色$u$和$v$不能相邻出现 | $m$种颜色染正$n$边形，但有限制条件颜色$u$和$v$不能相邻出现 | ||
| - | 注意：$m$很小 | + | 注意：$m<10$ |
| 对于颜色是否能同时出现的问题，考虑用一个关于颜色的邻接矩阵$G$来表示两个颜色之间的关系: | 对于颜色是否能同时出现的问题，考虑用一个关于颜色的邻接矩阵$G$来表示两个颜色之间的关系: | ||
| 行 94: | 行 94: | ||
| 在离散数学的图论中曾提到$$G^k[i][j]\; :=\; i出发，经过k条边到达j的路径数$$ | 在离散数学的图论中曾提到$$G^k[i][j]\; :=\; i出发，经过k条边到达j的路径数$$ | ||
| - | 在这里就是$$G^k[i][j]\; :=\; 第一个循环节的颜色是i，第k+1个循环节节的颜色是j的染色数$$ | + | 在这里就是$$G^k[i][j]\; :=\; 第1个循环节的颜色是i，第k+1个循环节节的颜色是j的染色数$$ |
| - | 因为最后一个循环节会和第一个循环节再次相邻，所以只对$G[i][j]==1$的$G^{gcd(n,i)-1}[i][j]$算贡献 | + | 因为最后一个循环节会和第一个循环节的下一个元素再次相邻，所以只对$G[i][j]==1$的$G^{gcd(n,i)-1}[i][j]$算贡献 |
| 然后我们会发现这实际上就是 | 然后我们会发现这实际上就是 | ||
2020-2021/teams/wangzai_milk/wzx27/combinatorial_mathematics.1590053350.txt.gz · 最后更改: 2020/05/21 17:29 由 wzx27
