-
張圖
鎖定
- 中文名
- 張圖
- 外文名
- 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),它們被稱為張圖,名稱由此而來。
[1]
張圖相關概念
張圖距離正則圖
距離正則圖(distance-regular graph)是一類與結合方案有關的圖,設Γ是一個連通圖,有v個頂點,無環邊及重邊,Γ中兩頂點間的距離是連結這兩點的最短路所含的邊數,Γ中任意兩個頂點之間距離的最大值稱為Γ的直徑,若對Γ中距離為k的任意兩個頂點x,y,與x的距離為i且與y的距離為j的頂點z的個數是一個常數Cijk,與x,y的選擇無關,則稱Γ為距離正則圖,直徑為2的距離正則圖稱為強正則圖
[1]
。
張圖度量方案
度量方案(metric scheme)是一類結合方案,由距離正則圖定義,若Γ為直徑d的距離正則圖,規定兩個頂點的距離為i時它們有第i種結合關係,則在Γ的頂點集合上有一個d個結合類的結合方案,稱為度量方案。許多最重要的結合方案都是度量方案。例如,具兩個結合類的結合方案一定是度量方案。漢明結合方案與約翰生結合方案也都是度量方案。但是,並非所有的結合方案都是度量方案
[1]
。
張圖約翰生結合方案
約翰生結合方案(Johnson association scheme)亦稱三角形結合方案,是一類度量方案,設k≤v/2,以J(v,k)記某個v元集的k元子集的全體,若當兩個k元子集的交為k-i元子集時,規定它們有第i種結合關係,則J(v,k)是有