度量方案

度量方案

度量方案(metric scheme)是一類結合方案,它由距離正則圖定義,若Γ為直徑d的距離正則圖,規定兩個頂點的距離為i時它們有第i種結合關係,則在Γ的頂點集合上有一個d個結合類的結合方案,稱為度量方案

基本介紹

  • 中文名:度量方案
  • 外文名:metric scheme
  • 所屬學科:數學(組合學)
  • 簡介:由距離正則圖定義的一類結合方案
基本介紹,舉例,約翰生結合方案,漢明結合方案,

基本介紹

度量方案由距離正則圖定義,若Γ為直徑d的距離正則圖,規定兩個頂點的距離為i時它們有第i種結合關係,則在Γ的頂點集合上有一個d個結合類的結合方案,稱為度量方案。許多最重要的結合方案都是度量方案。例如,具兩個結合類的結合方案一定是度量方案。漢明結合方案與約翰生結合方案也都是度量方案。但是,並非所有的結合方案都是度量方案。
距離正則圖(distance-regular graph)是一類與結合方案有關的圖,設Γ是一個連通圖,有v個頂點,無環邊及重邊,Γ中兩頂點間的距離是連結這兩點的最短路所含的邊數,Γ中任意兩個頂點之間距離的最大值稱為Γ的直徑,若對Γ中距離為k的任意兩個頂點x,y,與x的距離為i且與y的距離為j的頂點z的個數是一個常數Cijk,與x,y的選擇無關,則稱Γ為距離正則圖,直徑為2的距離正則圖稱為強正則圖。

舉例

約翰生結合方案

約翰生結合方案(Johnson association scheme)亦稱三角形結合方案,是一類度量方案,設k≤v/2,以J(v,k)記某個v元集的k元子集的全體,若當兩個k元子集的交為k-i元子集時,規定它們有第i種結合關係,則J(v,k)是有
個處理及k個結合類的結合方案,稱為約翰生結合方案。當k=2時,約翰生結合方案即為三角形設計中的結合方案。約翰生結合方案在編碼理論中也有重要套用,例如,每一個等重量碼都可看做某個約翰生結合方案中的子集。

漢明結合方案

漢明結合方案(Hamming association scheme)亦稱超立方體結合方案,是一類度量方案,結合方案的一種,設H(n,q)是一個q元集合上的有n個分量的有序組的全體,若兩個有序組恰好在i個位置上的分量不同,則稱它們的漢明距離為i,將H(m,q)取作處理的集合,兩個有序組的漢明距離為i時稱它們有第i種結合關係,便得到具q個處理及n個結合類的結合方案,稱為漢明結合方案。
例如,當n=3且q=2時,漢明方案可用下面的立方體表示,立方體的8個頂點表示方案的8個處理,從頂點x到頂點y若至少需經過i條邊,則表示處理x與處理y有第i種結合關係。漢明結合方案中的一個子集稱為一個碼,因此漢明結合方案在編碼理論中有重要的套用一類結合方案。
圖1圖1

相關詞條

熱門詞條

聯絡我們