[科普中國]-G設(shè)計

G設(shè)計(G-design)是平衡不完全區(qū)組設(shè)計的一種推廣，設(shè)G是有k個頂點且無孤立點的簡單無向圖，λKn是n個頂點的λ重完全無向圖，重邊看做不同的邊，若該完全圖能分解成若干個無公共邊的子圖，每一個都與G同構(gòu)，則稱這樣的分解為一個圖設(shè)計，記為(n，k，λ)G設(shè)計1。

基本介紹當(dāng) 時，一個 設(shè)計就是一個 。圖設(shè)計可以看成BIBD設(shè)計的區(qū)組中引入點之間的某種鄰接關(guān)系后的推廣，這些同構(gòu)子圖稱為G區(qū)組。當(dāng)G為有向圖時，將 改為λ重完全有向圖 ，可類似定義 設(shè)計。當(dāng)G為無向圖且 設(shè)計存在時， 且 ，式中e是圖G的邊數(shù)而d是G的所有頂點度數(shù)的最大公因數(shù)。當(dāng)G為有向圖且 設(shè)計存在時， ， 且

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

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

平衡G設(shè)計平衡G設(shè)計是一類特殊的G設(shè)計，若在一個G設(shè)計中每個頂點在G區(qū)組中出現(xiàn)的次數(shù)都相同，則稱該圖設(shè)計是平衡G設(shè)計。當(dāng)G為正則無向圖(即頂點的度數(shù)均相同的圖)或強正則有向圖(即每個頂點的出度數(shù)和入度數(shù)為同一個常數(shù)的圖)時，G設(shè)計總是平衡的，平衡G設(shè)計的參數(shù)除必須滿足一般G設(shè)計的必要條件外，還必須滿足進一步的條件：當(dāng)G為無向圖時，應(yīng)有

當(dāng)G為有向圖時，應(yīng)有

當(dāng)G為k個頂點k-1條邊的路或星形圖時，平衡設(shè)計存在的必要條件也是充分條件，當(dāng)且G為無向圖時，平衡設(shè)計的存在性也已得到完全解決1。

帶洞G設(shè)計帶洞G設(shè)計亦稱帶洞圖設(shè)計，用于遞推構(gòu)作G設(shè)計的一類輔助設(shè)計。設(shè)是λ重h部無向完全圖，頂點集X劃分為互不相交的，使

設(shè)G為k個頂點且無孤立點的無向簡單圖，若該多部完全圖能分解成若干個無公共邊的子圖，每一個都與G同構(gòu)，則稱這樣的分解為一個帶洞設(shè)計，稱為其型，這樣的G設(shè)計可以看做的通常G設(shè)計中帶有一些洞，當(dāng)時這些洞實際上是可分組設(shè)計的組，若每個頂點在G區(qū)組中出現(xiàn)的次數(shù)相同，則稱這種帶洞圖設(shè)計是平衡的，利用帶洞圖設(shè)計可以遞推地構(gòu)造圖設(shè)計，若存在型為的帶洞設(shè)計，且對每存在設(shè)計，其中ε=0或1，則存在設(shè)計。特別地，若存在型為(l，l，…，l)的平衡帶洞設(shè)計，且存在平衡的設(shè)計，其中ε=0或1，則存在平衡的設(shè)計，對于有向圖情形，也可類似定義帶洞圖設(shè)計概念，并且，有相應(yīng)的遞推構(gòu)造圖設(shè)計的方法1。

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

王海俠 - 副教授 - 南京理工大學(xué)