基本介紹
- 中文名：張圖
- 外文名：Chang graphs
- 所屬學科：數學（組合學）
- 簡介：一種重要的圖組
- 提出者：張千里
基本介紹,相關概念,距離正則圖,度量方案,約翰生結合方案,
基本介紹
張圖是由張里千於1960年發現，它是與三角形圖T(8)具有相同參數但互不同構的三個強正則圖。三角形設計組雄中所出現的結合方案是一個約翰生結合方案J(n，2)，因而是一個度量方案，相應的距離正則嚷敬翻圖是強正則圖，記為T(n)，稱為三角形圖，張里千於1959年、霍夫曼(A.J.Hoffman)於1960年證明：若Γ為與三角形圖T(n)有相同參數的強正則圖，則當n>8時，Γ與T(n)同構，當n=4，5，6，7時，上述結論也成立，張里千指出：當n=8時，除員尋棗員T(8)外，恰有三個與T(8)有相同參數但不同構的強正則圖，通常記為T′(8)，T"(8)及T〞(8)，它們被稱為張圖，名稱由此而來。
相關概念
距離正則圖
距離正則圖(distance-regular graph)是一類與結合方案有關的圖，設Γ是一個連通圖，有v個頂點，無環邊及重邊，Γ中兩頂點間的距離是連結這兩點的最短路所含的邊數，Γ中任意兩個頂點之間距離的最大值稱為Γ的直徑，若對Γ中距離為k的任意兩個頂點x，y，與x的距離為i且與y的距離為j的頂點z的個數是一個常數Cijk，與x，y的選擇無關，則稱Γ為距離正則圖，直徑為2的距離正則圖稱為強正則圖。
度量方案
度量方案(metric scheme)是一類結合方案，由距離正則圖定義，若Γ為直徑d的距離正則圖，規定兩個頂點的距離為i時它們有第i種結合關係，則在Γ的頂點集合上有一個d個結合類的結合方案，稱為度量方案。許多最重笑踏勸要的結合方案都是度量方案。例如，具兩個結合類的結合方案一定是度量方案。漢明結合方案與約翰生結合方案也都是度量方案。但是，並非所有的結合方案都是度量方案。
約翰生結合方案
約翰生結合方案(Johnson association scheme)亦稱三角形結合方案，是一類度量方案，設k≤v/2，以J(v，k)記某個v元集的k元子集的全體，若當兩個k元子集的交為k-i元子集時，規淚連紋祖定它們有旬盛符第i種結合關係，則J(v，k)是有享跨棕
