二維平面三色頂點著色的非空問題

Abstract

本篇在討論頂點著色在三個顏色的非空問題，一個頂點著色 的單位正方形本篇稱為頂點著色的磚(corner coloring tile)。 非空問題討論的是，能否從磚組成的集合拼出全平面花樣，若進 一步討論能否生成出週期性的花樣，則可以驗證王的猜測是否正 確。 在三個顏色的頂點著色會有81 個磚，藉由等價關係將所有 的磚分成6 類，並且找出最小週期生成元及最大非週期生成元， 再將非週期部分進行合併產生新的週期與非週期生成元，我們更 進一步找出最多磚的兩類合併的部分結果，週期生成元找到6-17 個磚的花樣種類；非週期生成元找到31-36 個磚的花樣種類。

This investigation studies nonemptiness problems of corner coloring with three colors. Unit squares which are discussed in corner coloring of a plane are colored one of p colors in the corner. The adjacent tiles can be combined the right side corners with the left side corners since the side corners have the same colors. The nonemptiness problem is to determine whether the basic set can tile the global patterns or not. Wang's conjecture is to give any B of tiles, if B can tile the global patterns then B is periodic. It has been confirmed that Wang's conjecture is wrong when p >= 6 and Wang's conjecture is true when p = 2. In this study, there are too many tiles to accomplish all the cases in p = 3. In order to compute efficiently, 81 tiles are classified into six groups. From now on, the cases which have already done show that Wang's conjecture holds. The algorithm has ve steps. This thesis shows the result from step 1 to step 3 and there are only parts of results in step 3. It means the computer does not finish the computation of step 3. This study shows the numbers of the equivalent classes of noncycle with k tiles in different groups. Besides, the numbers of the minimum cycle generators with k tiles are represented with the periodic numbers.