哥德巴赫偶数链

hujunhua

素数和1统称为非合数。
假定扩展的哥德巴赫猜想是成立的：任一偶数可以表为两个非合数之和。
{2, 4, 6, ..., 2n}的一个排列${\text{even}_1,\text{even}_2, \text{even}_3, \ldots, \text{even}_n}$称为一个哥德巴赫偶数链, 使得$\text{even}_i=p_i+p_{i+1},(i=1,2,\ldots,n)$. 这里$p_#$为非合数。
例如：
n=2, {2, 4}={1+1,1+3}
n=3, {2,4,6}={1+1,1+3, 3+3}，{4,2,6}={3+1,1+1,1+5}
n=4, {2,4,6,8}={1+1,1+3, 3+3, 3+5}, {4,2,6,8}={3+1,1+1,1+5,5+3}(成环), {6,4,2,8}={3+3, 3+1, 1+1,1+7}

对于给定的 n, 以a(n)表示最多的哥德巴赫偶数链，求a(n).
去重规则1：互逆排列视为同一个链。
去重规则2：互逆排列视为同一个链，成环排列视为同一个链。
问：
1、a(n)序列中会不会出现 0 ？
2、n>3时，总有环链吗？求环链数 b(n).

mathe

以n=5为例子，如图5所示, 以奇非合数为顶点，任意两个顶点如果和不大于2n=10, 就连接一条边，边的权重即为这个和。
可见权重为 2 和 4 的只有一条边，权重为 6, 8, 10的都有两条边。
我们需要选择一个子图，正好包含这权重(2,4,6,8,10)的边各一条，于是可有1·1·2·2·2=8个子图。
如图1~图4，图6~图9所示，其中虚线边表示未被选中。

然后判断各子图中是否存在欧拉路径或欧拉回路，这个可以使用两个性质
i) 奇度顶点的数目≤2？根据这个可以淘汰图3和图7。(红色框线的为奇度顶点）
ii) 需要连通图，根据这个可以淘汰掉子图4.
图2和图8奇度顶点数目为0，可以构成回路。图1、图6和图9 奇度顶点为2，只能构成开的欧拉路径。
最后对留下的每个合法图枚举不同路径数目即可，其中图1有4条，图2和图8各一条回路，图6有2条，图9有1条。
所以 a(5)=9

hujunhua