G設計(G-design)是平衡不完全區組設計的一種推廣，設G是有k個頂點且無孤立點的簡單無向圖，λKn是n個頂點的λ重完全無向圖，重邊看做不同的邊，若該完全圖能分解成若干個無公共邊的子圖，每一個都與G同構，則稱這樣的分解為一個圖設計，記為(n，k，λ)G設計。
基本介紹
- 中文名：G設計
- 外文名：G-design
- 所屬學科：數學（組合學）
- 簡介：平衡不完全區組設計的一種推廣
基本介紹,平衡G設計,帶洞G設計,
基本介紹
當
時，一個
設計就是一個
。圖設計可以看成BIBD設計的區組中引入點之間的某種鄰接關係後的推廣，這些同構子圖稱為G區組。當G為有向圖時，將
改為λ重完全有向圖
，可類似定義 設計。當G為無向圖且 設計存在時，
且
，式中e是圖G的邊數而d是G的所有頂點度數的最大公因數。當G為有向圖且 設計存在時，
，
且
式中的e是圖G中弧的條數，而d+與d-分別是所有頂點的出度數的最大公因數及入度數的最大公因數。
黑爾(P.Hell)和羅薩(A.Rosa)於1972年首先引入了圖設計這一概念，並研究了
設計的存在性，這裡Pk表示k個頂點k-1條邊的路，由於圖G的變化千姿百態，G設計的存在性研究面廣量大，已有結果大多是關於路和圈這些簡單而規則的圖G的，只有當k較小時才考察所有可能的圖G，而完整的結果僅限於k=3，4的情形，圖設計的直接構造方法是玻色(R.C.Bose)的對稱重差法的變形，而遞推構造方法則主要利用多部完全圖的分解，與BIBD設計的情形類似，也有可分解性問題以及平衡圖設計問題。
平衡G設計
平衡G設計是一類特殊的G設計，若在一個G設計中每個頂點在G區組中出現的次數都相同，則稱該圖設計是平衡G設計。當G為正則無向圖(即頂點的度數均相同的圖)或強正則有向圖(即每個頂點的出度數和入度數為同一個常數的圖)時，G設計總是平衡的，平衡G設計的參數除必須滿足一般G設計的必要條件外，還必須滿足進一步的條件：當G為無向圖時，應有
帶洞G設計
帶洞G設計亦稱帶洞圖設計，用於遞推構作G設計的一類輔助設計。設
是λ重h部無向完全圖，頂點集X劃分為互不相交的
，使
