[科普中國]-張圖

張圖(Chang graphs)是一種重要的圖組，由張里千于1960年發(fā)現(xiàn)，它是與三角形圖T(8)具有相同參數(shù)但互不同構(gòu)的三個(gè)強(qiáng)正則圖1。

基本介紹張圖是由張里千于1960年發(fā)現(xiàn)，它是與三角形圖T(8)具有相同參數(shù)但互不同構(gòu)的三個(gè)強(qiáng)正則圖。三角形設(shè)計(jì)中所出現(xiàn)的結(jié)合方案是一個(gè)約翰生結(jié)合方案J(n，2)，因而是一個(gè)度量方案，相應(yīng)的距離正則圖是強(qiáng)正則圖，記為T(n)，稱為三角形圖，張里千于1959年、霍夫曼(A.J.Hoffman)于1960年證明：若Γ為與三角形圖T(n)有相同參數(shù)的強(qiáng)正則圖，則當(dāng)n>8時(shí)，Γ與T(n)同構(gòu)，當(dāng)n=4，5，6，7時(shí)，上述結(jié)論也成立，張里千指出：當(dāng)n=8時(shí)，除T(8)外，恰有三個(gè)與T(8)有相同參數(shù)但不同構(gòu)的強(qiáng)正則圖，通常記為T′(8)，T"(8)及T〞(8)，它們被稱為張圖，名稱由此而來。1

相關(guān)概念距離正則圖距離正則圖(distance-regular graph)是一類與結(jié)合方案有關(guān)的圖，設(shè)Γ是一個(gè)連通圖，有v個(gè)頂點(diǎn)，無環(huán)邊及重邊，Γ中兩頂點(diǎn)間的距離是連結(jié)這兩點(diǎn)的最短路所含的邊數(shù)，Γ中任意兩個(gè)頂點(diǎn)之間距離的最大值稱為Γ的直徑，若對(duì)Γ中距離為k的任意兩個(gè)頂點(diǎn)x，y，與x的距離為i且與y的距離為j的頂點(diǎn)z的個(gè)數(shù)是一個(gè)常數(shù)Cijk，與x，y的選擇無關(guān)，則稱Γ為距離正則圖，直徑為2的距離正則圖稱為強(qiáng)正則圖1。

度量方案度量方案(metric scheme)是一類結(jié)合方案，由距離正則圖定義，若Γ為直徑d的距離正則圖，規(guī)定兩個(gè)頂點(diǎn)的距離為i時(shí)它們有第i種結(jié)合關(guān)系，則在Γ的頂點(diǎn)集合上有一個(gè)d個(gè)結(jié)合類的結(jié)合方案，稱為度量方案。許多最重要的結(jié)合方案都是度量方案。例如，具兩個(gè)結(jié)合類的結(jié)合方案一定是度量方案。漢明結(jié)合方案與約翰生結(jié)合方案也都是度量方案。但是，并非所有的結(jié)合方案都是度量方案1。

約翰生結(jié)合方案約翰生結(jié)合方案(Johnson association scheme)亦稱三角形結(jié)合方案，是一類度量方案，設(shè)k≤v/2，以J(v，k)記某個(gè)v元集的k元子集的全體，若當(dāng)兩個(gè)k元子集的交為k-i元子集時(shí)，規(guī)定它們有第i種結(jié)合關(guān)系，則J(v，k)是有

個(gè)處理及k個(gè)結(jié)合類的結(jié)合方案，稱為約翰生結(jié)合方案。當(dāng)k=2時(shí)，約翰生結(jié)合方案即為三角形設(shè)計(jì)中的結(jié)合方案。約翰生結(jié)合方案在編碼理論中也有重要應(yīng)用，例如，每一個(gè)等重量碼都可看做某個(gè)約翰生結(jié)合方案中的子集。

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

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