圆环染色（转自微信公众号单谈数学）
懒得传图片了，改述如下：一个正16边形的顶点标着0或者1，它的任意四个连续顶点形成的4位二进数（共16个）可否恰好包括0000~1111？趣题，图论妙解 这个会不会与格雷码（Binary Gray Code）有关？ 0000111101100101
通过方向和颜色的组合，上述图案可以解释为四个不同的解。其它三解略。
通过颜色和方向的组合，这个图案也是能解释为 4 个不同的解。
顺时针方向，红=0，蓝=1：0000111101001011，化为16进数为0F4B
这个图案有一个特点：从任意位置断开化为16进数都得到两对互补数码，比如0F4B中，0+F=4+B=F.
以上述解释为例，四个16进数是：0F4B，1E96, 3D2C, 7A58, 正好验证包含0~F。
还有两个图案，每个也是四解。然后应该是没有了（0000与1111对径无解）。
这个，可否推广出更一般的规律？感觉蛮有趣的
本题的图论解法，转此留存
且将形成4位二进数的四个连续顶点称为一条边。16边形的任意三个连续顶点都可以跟前端或者尾端的顶点合成一条边，这两条边视作相邻接，接点就是它们共同的三个顶点。
因此，这三个连续顶点就被视作一个点，编号就是它们对应的三位二进数。
以环的顺时针方向为正向，将方向过渡给上述边成为有向边，即出/入接点的边，其编码为在接点编码的右/左端加一位。
一个合格的正16边形顶点染色，显然包括全部8种可能的编码点，并且形成了一个8点16边的图，图中顺箭头方向存在一条单向欧拉回路。
这个图显然就是下图，如果其中真的存在单向欧拉回路，那么就对应了一种合格染色，本题就有了一解。
图中，点000和111所带环形边既是出发边也是进入边。
由于每个接点都有两条进入边和两条出发边，所以必定存在单向欧拉回路，故本题有解。
正32边形染色的有向图
正27边形染3色的有向图
居然还是一个可平面图。正64边形染4色的有向图局部
@mathe 包含K33子图，所以不是可平面图。
页:
[1]
2