四色方柱问题

四色方柱问题是由有四個顏色的立方体組成的問題。由四色(通常是红色,蓝色,绿色和白色)將立方體着色,用四个立方体组成方柱。问题是如何将这些立方体排成一列,使得排成的长方体的每一側(前、后、左、右)都有四种颜色。

四色方柱问题的一种解法。立方体背面的颜色(从左到右)分别是蓝红绿白。底部(从左到右)是白绿蓝红。

四色方柱问题可以转化为图着色问题来解决。

解法

编辑
 
四个立方体及其颜色
 
通过四个立方体构造的图

希望通过给定的四个立方体,构造一张,并通过解决图着色问题得到排列方式。图的构造方式如下:

  1. 图最初由4个点构成,四个点的颜色与四色方柱的四种颜色相同(红绿蓝黄)。
  2. 对每个立方体,考虑三个对立面,将每个对立面对应颜色的点用边连起来。本例中,对于立方体1,在图中加入了三条边:红-红、红-绿、黄-蓝。
  3. 根据立方体来给边着色,相同立方体对应的边染上相同颜色,不同立方体对应边染上不同颜色。本例中,分别给四个立方体对应边染上黑、青、橙、紫四种颜色。

下一步需要在构成的无向图中找出两个特殊子图,一个图表示叠置长方体的前后两面,另一个表示左右两面。为了区分叠置的立方体的前/左面与后/右面,需要给两个子图设定方向,使得每个顶点恰好有一个入度和一个出度。

构建的子图应满足以下三个性质:

  1. 两个子图没有共同边。否则某个立方体的一对面既是前后两面,又是左右两面。
  2. 每个子图包含仅包含每个立方体的一条边。因为每条边只能表示一个立方体,而既要用上所有立方体,又不能重复使用。
  3. 子图中每个顶点的度为2。因为每个子图表示长方体的一对面,每种颜色需要在这一对面中出现两次。
 
两个有向图代表立方体两组对面的排列方式

找到两个子图之后,根据构建的两个有向子图确定对应立方体每个面的颜色。

例如,在本例中,规定有向边的起点对应立方体的前/左面,有向边的终点对应立方体的后/右面。

那么四个立方体前面的颜色分别是:黄,绿,蓝,红;左面的颜色分别是:红,蓝,黄,绿。