300000
22772
11746
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
11746
彩色结
如果你只是对如何解决这个难题感兴趣，而不是对背后的理论感兴趣，那么就提前到'通过试错找到上色的提示是什么？
关于不变量
以下三张图中的两张图
可以在不切断结绳的情况下相互变形。
不变量的一个例子是无限多的等价图中的任何一个可能有的最小交叉数。这个不变量很难找到，因为人们无法检查无限多的图。
但是，对于一个给定的图来说，什么可能是一个可以计算的不变量？很难想象，当一个人可以以任何方式对图进行变形时，哪个属性不会在变形中发生变化。
三色性是一个不变量。
N-可着色性
解开结
Tuzun-Sikora
8_19
可以在不切断结绳的情况下相互变形。
你认为它们是哪一种？
下面你将学习如何用颜色来判断两张图是否属于不同的结。通过研究三色性，我们可以看到哪些图绝对不能被变形为另一个图。
否则，下面的顺序显示了如何将Tuzun-Sikora图简化为一个圆。
证明Tuzun-Sikora图是没有结的。
解结图和Tuzun-Sikora连同其他无限多的变形都属于同一个数学结，在这种情况下就是解结。如何决定两个图是否永远不能变形为彼此，无论它们之间的增长有多大？一个在图被变形时不发生变化的属性被称为 "不变"（非可变）。否则，下面的顺序显示了如何将Tuzun-Sikora图简化为一个圆。
证明Tuzun-Sikora图是没有结的。
初步预测
一个Reidemeister 3的移动
移动之后
一个交叉减少传递的移动
移动之后
一个交叉减少传递的移动
移动之后
一个交叉减少传递的移动
移动之后
一个交叉减少传递的移动
移动之后
一个交叉减少传递的移动
移动之后
一个交叉减少传递的移动
移动之后
一个Reidemeister 2的移动
移动之后
一个Reidemeister 1的移动
移动之后
一个Reidemeister 1的移动
移动之后
一个Reidemeister 1的移动
移动之后
一个Reidemeister 1的移动
移动之后
不变量的一个例子是无限多的等价图中的任何一个可能有的最小交叉数。这个不变量很难找到，因为人们无法检查无限多的图。
但是，对于一个给定的图来说，什么可能是一个可以计算的不变量？很难想象，当一个人可以以任何方式对图进行变形时，哪个属性不会在变形中发生变化。
三色性是一个不变量。
为了解释它，我们使用股，这是结线的一部分，可以不提笔就画出来。在每个交叉点都有3条线，一条是过路的，另一条来自两侧。如果每条线都能被赋予3种颜色中的一种，那么这个结就是三色的，这样在每个交叉点我们就有1种或3种颜色，而不是2种颜色。全部用一种颜色上色总是可能的，但不算数。至少需要在某处使用两种颜色。
3张图中，哪张是三色的？
解结只有一股，因此不是三段式的。第2个结对解结是可变形的，因此也不是可结的。我们稍后将证明这一点。另一个结是三段式的，因此如上图所示，永远不可能变形到解结处。
三可性是一个弱的不变性，因为它只包含最小的信息量，只是一个是/否。这个不变量只能够把所有的结分成两组，一组是三可的结，另一组是不可的结。
N-可着色性
一个更强的不变量是 N-可着色性，其中有 N 种颜色可用，每种颜色代表 0、1、2、3、…、N-1 中的一个数字。在每个交叉点上要满足的条件是，2个下方绳子的颜色之和减去上方绳子的颜色的2倍是 N 的倍数。换句话说，如果颜色是 a，b，c，则必须存在一个乘数 k，使得 a+b-2c = kN。数学上相等但更常见的表述是 a+b≡2c mod N。这意味着≡的两侧在模 N 的除法中留下相同的余数。对某个数取模（mod）被称为模块运算，并具有许多有趣和有用的规则。
许多问题出现了。
许多问题出现了。
模块运算介绍
我们可以通过引入一个乘数 k 并将≡方程重新表述为一个普通方程来证明模块化算术的所有陈述。为了缩短符号，我们使用
'integer'为'整数'，
'pq'表示'p乘q'，
'∃'代表'存在'、
':'为'占比'，和
'A→B'为'从A到B'。
证明：如果a ≡ b mod N，c ≡ d mod N，那么(a+c) ≡ (b+d) mod N
a ≡ b mod N 表示 a 和 b 只相差 p 的倍数。
即一定存在一个乘数m，其特性是a=b+mp。用简短的符号表示，这就是
(a ≡ b mod N) → (∃ integer m: a = b + mp)
(c ≡ d mod N) → (∃ integer n: c = d + np)
将两个方程相加，得到a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
即一定存在一个乘数m，其特性是a=b+mp。用简短的符号表示，这就是
(a ≡ b mod N) → (∃ integer m: a = b + mp)
(c ≡ d mod N) → (∃ integer n: c = d + np)
将两个方程相加，得到a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
证明：如果a≡b mod N，那么对于任何整数m，我们有ma≡mb mod N
(a ≡ b mod N) → (∃ integer k: a = b + kN)
与m相乘后，得到
ma = mb + mkN
→ ma ≡ mb mod N
与m相乘后，得到
ma = mb + mkN
→ ma ≡ mb mod N
证明：如果a ≡ b mod (PQ) , 那么a ≡ b mod P.
a ≡ b mod (PQ)
→ ∃ integer k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
那么相反的方向呢？
为什么反过来说是不成立的呢？
→ ∃ integer k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
那么相反的方向呢？
这里有一个反面例子：
6 ≡ 1 mod 5 但是
6 ≢ 1 mod 15，因为6和1相差的不是15的倍数。
6 ≡ 1 mod 5 但是
6 ≢ 1 mod 15，因为6和1相差的不是15的倍数。
为什么反过来说是不成立的呢？
在一个等式mod N中，≡的两边可以有N个不同的值。在一个等式mod(NM)中，≡的两边都可以有NM的不同值。因此，一个模（NM）关系比一个模N关系携带更多的信息。从模（NM）到模N，扔掉信息很容易，但从无中创造信息的反面却不可能。粗略地说，在这个意义上，使用=的正常等价物相当于≡mod ∞(无穷大)。
补充一下，这打开了一种可能性，即在解决方案涉及整数数字且正在寻找形式为使用“=”的方程式解决方案的应用程序中，其中人们知道解决方案中数字的绝对值有一个上限，则策略可能是从用某个小素数N找到mod N的解开始，并计算mod N^2，然后是mod N^4等，直到N的幂大于人们已知的解的上界，然后就可以放弃mod并使用=得到精确解答。
这种方法叫做亨泽尔引理，它可以首先相对于某个较小的质数对单变量多项式进行分解，然后最终精确地分解为整数。
证明： a + b ≡ （（a mod N） + （b mod N）） mod N
a 和 a mod N 相差 N 的倍数：a = （a mod N） + pN
b 和 b mod N 相差 N 的倍数：b = （b mod N） + qN
→ a + b = （a mod N） + （b mod N） + （p + q）N
→ a + b ≡ （a mod N） + （b mod N）） mod N
b 和 b mod N 相差 N 的倍数：b = （b mod N） + qN
→ a + b = （a mod N） + （b mod N） + （p + q）N
→ a + b ≡ （a mod N） + （b mod N）） mod N
证明： ab ≡ （a mod N）（b mod N）） mod N
a 和 a mod N 相差 N 的倍数：a = （a mod N） + pN
b 和 b mod N 相差 N 的倍数：b = （b mod N） + qN
→ ab = （（a mod N） + pN）（（b mod N） + qN）
= （a mod N）（b mod N） + [（a mod N）q + （b mod N）p + pqN]N
→ ab ≡ （a mod N）（b mod N） mod N
b 和 b mod N 相差 N 的倍数：b = （b mod N） + qN
→ ab = （（a mod N） + pN）（（b mod N） + qN）
= （a mod N）（b mod N） + [（a mod N）q + （b mod N）p + pqN]N
→ ab ≡ （a mod N）（b mod N） mod N
证明：如果 P（x，y,...） 是变量 x，y 中的多项式,...那么 P（x，y,...） ≡ P（（x mod N），（y mod N）,...） mod N
每个多项式都可以写成一系列乘积的和，因此反复应用上述两个规则可以证明该说明。
证明：在模算术模中，质数，除以整数再次得到整数。
我们首先证明对于任意整数a ≢ 0 mod N以及质数p，逆元1/a mod N也是一个整数。我们要求a ≢ 0 mod N是因为即使在模算术中，除以零也是不可能的。
让 u 成为 u ≡ 1/a mod N。对于 u 来说，它是 a mod N的倒数，这表示
ua ≡ 1 mod N
→ ∃ integer k：ua = 1 + kp
这具有贝祖定理的形式：ua + vp = GCD(a,p)，其中GCD(a,p)是a和p的最大公约数，而v=-k。由于p是质数且a不是p的倍数，因此GCD(a,p)=1。
通过扩展欧几里得算法可以计算贝祖恒等式中的乘数u,v，并且它们都是整数。
如果你=1/a 是一个整数模 N，那么 b/a = bu 也是一个整数模 N，它将被显示。
示例：1/3 ≡ 5 mod 7，因为 1 = 3（1/3） ≡ 3（5） = 15 = 2（7） + 1 ≡ 1 mod 7。
什么时候 ma ≡ mb mod N 等于 ≡ b mod N？
我们看到从a ≡ b mod N可以得出ma ≡ mb mod N。如果我们可以乘以一个整数k ≡ 1/m mod N，那么我们就能得到等价。这意味着在乘以m之后存在一个整数l使得mk = 1 + lN，这是由于贝祖定理中1 = GCD(m,N)（m和N的最大公约数），因此ma ≡ mb mod N和a ≡ b mod N的等价需要m和N互质。
中国余数定理。
我们之前谈到，模方程 mod N 的信息内容取决于 N。那么将两个更小的模数的模方程组合成一个更大的模数的模方程应该是不可能的吗？
这就是中国余数定理所说的。
如果对于两个方程
x ≡a 1 mod N1
x ≡a 2 mod N2
除数 N1，N2 是互质数，则 x 正好存在一个值，最多是 p1p2 的倍数，它满足两个模方程。
获得解决方案的一种方法是使用扩展的欧几里得算法通过计算m1，m2 求解贝祖恒等式m1N1 + m2N2 = 1，然后使用公式
x =a1m2N2 + a2m1M1
= a1(1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
这显示 x ≡ a1 mod N1 和等价的 x = a2 + (a1 - a2)m2N2，这显示 x ≡ a2 mod N2。
如果有两个以上的模方程，那么可以重复地用一个替换其中的两个，直到有一个模方程形式的解。在每次替换中，新的除数通过成为合并方程的两个除数的乘积而增长。
这就是中国余数定理所说的。
如果对于两个方程
x ≡a 1 mod N1
x ≡a 2 mod N2
除数 N1，N2 是互质数，则 x 正好存在一个值，最多是 p1p2 的倍数，它满足两个模方程。
获得解决方案的一种方法是使用扩展的欧几里得算法通过计算m1，m2 求解贝祖恒等式m1N1 + m2N2 = 1，然后使用公式
x =a1m2N2 + a2m1M1
= a1(1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
这显示 x ≡ a1 mod N1 和等价的 x = a2 + (a1 - a2)m2N2，这显示 x ≡ a2 mod N2。
如果有两个以上的模方程，那么可以重复地用一个替换其中的两个，直到有一个模方程形式的解。在每次替换中，新的除数通过成为合并方程的两个除数的乘积而增长。
如何证明N-着色性是不变量的？
如前面所述 点开“思维拓展” > 定义介绍 > Reidemeister 操作，三个 Reidemeister 操作足以执行旋结图的任何变形。因此，要成为一个不变量，只需要证明该属性在这三个操作下不会改变。
如何证明我移动的Reidemeister不会改变着色性？
如果绳子的颜色是 A 和 B，则左边图中的着色条件要求 A + B ≡ 2B mod N，右边图中的着色条件要求 B + A ≡ 2A mod N。在这两种情况下，B = A 是一个解：
这意味着，执行Reidemeister我移动不会改变着色性。
如何证明Reidemeister II移动不会改变着色性？
如果绳线的颜色分别为 A、B 和 C，如左图所示，则 C 的值由 B + C ≡ 2A mod N 的条件唯一确定，因此 C ≡ (2A - B mod N)；在右图中，有 A + C ≡ 2B mod N，因此 C ≡ (2B - A mod N)。这确定了当进行 Reidemeister II 操作时，新绳的颜色。这不会影响可着色性。
如何证明Reidemeister III移动不会改变着色性？
如果绳线的颜色如图所示为 A、B、C、D、E、F 和 G，则左边的三个条件是
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
通过消除内部绳线F，外部绳线的条件是
2D - E ≡ 2C - B mod N，通过使用 A + D ≡ 2C mod N 简化为
2D - E ≡ A + D - B mod N，因此 A - B - D + E ≡ 0 mod N。
右边的 3 个条件是
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
通过消除内部绳线G，外部绳线的条件是
2C - E ≡ 2A - B mod N，通过使用 2C ≡ A + D mod N 简化为
A + D - E ≡ 2A - B mod N，因此 0 ≡ A - B - D + E mod N。
F 和 G 是根据它们出现的任何一个关系计算得出的。
我们得出的结论是，对于两个图，外部绳线的颜色条件是相同的：A + D ≡ 2C mod N 和 A - B - D + E ≡ 0 mod N。
因此，要么两个图都有颜色，要么没有一个有颜色，因此在Reidemeister III移动下着色性是不变的。
如何证明我移动的Reidemeister不会改变着色性？
如果绳子的颜色是 A 和 B，则左边图中的着色条件要求 A + B ≡ 2B mod N，右边图中的着色条件要求 B + A ≡ 2A mod N。在这两种情况下，B = A 是一个解：
这意味着，执行Reidemeister我移动不会改变着色性。
如何证明Reidemeister II移动不会改变着色性？
如果绳线的颜色分别为 A、B 和 C，如左图所示，则 C 的值由 B + C ≡ 2A mod N 的条件唯一确定，因此 C ≡ (2A - B mod N)；在右图中，有 A + C ≡ 2B mod N，因此 C ≡ (2B - A mod N)。这确定了当进行 Reidemeister II 操作时，新绳的颜色。这不会影响可着色性。
如何证明Reidemeister III移动不会改变着色性？
如果绳线的颜色如图所示为 A、B、C、D、E、F 和 G，则左边的三个条件是
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
通过消除内部绳线F，外部绳线的条件是
2D - E ≡ 2C - B mod N，通过使用 A + D ≡ 2C mod N 简化为
2D - E ≡ A + D - B mod N，因此 A - B - D + E ≡ 0 mod N。
右边的 3 个条件是
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
通过消除内部绳线G，外部绳线的条件是
2C - E ≡ 2A - B mod N，通过使用 2C ≡ A + D mod N 简化为
A + D - E ≡ 2A - B mod N，因此 0 ≡ A - B - D + E mod N。
F 和 G 是根据它们出现的任何一个关系计算得出的。
我们得出的结论是，对于两个图，外部绳线的颜色条件是相同的：A + D ≡ 2C mod N 和 A - B - D + E ≡ 0 mod N。
因此，要么两个图都有颜色，要么没有一个有颜色，因此在Reidemeister III移动下着色性是不变的。
着色的简单性、等效性和独立性
如果有一种颜色，那么对于任何结的图，可以从中获得哪些其他颜色？
每个着色条件都有形式A + B≡2C mod N。让我们把它写成 A - C ≡ C - B mod N。
1）当向每种颜色添加相同的常数（例如S）时，差异不会改变：
（A+S） - （C+S） = A - C + S - S = A - C 和
（C+S） - （B+S） = C - B + S - S = C - B 和
因此，条件仍然得到满足。
2）我们之前看到模算术的规则是，我们可以将≡的两边乘以一个N的互质数，得到方程组的等价解，从而得到等价的颜色。
1）当向每种颜色添加相同的常数（例如S）时，差异不会改变：
（A+S） - （C+S） = A - C + S - S = A - C 和
（C+S） - （B+S） = C - B + S - S = C - B 和
因此，条件仍然得到满足。
2）我们之前看到模算术的规则是，我们可以将≡的两边乘以一个N的互质数，得到方程组的等价解，从而得到等价的颜色。
可着色性模组 2 有意义吗？
不，对于 N=2，着色是简单的。
我们从一条颜色为 A 的绳开始，在经过第一次跨过颜色为 C 的上层绳后继续成为颜色为 B 的绳。然后，A、B 和 C 通过 A + B ≡ 2C mod 2 相关联，之后在两侧加上 B，则有 A ≡ B mod 2，因为 2B ≡ 2C ≡ 0 mod 2。在所有交叉处继续这种推理，就可以得出所有绳子的颜色要么是偶数颜色（0），要么是奇数颜色（1）。这可以得到一个简单的着色。
我们从一条颜色为 A 的绳开始，在经过第一次跨过颜色为 C 的上层绳后继续成为颜色为 B 的绳。然后，A、B 和 C 通过 A + B ≡ 2C mod 2 相关联，之后在两侧加上 B，则有 A ≡ B mod 2，因为 2B ≡ 2C ≡ 0 mod 2。在所有交叉处继续这种推理，就可以得出所有绳子的颜色要么是偶数颜色（0），要么是奇数颜色（1）。这可以得到一个简单的着色。
可着色性mod（2N），即模偶数呢？
如上所述，我们可以发现所有颜色都是偶数或奇数。如果它们是偶数，那么我们可以将它们都除以 2，不会丢失信息，并且得到mod N 的染色方案。如果它们都是奇数，那么我们可以将所有颜色加上 1，得到一个等价的染色方案，这时所有颜色都是偶数，因此我们可以去掉一个因子 2，得到mod N 的等价染色方案。
因此，每个着色mod （2N） 相当于一个mod N。
因此，每个着色mod （2N） 相当于一个mod N。
对于哪个N是有用的而不是微不足道的？
对于奇数 N>1 着色性 mod N 是有意义的。
知道所有着色模组 P 和模组 Q 是否足以知道所有着色模组 （PQ）？
如果 N 是一个合数，即一个有两个因数且它们不是 1 的乘积，那么我们可以将其写成 N=PQ，其中 P 和 Q 是互质的。如果我们有一个关于mod N 的着色方案的解，那么通过对所有的颜色值取mod P，我们可以得到一个关于mod P 的着色方案；而通过对所有的颜色值取mod Q，则可以得到一个关于mod Q 的染色方案。但是反过来呢？如果一个结环图的染色方案关于mod P 和mod Q 都有解（其中 P 和 Q 是互质的），那么这个着色方案是否有关于mod PQ 的解呢？
答：是的。
证明：
设1、2 是着色 mod P 和 mod Q 中一股的颜色。
然后，中国余数定理保证了一个满足两个条件的整数 A mod PQ 的存在性和唯一性
A ≡A 1 mod P
A ≡A 2 mod Q。
这可以对每条线重复，给出颜色值A，B，C,...模组 PQ.
在每次交叉时，两种着色条件
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
是满足的。（A + B - 2C） mod PQ 的唯一值为零 mod P 且为零 mod Q 是 A + B - 2C ≡ 0 mod PQ。这表明颜色值 A、B、C,...提供一个着色 mod PQ。
因为所有正整数都有一个质因式分解，所以它们可以写成质数幂的乘积。因此，人们可以通过仅研究所有奇质数的所有幂作为着色数来找到所有着色数。我们之前看到，质数 2 和 2 的幂不可能是着色数字。
将开始检查某个质数的着色模的存在，如果成功，则以该质数的更高幂重复检查，直到不再存在着色。
答：是的。
证明：
设1、2 是着色 mod P 和 mod Q 中一股的颜色。
然后，中国余数定理保证了一个满足两个条件的整数 A mod PQ 的存在性和唯一性
A ≡A 1 mod P
A ≡A 2 mod Q。
这可以对每条线重复，给出颜色值A，B，C,...模组 PQ.
在每次交叉时，两种着色条件
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
是满足的。（A + B - 2C） mod PQ 的唯一值为零 mod P 且为零 mod Q 是 A + B - 2C ≡ 0 mod PQ。这表明颜色值 A、B、C,...提供一个着色 mod PQ。
因为所有正整数都有一个质因式分解，所以它们可以写成质数幂的乘积。因此，人们可以通过仅研究所有奇质数的所有幂作为着色数来找到所有着色数。我们之前看到，质数 2 和 2 的幂不可能是着色数字。
将开始检查某个质数的着色模的存在，如果成功，则以该质数的更高幂重复检查，直到不再存在着色。
通过反复试验找到颜色的提示是什么？
应该给哪个字母一个值？
- 要决定接下来要着色的线，请按 Enter 按字母数（即按紧急程度）对方程式进行排序。
- 如果一个方程有几个字母，那么选择一个出现在大多数其他方程中的字母，以便在分配数字时简化更多的方程。等效地，将鼠标移到方程上，看到圆圈的交叉点，并在此交叉点单击通过次数最多的无色线条。
- ≡右侧的字母比左侧的字母计算速度更快。要计算左边的字母，需要除以 2，这可能需要在右边加上 N 才能变得偶数。这并不困难，但在比赛中是有先见之明的。出于同样的原因，在猜测一个字母的值时，人们可能会在≡的左侧取一个字母。
- 为了节省时间，请不要担心计算区间 0..N−1 的值。值可以是负数或任意大。如果它们是正确的，那么紫色方程就会变成绿色，这才是最重要的。
- 如果一个方程只剩下一个字母，那么背景是紫色的，然后别无选择，需要计算该值以使方程变为绿色。请参阅说明中的示例。
- 如上所示 本节 > “如果一个人有一种颜色......”部分，所有字母的值都可以按相同的常量值移动。因此，想要赋值的第一个字母可以赋予值 0，而不会损失通用性。不用为该字母尝试任何其他值，因为总是可以将该值转换为零。
- 对于要着色的第二个字母，只需要考虑两种情况：1）它与第一个字母具有相同的值，即0，以及2）它具有不同的值。在这种情况下，只需要考虑 1，因为我们看到所有数字都可以乘以 2。（N-1）（其中 N 是可用颜色数量的质数）并且仍然具有等效的解决方案。请参考 本节 >“如果一个人有一种颜色......”。例如，如果 N=5 并且一个人会为第二个分配的字母尝试不同的值，例如 3 并获得解决方案，然后将该值（和所有其他值）乘以 2 将使 3 到 3×2 = 6 ≡ 1 mod 5 所以变成 1。因此，第二个字母只需要尝试为 0 和 1。
- 测试也是时间问题。当负数比正数计算得更快时，可以通过输入负数来节省时间。接口不需要 0..N-1 范围内的数字。
- 当方程变为红色时，则不满足≡条件，必须至少更改一个数字。然后尝试使用其他数字。为了不错过数字，可以尝试0，1,...,N-1顺序的数字，并在发现颜色时停止。
- 通过单击撤消按钮进行回溯时，如果看到紫色方程式，则可以不假思索地再次单击撤消按钮。原因是紫色方程只有一个字母，对于这个字母只有一个可能的值（mod N），所以在这种情况下不需要为这个字母尝试其他值。
- 为了系统地搜索并且不错过任何着色可能性，可以首先为每个变量分配值 0，给出简单的解决方案，然后开始回溯以获得非简单的解决方案。
- 此游戏中使用的结图已经具有最少的交叉次数。但是，如果图表不是最小的，那么首先简化它们是有利的。如果没有上述加速技术，人们将不得不尝试NC 着色，其中N是颜色的数量，C是交叉数量=股数。仅将交叉次数减少 1 可使工作量降低 N 个系数。
有不能上色的结吗？
是的。少于 12 个没有颜色的交叉点是 10124、10153、11n 34、11n42、11n49、11n116，当然还有解结。该图显示了结 10124 的示意图。
页面顶部标有“Tuzun-Sikora”的图表只是无数张解结图之一，因此也无法着色。
页面顶部标有“Tuzun-Sikora”的图表只是无数张解结图之一，因此也无法着色。
是否还有更多的颜色不变量，如何计算它们？
是的，这些额外的不变量是解决方案的多重性，每个可用颜色的数量都有一个多重性。要理解以下评论，一些线性代数知识是有用的。
如果节点图有 C 交叉，那么它也有 C 链，因此条件系统有一个 C×C 系数矩阵，其中每行代表一个交叉，由两个 -1 和一个 2 或 +1 和 -1 组成（Reidemeister I 环交叉）。每列对应于一个链，并且具有与链具有通道一样多的 2，并且两个 -1 或一个 -1 和一个 +1。
条件形成一个齐次线性系统（右侧仅包含 0），问题是找到存在非简单线性独立解（着色）的着色数模。
就像线性代数中通过交换行和将行的倍数加到其他行中将矩阵变成对角形式一样，在这里还会对列执行这些步骤。但是不允许使用一个数字乘以行或列，因为这会添加一个颜色数字模数，使得矩阵的行列式为零，从而添加一种额外的着色方式。相反，所做的是重复选择列/行的2个非零分量，比如A,B，使用扩展欧几里得算法找到p，q，满足pA + qB = GCD(A, B)。p，q是两个行/列的乘数。交换行/列后，GCD(A,B)成为对角元素。这样得到的是一个对角矩阵，称为史密斯正规形式，通常左上角以1开头，后面是每个数字因为下一个对角线数而被分解质因数的数字。最后一个对角线元素为零，因为每个节点图可以使用仅一个颜色来进行简单的着色。因此，删除任意一列和任意一行后，计算Smith 标准型就足够了。
计算 C×C 系数矩阵的行列式给出零，因为列加起来为零。在删除一行和一列后计算行列式得到一个数字，该数字是Smith 标准型对角线上数字的乘积。因此，Smith 标准型为大致相同的努力提供了更多信息。
示例：对于此具有 83 个交叉的图表，系数矩阵的大小为 83×83。
Smith 标准型在左上角开始用79个1的对角线后是3，3，85837301265（= 3 x 5 x 5722486751），0。这意味着有三种独立的3着色方案和一种85837301265着色方案，这也意味着它有5着色，15着色，3x5722486751着色和5x5722486751着色。
如果图表没有着色，则除最后一个位置的 0 外，所有对角线数字均为 1。
下图属于结 12a801。
Smith 标准型（SNF）在对角线上有9个1，后面是3，45，0。在这种形式中，每个数字都是下一个对角线数字的一个因数。着色的多重性是作为一个因数出现的对角线元素的数量。因此，这个结的每个图都有两个独立的3-着色和一个45-着色，这表明它也有一个5-着色、9-着色、15-着色。
如果节点图有 C 交叉，那么它也有 C 链，因此条件系统有一个 C×C 系数矩阵，其中每行代表一个交叉，由两个 -1 和一个 2 或 +1 和 -1 组成（Reidemeister I 环交叉）。每列对应于一个链，并且具有与链具有通道一样多的 2，并且两个 -1 或一个 -1 和一个 +1。
条件形成一个齐次线性系统（右侧仅包含 0），问题是找到存在非简单线性独立解（着色）的着色数模。
就像线性代数中通过交换行和将行的倍数加到其他行中将矩阵变成对角形式一样，在这里还会对列执行这些步骤。但是不允许使用一个数字乘以行或列，因为这会添加一个颜色数字模数，使得矩阵的行列式为零，从而添加一种额外的着色方式。相反，所做的是重复选择列/行的2个非零分量，比如A,B，使用扩展欧几里得算法找到p，q，满足pA + qB = GCD(A, B)。p，q是两个行/列的乘数。交换行/列后，GCD(A,B)成为对角元素。这样得到的是一个对角矩阵，称为史密斯正规形式，通常左上角以1开头，后面是每个数字因为下一个对角线数而被分解质因数的数字。最后一个对角线元素为零，因为每个节点图可以使用仅一个颜色来进行简单的着色。因此，删除任意一列和任意一行后，计算Smith 标准型就足够了。
计算 C×C 系数矩阵的行列式给出零，因为列加起来为零。在删除一行和一列后计算行列式得到一个数字，该数字是Smith 标准型对角线上数字的乘积。因此，Smith 标准型为大致相同的努力提供了更多信息。
示例：对于此具有 83 个交叉的图表，系数矩阵的大小为 83×83。
Smith 标准型在左上角开始用79个1的对角线后是3，3，85837301265（= 3 x 5 x 5722486751），0。这意味着有三种独立的3着色方案和一种85837301265着色方案，这也意味着它有5着色，15着色，3x5722486751着色和5x5722486751着色。
如果图表没有着色，则除最后一个位置的 0 外，所有对角线数字均为 1。
下图属于结 12a801。
Smith 标准型（SNF）在对角线上有9个1，后面是3，45，0。在这种形式中，每个数字都是下一个对角线数字的一个因数。着色的多重性是作为一个因数出现的对角线元素的数量。因此，这个结的每个图都有两个独立的3-着色和一个45-着色，这表明它也有一个5-着色、9-着色、15-着色。
结着色的数据
是否有一定尺寸的素结的可能着色概述？
文本文件
https://cariboutests.com/qi/knots/colour3-15-N.txt 列出了每个交叉数为 15 ≦的结，列出了Smith 标准型中所有非 0 或 1 的条目。这些数字是从一张图计算出来的，但它们是不变的，因此从该结的任何图计算时都是相同的。如果喜欢彩色结的图片，那么可以通过单击主页“主页”>“海报”从我们的海报集中下载海报， https://cariboutests.com/images/posters/knot_colouring_portrait.pdf。
N着色作为不变的强度有多大？
下表显示了使用更多的着色不变量如何增加节点的不变类数，从而减少每个类的平均节点数。右列显示了着色不变类数的 （#cr - 3） 根如何大致保持不变，其中#cr是结的交叉数。
表1：颜色不变量的统计量
# CR： # 交叉点数
# 节数： # 节数
# of cl1： # 类 当只考虑质数列表时
# of cl2： # 类 当只考虑质数的多重性列表时
# of cl3: # 类 当考虑 Smith 标准型条目列表时
abs: exp(ln(noofcl3[cr])/(cr-3))
= (# of cl3)的第(cr-3)个根
表1：颜色不变量的统计量
# CR： # 交叉点数
# 节数： # 节数
# of cl1： # 类 当只考虑质数列表时
# of cl2： # 类 当只考虑质数的多重性列表时
# of cl3: # 类 当考虑 Smith 标准型条目列表时
abs: exp(ln(noofcl3[cr])/(cr-3))
= (# of cl3)的第(cr-3)个根
| # of cr | # of kn | # of cl1 | kn/cl1 | # of cl2 | kn/cl2 | # of cl3 | kn/cl3 | abs ↑ |
|---|---|---|---|---|---|---|---|---|
| 3 | 1 | 1 | 1.00 | 1 | 1.00 | 1 | 1.00 | |
| 4 | 1 | 1 | 1.00 | 1 | 1.00 | 1 | 1.00 | 1.000 |
| 5 | 2 | 2 | 1.00 | 2 | 1.00 | 2 | 1.00 | 1.414 |
| 6 | 3 | 3 | 1.00 | 3 | 1.00 | 3 | 1.00 | 1.442 |
| 7 | 7 | 7 | 1.00 | 7 | 1.00 | 7 | 1.00 | 1.627 |
| 8 | 21 | 13 | 1.62 | 14 | 1.50 | 16 | 1.31 | 1.741 |
| 9 | 49 | 25 | 1.96 | 29 | 1.69 | 33 | 1.48 | 1.791 |
| 10 | 165 | 47 | 3.51 | 53 | 3.11 | 62 | 2.66 | 1.803 |
| 11 | 552 | 81 | 6.81 | 93 | 5.94 | 116 | 4.76 | 1.812 |
| 12 | 2176 | 136 | 16.00 | 162 | 13.43 | 203 | 10.72 | 1.805 |
| 13 | 9988 | 234 | 42.68 | 271 | 36.86 | 342 | 29.20 | 1.792 |
| 14 | 46972 | 409 | 114.85 | 488 | 96.25 | 623 | 75.40 | 1.795 |
| 15 | 253293 | 722 | 350.82 | 855 | 296.25 | 1100 | 230.27 | 1.792 |
带有 C 交叉的结的最大着色数如何取决于 C？
如果取所有交叉数为 C （<16） 的结，并从这些结中找到着色数最高的结 Nmax，则下表显示当将 C 增加 1 时，Nmax 大约增加 1.7 倍。
表 2：表 B（C） =Nmax1/(C−1)
表 2：表 B（C） =Nmax1/(C−1)
| C | Nmax | 结 | B（C） |
|---|---|---|---|
| 3 | 3 | 31 | 1.732 |
| 4 | 5 | 41 | 1.710 |
| 5 | 7 | 52 | 1.627 |
| 6 | 13 | 63 | 1.670 |
| 7 | 19 | 76 | 1.634 |
| 8 | 37 | 817 | 1.675 |
| 9 | 61 | 933 | 1.672 |
| 10 | 109 | 10115 | 1.684 |
| 11 | 199 | 11a301 | 1.698 |
| 12 | 353 | 12a1188 | 1.705 |
| 13 | 593 | 13a4620 | 1.703 |
| 14 | 1103 | 14a16476 | 1.714 |
| 15 | 1823 | 15a65606 | 1.710 |
有没有可以计算着色的计算机程序？
AsciiKnots是一个计算机程序，通过计算系数矩阵的smith标准型来计算给定的结图的所有着色数字。如果结图没有太多交叉，那么它还通过优化的试错搜索来计算给定的着色数，所有着色或所有着色数字，包括它们的颜色。除了着色，这个程序还可以计算更多。可以从
https://cariboutests.com/games/knots/AsciiKnots.tar.gz 下载。AsciiKnots 在 Linux 下运行。严格的Windows用户可以免费安装Ubuntu linux作为Windows 10下的应用程序。用于删除旧下载版本、下载最新版本、解压缩和启动它的 Linux 命令是
rm AsciiKnots.tar.gz
wget https://cariboutests.com/games/knots/AsciiKnots.tar.gz
tar xfz AsciiKnots.tar.gz
./AsciiKnots
选择“工具”>“颜色结”后，https://cariboutests.com/games/knots/knoteditor/ 上也提供有限的着色功能
引用
[1] R. H. Fox, Metacyclic invariants of knots and links, Canadian Journal of Mathematics 22 (1970) 193−201.
[2] J. H. Przytycki, 3-coloring and other elementary invariants of knots. Banach Center Publications, Vol. 42, “Knot Theory”, Warszawa, 1998, 275−295.
[3] D. Rolfsen, Table of Knots and Links. Appendix C in Knots and Links. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha and C. Livingston, KnotInfo: Table of Knot Invariants, http://www. indiana.edu/~knotinfo
[5] “Colour Classification of Knots with Crossing Number up to 15”, https:// cariboutests.com/qi/knots/colour3-15.txt
[6] T. Wolf, “A Knot Workbench”, https://cariboutests.com/games/knots/AsciiKnots.tar.gz
[2] J. H. Przytycki, 3-coloring and other elementary invariants of knots. Banach Center Publications, Vol. 42, “Knot Theory”, Warszawa, 1998, 275−295.
[3] D. Rolfsen, Table of Knots and Links. Appendix C in Knots and Links. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha and C. Livingston, KnotInfo: Table of Knot Invariants, http://www. indiana.edu/~knotinfo
[5] “Colour Classification of Knots with Crossing Number up to 15”, https:// cariboutests.com/qi/knots/colour3-15.txt
[6] T. Wolf, “A Knot Workbench”, https://cariboutests.com/games/knots/AsciiKnots.tar.gz
关注或订阅更新：