四色方柱問題

四色方柱問題是由有四個顏色的立方體組成的問題。由四色(通常是紅色,藍色,綠色和白色)將立方體着色,用四個立方體組成方柱。問題是如何將這些立方體排成一列,使得排成的長方體的每一側(前、後、左、右)都有四種顏色。

四色方柱問題的一種解法。立方體背面的顏色(從左到右)分別是藍紅綠白。底部(從左到右)是白綠藍紅。

四色方柱問題可以轉化為圖着色問題來解決。

解法

 
四個立方體及其顏色
 
通過四個立方體構造的圖

希望通過給定的四個立方體,構造一張,並通過解決圖着色問題得到排列方式。圖的構造方式如下:

  1. 圖最初由4個點構成,四個點的顏色與四色方柱的四種顏色相同(紅綠藍黃)。
  2. 對每個立方體,考慮三個對立面,將每個對立面對應顏色的點用邊連起來。本例中,對於立方體1,在圖中加入了三條邊:紅-紅、紅-綠、黃-藍。
  3. 根據立方體來給邊着色,相同立方體對應的邊染上相同顏色,不同立方體對應邊染上不同顏色。本例中,分別給四個立方體對應邊染上黑、青、橙、紫四種顏色。

下一步需要在構成的無向圖中找出兩個特殊子圖,一個圖表示疊置長方體的前後兩面,另一個表示左右兩面。為了區分疊置的立方體的前/左面與後/右面,需要給兩個子圖設定方向,使得每個頂點恰好有一個入度和一個出度。

構建的子圖應滿足以下三個性質:

  1. 兩個子圖沒有共同邊。否則某個立方體的一對面既是前後兩面,又是左右兩面。
  2. 每個子圖包含僅包含每個立方體的一條邊。因為每條邊只能表示一個立方體,而既要用上所有立方體,又不能重複使用。
  3. 子圖中每個頂點的度為2。因為每個子圖表示長方體的一對面,每種顏色需要在這一對面中出現兩次。
 
兩個有向圖代表立方體兩組對面的排列方式

找到兩個子圖之後,根據構建的兩個有向子圖確定對應立方體每個面的顏色。

例如,在本例中,規定有向邊的起點對應立方體的前/左面,有向邊的終點對應立方體的後/右面。

那麼四個立方體前面的顏色分別是:黃,綠,藍,紅;左面的顏色分別是:紅,藍,黃,綠。