【正文】 0 1 0 2 0 0 2 0 1 0 0 1 1 推廣的 鄰接矩陣 A = 我們有： 1 0 2 0 0 5 0 2 2 0 5 1 0 2 1 2 A 2= 圖中 v1到 v1 的長(zhǎng)為 2的的通道的數(shù)目為 1 v1到 v2 的長(zhǎng)為 2的的通道的數(shù)目為 0 v1到 v3 的長(zhǎng)為 2的的通道的數(shù)目為 2 v1到 v4的長(zhǎng)為 2的的通道的數(shù)目為 0 v2到 v2 的長(zhǎng)為 2的的通道的數(shù)目為 5 定理 10 令 G是一個(gè)有推廣鄰接矩陣 A的 p階標(biāo)定圖，則 An的 i 行 j 列元素 等于由 vi到 vj的長(zhǎng)度為 n的通道的數(shù)目。 由于 aik是聯(lián)結(jié) vi和 vk的長(zhǎng)度為 1的通道的數(shù)目， akj(n)是聯(lián)結(jié) vk和 vj的長(zhǎng)度為 n的通道的數(shù)目，所以 aikakj(n) 表示由 vi經(jīng)過(guò) vk到 vj的長(zhǎng)度為 n+1的通道 數(shù)目。也即 aij(n+1) 為由 vi 到 vj 的長(zhǎng)度為 n+1的通道 數(shù)目。 推論 設(shè) A為簡(jiǎn)單圖 G的鄰接矩陣，則 （ 1） A2 的元素 aii(2) 是 vi 的度數(shù)。 （ 2） 若 G是連通的，對(duì)于 i≠j， vi 與 vj 之間的距離是使An 的 aij(n) ≠0 的最小整數(shù) n。 v1 e1 e5 v2 v5 e6 e7 e2 e4 v3 e3 v4 例 B = e1 e2 e3 e4 e5 e6 e7 v1 v2 v3 v4 v5 ????????????????00110001001100010011000000111110001說(shuō)明： 定義中“無(wú) 環(huán)”的條件可去掉，此時(shí) bij =點(diǎn) vi 與邊 ej 關(guān)聯(lián)的次數(shù)（ 0, 1, 2(環(huán) )). 性質(zhì)： 關(guān)聯(lián)矩陣的每列和為 2；其行和為對(duì)應(yīng)頂點(diǎn)的度數(shù) . 例如： e1 v4 v3 v2 v1 e7 e5 e4 e3 e2 e6 1 1 0 0 1 0 11 1 1 0 0 0 0()0 0 1 1 0 0 10 0 0 1 1 2 0MG?????????三、鄰接代數(shù) 給定圖 G , 容易驗(yàn)證 G 的鄰接矩陣的全體復(fù)系數(shù)多項(xiàng)式在通常的矩陣運(yùn)算下構(gòu)成一個(gè)有限維的線性空間，它也是一個(gè)代數(shù)，稱為圖 G的鄰接代數(shù)，記為 Λ(G)。 定理 11 n階連通圖 G的鄰接代數(shù)的維數(shù)有 d(G)＋１ ≤dimΛ(G)≤n 回憶線性代數(shù)的一些概念。 A的行（列）組成的 n維向量稱為 A的行（列）向量。 實(shí)際上 λ是方程 |λInA | = 0 （ 2）的根，其中 In為 n階單位矩陣。 例 1 設(shè) A 為 4圈 C4 的鄰接矩陣，求 A的譜。 所以 A 的特征值為 2 , 0, 2 。故 Spec A = ??????? 121 202 對(duì)于左邊的不等式，因 A(G) 是對(duì)稱的，故不同的特征值的數(shù)目 s 等于最小多項(xiàng)式的次數(shù)，即等于鄰接代數(shù)的 Λ(G)的維數(shù)，于是所要的不等式由定理 11得到。 ??si iim1 2? 而 [A(G) ]2的跡有 ??niiia1)2( mvdnii 2)(1?? ??定理 10的推論及握手定理 mmsiii 212 ????故 證明 設(shè) A(G)的 n 個(gè)特征值為 ρ1, ρ2,…, ρ n。對(duì)向量 (1,1,…,1) 和 (ρ1, ρ2,…, ρ n1) 應(yīng)用許瓦茲（ Schwarz）不等式，得 ??????????211nii? ????112)1(niin ?（ ） 定理 15 設(shè) λ是 A(G)的任一特征值，則 nnm )1(2 ?????????? 121 202如 4圈 的譜 : 有 (2)2+22=8 因鄰接矩陣 A(G)的對(duì)角元全為零 , 故 ??nii1? 01?? ??niiia于是 ?????? 11niin ???又由定理 14知 mnii 212 ????故 2112 2 ?? ?????mnii這樣（ ）式變成 (λ)2≤(n1)(2mλ2) 即 nλ2≤2m(n1) 故 nnm )1(2 ???例 C4中 , n=4, m=4, 故 64 )14(42 ???????????????211nii? ???? 112)1( niin ?（ ） 2112 2 ?? ?????mnii ?????? 11niin ???167。 說(shuō)明 : (1) 如果 l=2，則 G就是偶圖； (2) 任何一個(gè) n階圖必是一個(gè) n部圖； (3) 若 l1l2≤n，易知任意的 l1部圖也是 l2部圖。記作 lnnnK , 21 ? v1 v2 v3 v5 v4 v6 K1,2,3 例 注 : 它有 個(gè)點(diǎn)和 條邊。 |Vr+1| = |Vr+2 | = … = | Vl | = k 則稱 G 為 n 階 完全 l 幾乎等部圖 ，記為 Tl ,n。 v1 v2 v3 v4 v5 v6 考察 1. 這是一個(gè)連通的 3部圖 , 點(diǎn)集 V 的劃分為 : V1= {v4}， V2 = {v3 ,v5}， V3 ={v1 ,v2 ,v6 } 2. V 的劃分也可為 V1= {v1,v5}， V2 = {v2 ,v3}，V3 = {v4 ,v6 } 3. 這也是一個(gè) 2部圖 , 點(diǎn)集 的劃分為 : V1= {v4 ,v2 ,v6 }， V2 = {v1,v3 ,v5},且劃分唯一 定理 16 連通偶圖的 2部劃分是唯一的。取 v∈ V1 ，由于 G 連通，對(duì)任何 u∈ V1∪ V2 ， G 中有聯(lián)結(jié) u 和 v 的路，故 d (v, u)有定義。這準(zhǔn)則唯一地決定了 G的 2部劃分。 又 m = n1n2 = n1(nn1) = n1n n12 = n2 /4 (n1n/2)2 （配方） ≤ n2 /4 考慮到 m 是正整數(shù)，故 ???????42nm定理 18 n階 l 部圖 G有最多邊數(shù)的充要條件是 G≌ Tl,n。 下面的定理是 Turan（ 1941）提出的一個(gè)著名的定理。 定理 20 （ Tur225。此外，僅當(dāng) G ≌ Tl,n 時(shí)有 m(G) = m(Tl,n)。其中任意的兩個(gè)人，若其距離不超過(guò) g米，則可用無(wú)線電保持聯(lián)系；若發(fā)生觸雷意外，地雷的殺傷半徑為 h米。n定理的一個(gè)應(yīng)用 對(duì)此問(wèn)題，按問(wèn)題的條件若某人 A觸雷，則與 A的距離大于 h米的人將是安全的，但究竟哪個(gè)人會(huì)發(fā)生觸雷意外，事先是不知道的，所以此問(wèn)題實(shí)際上是求在任意的兩個(gè)人之間的距離不超過(guò) g米的條件下，距離大于等于 h米的人數(shù)對(duì)最多能達(dá)到多少對(duì)。 有限平面點(diǎn)集 A的直徑 : 指 A中點(diǎn)對(duì)的距離的最大值 , 其中距離是指歐氏距離。下面我們對(duì) g =1， h = 展開討論。一種情況為六個(gè)點(diǎn) x1, x2, x3, x4, x5和 x6位于一個(gè)正六邊形的頂點(diǎn)上，并使點(diǎn)對(duì)（ x1, x4），（ x2, x5）和（ x3, x6）的距離為 1，如圖 1。同理，點(diǎn)對(duì)（ x1, x3） ,（ x2, x4） ,（ x2, x6） ,（x3, x5） ,（ x4, x6）均為 。所以此種情況距離大于 的點(diǎn)對(duì)有 9對(duì)。該定理的證明用到 Tur225。 x1 x4 B x5 x6 x2 A x3 圖 2 另一種情況如圖 2所示。由于線段 x2 A的長(zhǎng)為 1/2，可使線段 x5 B的長(zhǎng)大于 。這樣 , 除點(diǎn)對(duì)（ x1, x4） ,（ x2, x5） ,（ x3, x6）外，其余十二個(gè)點(diǎn)對(duì)的距離均大于 。并且對(duì)每個(gè) n，存在直徑為 1的點(diǎn)集 A* = {x1, x2,…, xn}，它恰有 個(gè)點(diǎn)對(duì)，其距離大于 。所以圖 2的 12是最大數(shù)