14. 奇数环拓展——异数节点、数组节点


在本题中紫色9个节点形成奇数环,但其中部分节点为异数区块节点和数组节点。
其中异数区块节点与同数区块节点性质相同。
数组节点:为真,数组成立(至少有n个候选数为真,本题中n=2);为假,数组不成立(至多有n-1个候选数为真)。
之前对于奇数环的公式是基于同数节点的,广义上来说可以将link自噬改为节点的自噬:
即在节点数量为n的奇数环中,至少有 (n - 1) / 2 个节点为真。
本题中根据弱链定义(两个节点不能同时为真),可以发现9个节点之间均为弱链,则形成奇数环。
因此至少有4个节点为真。
同时其中有两个数组节点,而当数组节点为真时 link = 2。
因此奇数环总 link = 4 + 2 = 6。(需注意,在计算由数组节点引起的link增加时,要看数组节点是否相邻,若两个数组节点相邻,则这两数组节点不能同时成立,即link只会+1,link = 4 + 1 = 5)
除奇数环外,三个普通link为:r1(3)、r4c3、r4c8
综上所述:Truth = 9, Link = 6 + 3 = 9, Rank = 0