四色方柱問題
![]() |
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/fd/InstantInsanity.jpg/220px-InstantInsanity.jpg)
四色方柱問題是由有四個顏色的立方體組成的問題。由四色(通常是紅色,藍色,綠色和白色)將立方體着色,用四個立方體組成方柱。問題是如何將這些立方體排成一列,使得排成的長方體的每一側(前、後、左、右)都有四種顏色。
四色方柱問題可以轉化為圖着色問題來解決。
解法
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Instant_insanity_Cube.png/220px-Instant_insanity_Cube.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Instant_sanity_graph.png/220px-Instant_sanity_graph.png)
希望通過給定的四個立方體,構造一張圖,並通過解決圖着色問題得到排列方式。圖的構造方式如下:
- 圖最初由4個點構成,四個點的顏色與四色方柱的四種顏色相同(紅綠藍黃)。
- 對每個立方體,考慮三個對立面,將每個對立面對應顏色的點用邊連起來。本例中,對於立方體1,在圖中加入了三條邊:紅-紅、紅-綠、黃-藍。
- 根據立方體來給邊着色,相同立方體對應的邊染上相同顏色,不同立方體對應邊染上不同顏色。本例中,分別給四個立方體對應邊染上黑、青、橙、紫四種顏色。
下一步需要在構成的無向圖中找出兩個特殊子圖,一個圖表示疊置長方體的前後兩面,另一個表示左右兩面。為了區分疊置的立方體的前/左面與後/右面,需要給兩個子圖設定方向,使得每個頂點恰好有一個入度和一個出度。
構建的子圖應滿足以下三個性質:
- 兩個子圖沒有共同邊。否則某個立方體的一對面既是前後兩面,又是左右兩面。
- 每個子圖包含僅包含每個立方體的一條邊。因為每條邊只能表示一個立方體,而既要用上所有立方體,又不能重複使用。
- 子圖中每個頂點的度為2。因為每個子圖表示長方體的一對面,每種顏色需要在這一對面中出現兩次。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/0/02/Instant_insanity_final.png/220px-Instant_insanity_final.png)
找到兩個子圖之後,根據構建的兩個有向子圖確定對應立方體每個面的顏色。
例如,在本例中,規定有向邊的起點對應立方體的前/左面,有向邊的終點對應立方體的後/右面。
那麼四個立方體前面的顏色分別是:黃,綠,藍,紅;左面的顏色分別是:紅,藍,黃,綠。