著色設計

著色設計(coloured design)是一種特殊類型的圖設計，從著色設計可得到別的類型的組合設計，因此，著色設計在一定程度上起著統一不同類型的設計的作用，對k=4及各種可能的著色情況，著色設計的存在性已基本解決。

基本介紹

• 中文名：著色設計
• 外文名：coloured design
• 所屬學科：數學（組合學）
• 簡介：一種特殊類型的圖設計

基本介紹

著色設計是一種特殊類型的圖設計，設對K_k用c種顏色C₁，C₂，…，C_c將邊著色，著色C_i的邊有n_i條，著色後的圖記為G，以g記所有n_i的最大公因數，

將λK_n中連結任意兩個頂點的λ條邊中的n_i/g條著色C_i，所得的圖記為C°K_n，若C°K_n可以分解為若干子圖，使每個子圖都與G同構(連同著色)，則稱這樣的分解是一個著色設計。當c=1時，一個著色(n，k，1)G設計就是一個(n，k，1)-BIBD。當k=4，c=2並使著色C₁的邊形成長為3的圈，著色C₂的邊形成一個星形圖，則一個著色設計中長為3的圈形成一個STS(n)，而第二種顏色的星形圖形成該STS(n)的一個嵌套(參見下文“嵌套”)，當k=4，且{a，b，c，d}上K₄的邊{a，b}，{c，d}著色C₁，{a，c}，{b，d}著色C₂，而{a，d}，{b，c}著色C₃，利用相應的著色設計的G區組定義頂點集上的一個冪等擬群，使

a°b=c，b°a=d，c°d=a，d°c=b，

則該冪等擬群必滿足擬群恆等式xy°yx=x(參見下文“擬群”)，從著色設計還可得到別的類型的組合設計，因此，著色設計在一定程度上起著統一不同類型的設計的作用，對k=4及各種可能的著色情況，著色設計的存在性已基本解決。

相關概念

嵌套

嵌套是由已知圖設計構造新的圖設計的一種方法，以C_k表k個頂點k條邊的無向圈，以S_k+1表k+1個頂點k條邊的星形圖，若對一個(n，k，1)C_k設計存在一個映射f，將每個圈B映為不在B中的某個頂點f(B)，並且使所有的星形圖K_k+1-B(K_k+1)的頂點集V(B)∪{f(B)}，它形成一個(n，k+1，1)S_k+1設計，則稱映射f是一個嵌套，當(n，k，1)C_k設計有嵌套映射時，稱該設計是可嵌套的。若用W_k+1表示k+1個頂點2k條邊的輪形無向圖，則從一個可嵌套的(n，k，1)C_k設計可得到一個(n，k+1，2)W_k+1設計，一個(n，k，1)C_k設計可嵌套的必要條件是n≡1(mod 2k)，史汀生(D.R.Stinson)於1985年證明：當k=3時，這一必要條件也是充分條件，史汀生等人還證明：對每個整數k≥3，除了至多13個可能例外的n值，這個必要條件也是充分條件。

擬群

擬群是一種代數系統，設集Q上有一個二元運算稱為乘法，記為“°”，若對Q中任意元a，b，方程a°x=b及x°a=b在Q中都恰有一個解x，則稱(Q，°)為一個擬群，當Q為有限集時，Q中元素個數稱為擬群的階，在n階擬群(Q，°)的乘法表中，第a行第b列的元素為a°b，若記L=(m_ab)，m_ab=a°b，則由乘法表所得的陣列L是一個n階拉丁方，反之，由一個n階拉丁方作為乘法表所得的二元運算形成集Q上的一個擬群，若對擬群(Q，°)中的每個元x恆有x°x=x，則稱該擬群是冪等的，若集Q上有n-2個n階冪等擬群，使對Q中任意兩個相異元a，b，集Q上n-2個值a°b取遍Q\{a，b}，則稱這n-2個擬群構成一個冪等擬群大集.已知當n≥3且n≠6時，n階冪等擬群大集總存在，而6階冪等擬群大集則不可能存在。