[科普中國]-施泰納k圈系統(tǒng)

施泰納k圈系統(tǒng)(Steiner k-cycle system)是一類特殊的圖設(shè)計(jì)，以Ck表示k個(gè)頂點(diǎn)k條邊的圈無向圖，若對(duì)任意r(1≤r5時(shí)，SCS(n，k)的已知結(jié)果甚少，當(dāng)k為奇數(shù)時(shí)，若存在一個(gè)SCS(n，k)，則將每個(gè)圈Ck按兩個(gè)方向定向得兩個(gè)，所有這些有向圈構(gòu)成一個(gè)(n，k，1)-PMD，由此得SCS(n，k)與正交拉丁方的關(guān)系1。

相關(guān)說明①完全門德爾森設(shè)計(jì)是一種特殊類型的圖設(shè)計(jì)。

以記k個(gè)頂點(diǎn)k條弧的有向圈，稱(n，k，λ)設(shè)計(jì)為門德爾森設(shè)計(jì)，簡記為(n，k，λ)-MD。若對(duì)每一個(gè)r(1≤r≤k-1)以及對(duì)任意兩個(gè)相異頂點(diǎn)x和y，某個(gè)(n，k，λ)-MD中恰有λ個(gè)G區(qū)組含x及y，使每一個(gè)這樣的有向圈中從x到y(tǒng)的有向距離為r，則稱該MD為完全門德爾森設(shè)計(jì)，記為(n，k，λ)-PMD。

若忽略掉G區(qū)組中頂點(diǎn)之間的鄰接關(guān)系而將G區(qū)組看做頂點(diǎn)集的一個(gè)子集，則從一個(gè)(n，k，λ)-PMD可以得到一個(gè)(n，k，λ(k-1))-BIBD。另一方面，從每一點(diǎn)開始按G區(qū)組的有向圈方向?qū)懴滤衚個(gè)頂點(diǎn)作為正交表的一行，這樣可得λn(n-1)個(gè)行，再添上λ個(gè)形如xx…x行，這里x取遍n個(gè)頂點(diǎn)，于是，可得一個(gè)正交表OA(λn2，k，n，2)，特別地，當(dāng)(n，k，1)-PMD存在時(shí)，也存在OA(n，k)，這等價(jià)于k-2個(gè)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，指出這樣的設(shè)計(jì)等價(jià)于滿足擬群恒等式y(tǒng)x·xy=x的一個(gè)n階冪等擬群。目前，當(dāng)k=4，5時(shí)，(n，k，λ)-PMD的存在性已基本解決。

②G設(shè)計(jì)是平衡不完全區(qū)組設(shè)計(jì)的一種推廣，設(shè)G是有k個(gè)頂點(diǎn)且無孤立點(diǎn)的簡單無向圖，λKn是n個(gè)頂點(diǎn)的λ重完全無向圖，重邊看做不同的邊，若該完全圖能分解成若干個(gè)無公共邊的子圖，每一個(gè)都與G同構(gòu)，則稱這樣的分解為一個(gè)圖設(shè)計(jì)，記為(n，k，λ)G設(shè)計(jì)。當(dāng)G=Kk時(shí)，一個(gè)(n，k，λ)G設(shè)計(jì)就是一個(gè)(n，k，λ)-BIBD。圖設(shè)計(jì)可以看成BIBD設(shè)計(jì)的區(qū)組中引入點(diǎn)之間的某種鄰接關(guān)系后的推廣，這些同構(gòu)子圖稱為G區(qū)組。當(dāng)G為有向圖時(shí)，將λKn改為λ重完全有向圖λK*n，可類似定義(n，k，λ)G設(shè)計(jì)。當(dāng)G為無向圖且(n，k，λ)G設(shè)計(jì)存在時(shí)，λn(n-1)≡0(mod 2e)且λ(n-1)≡0(mod d)，式中e是圖G的邊數(shù)而d是G的所有頂點(diǎn)度數(shù)的最大公因數(shù)。當(dāng)G為有向圖且(n，k，λ)G設(shè)計(jì)存在時(shí)，λn(n-1)≡0(mod e)，λ(n-1)≡0(mod d+)且1

λ(n-1)≡0(mod d-)，

式中的e是圖G中弧的條數(shù)，而d+與d-分別是所有頂點(diǎn)的出度數(shù)的最大公因數(shù)及入度數(shù)的最大公因數(shù)。

黑爾(P.Hell)和羅薩(A.Rosa)于1972年首先引入了圖設(shè)計(jì)這一概念，并研究了(n，k，λ)Pk設(shè)計(jì)的存在性，這里Pk表示k個(gè)頂點(diǎn)k-1條邊的路，由于圖G的變化千姿百態(tài)，G設(shè)計(jì)的存在性研究面廣量大，已有結(jié)果大多是關(guān)于路和圈這些簡單而規(guī)則的圖G的，只有當(dāng)k較小時(shí)才考察所有可能的圖G，而完整的結(jié)果僅限于k=3，4的情形，圖設(shè)計(jì)的直接構(gòu)造方法是玻色(R.C.Bose)的對(duì)稱重差法的變形，而遞推構(gòu)造方法則主要利用多部完全圖的分解，與BIBD設(shè)計(jì)的情形類似，也有可分解性問題以及平衡圖設(shè)計(jì)問題1。

本詞條內(nèi)容貢獻(xiàn)者為:

任毅如 - 副教授 - 湖南大學(xué)