帶洞G設計

帶洞G設計(G-design with holes)亦稱帶洞圖設計,是用於遞推構作圖設計的一類輔助設計。

設.1Kn,.nZ.. ,}*是幾重h部無向完全圖,頂點集X劃分為互不相交的X},Xz,... }Xh,使設G為k個頂點且無孤立點的無向簡單圖.若該多部完全圖能分解成若干個無公共邊的子圖,每一個都與G同構,則稱這樣的分解為一個帶洞((n,k,.})G設計,稱((n},n2,...}nh)為其型.這樣的G設計可以看做.1K。的通常G設計中帶有一些洞XX2, ...Xh,當G=K*時這些洞實際上是可分組設計的組.若每個頂點在G區組中出現的次數相同,則稱這種帶洞圖設計是平衡的.利用帶洞圖設計可以遞推地構造圖設計.若存在型為((nnZ , ".. } nh)的帶洞((n ,k,.1)G設計,且對每i(1簇i簇h)存在((n;+E,k,.l)G設計,其中。一。或1,則存在((n}--s,k,.})G設計.特別地,若存在型為((L,L,}}},L)的平衡帶洞(hl,k,})G設計,且存在平衡的((l-}e,k,.})G設計,其中。一。或1,則存在平衡的(hl+e,k,.})G設計.對於有向圖情形,也可類似定義帶洞圖設計概念,並且,有相應的遞推構造圖設計的方法.

相關詞條

熱門詞條

聯絡我們