施泰納k圈系統(Steiner k-cycle system)是一類特殊的圖設計，以Ck表示k個頂點k條邊的圈無向圖，若對任意r(1≤r<k/2)以及任意兩個相異頂點，在某個(n，k，1)Ck設計中恰有一個圈含這兩個頂點且使它們在該圈中的距離為r，則稱該圖設計為施泰納k圈系統，記為SCS(n，k)。
基本介紹
- 中文名：施泰納k圈系統
- 外文名：Steiner k-cycle system
- 所屬學科：數學（組合學）
- 簡介：一類特殊的圖設計
- 符號：SCS(n，k)
基本介紹,相關說明,
基本介紹
一個SCS(n，3)即為通常的STS(n)，而一個SCS(n，4)就是一般的(n，4，1)C4設計。
當k為奇數時，若忽略掉SCS(n，k)的G區組中頂點之間的鄰接關係而將G區組看做頂點集的一個子集，則從一個SCS(n，k)可以得到一個：
(n，k，(k-1)/2)-BIBD.
由於(15，5，2)-BIBD不存在，所以SCS(15，5)也不存在。除這一例外，SCS(n，5)存在的必要條件n≡1，5(mod 10)也是充分條件。史汀生(D.R.Stinson)與泰爾林克(L.Teirlink)指出：當k為奇數時，SCS(n，k)可用於一類密碼問題中的加密方案，但當k>5時，SCS(n，k)的已知結果甚少，當k為奇數時，若存在一個SCS(n，k)，則將每個圈Ck按兩個方向定向得兩個
，所有這些有向圈構成一個(n，k，1)-PMD，由此得SCS(n，k)與正交拉丁方的關係。
相關說明
①完全門德爾森設計是一種特殊類型的圖設計。
以記k個頂點k條弧的有向圈，稱(n，k，λ)設計為門德爾森設計，簡記為(n，k，λ)-MD。若對每一個r(1≤r≤k-1)以及對任意兩個相異頂點x和y，某個(n，k，λ)-MD中恰有λ個G區組含x及y，使每一個這樣的有向圈中從x到y的有向距離為r，則稱該MD為完全門德爾森設計，記為(n，k，λ)-PMD。
若忽略掉G區組中頂點之間的鄰接關係而將G區組看做頂點集的一個子集，則從一個(n，k，λ)-PMD可以得到一個(n，k，λ(k-1))-BIBD。另一方面，從每一點開始按G區組的有向圈方向寫下所有k個頂點作為正交表的一行，這樣可得λn(n-1)個行，再添上λ個形如xx…x行，這裡x取遍n個頂點，於是，可得一個正交表OA(λn，k，n，2)，特別地，當(n，k，1)-PMD存在時，也存在OA(n，k)，這等價於k-2個n階相互正交拉丁方的存在性，因此，(6，5，1)-PMD與(6，6，1)-PMD都不存在。門德爾森(N.S.Mendelsohn)證明：(n，3，λ)-PMD 存在的充分必要條件是
λn(n-1)≡0(mod 3)且(n，λ)≠(6，1).
他還首先研究了(n，4，1)-PMD，指出這樣的設計等價於滿足擬群恆等式yx·xy=x的一個n階冪等擬群。目前，當k=4，5時，(n，k，λ)-PMD的存在性已基本解決。
②G設計是平衡不完全區組設計的一種推廣，設G是有k個頂點且無孤立點的簡單無向圖，λKn是n個頂點的λ重完全無向圖，重邊看做不同的邊，若該完全圖能分解成若干個無公共邊的子圖，每一個都與G同構，則稱這樣的分解為一個圖設計，記為(n，k，λ)G設計。當G=Kk時，一個(n，k，λ)G設計就是一個(n，k，λ)-BIBD。圖設計可以看成BIBD設計的區組中引入點之間的某種鄰接關係後的推廣，這些同構子圖稱為G區組。當G為有向圖時，將λKn改為λ重完全有向圖λKn，可類似定義(n，k，λ)G設計。當G為無向圖且(n，k，λ)G設計存在時，λn(n-1)≡0(mod 2e)且λ(n-1)≡0(mod d)，式中e是圖G的邊數而d是G的所有頂點度數的最大公因數。當G為有向圖且(n，k，λ)G設計存在時，λn(n-1)≡0(mod e)，λ(n-1)≡0(mod d)且
λ(n-1)≡0(mod d)，
式中的e是圖G中弧的條數，而d與d分別是所有頂點的出度數的最大公因數及入度數的最大公因數。
