【正文】 ρ2,…, ρ n。不妨設(shè)λ =ρ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。 極圖 定義 1 若簡(jiǎn)單圖 G的點(diǎn)集 V有一個(gè)劃分 V= ， Vi∩Vj =φ i≠j ?li iV1?且所有 Vi非空， Vi內(nèi)的點(diǎn)均不相鄰，則稱 G是一個(gè) l 部圖。 說明 : (1) 如果 l=2，則 G就是偶圖； (2) 任何一個(gè) n階圖必是一個(gè) n部圖； (3) 若 l1l2≤n，易知任意的 l1部圖也是 l2部圖。 定義 2 如果在一個(gè) l 部圖 G中， |Vi|=ni，任何兩點(diǎn) u∈ Vi ,v ∈ Vj , i≠j , i,j =1,2,…, l 均鄰接，則稱 G為完全 l 部圖。記作 lnnnK , 21 ? v1 v2 v3 v5 v4 v6 K1,2,3 例 注 : 它有 個(gè)點(diǎn)和 條邊。 ll nnnnnn KKKK ???? ?? 2121 ,??li in1 ???? lji jinn1定義 3 如果在一個(gè) n個(gè)點(diǎn)的完全 l 部圖 G中， n = kl + r 0≤rl |V1| = |V2| = … = | Vr| = k + 1。 |Vr+1| = |Vr+2 | = … = | Vl | = k 則稱 G 為 n 階 完全 l 幾乎等部圖 ，記為 Tl ,n。 |V1| = |V2| = … = | Vl | 的完全 l 幾乎等部圖稱為 完全 l 等部圖 。 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部劃分是唯一的。 證明 設(shè)連通偶圖 G 的 2部劃分為 V1∪ V2 =V 。取 v∈ V1 ，由于 G 連通，對(duì)任何 u∈ V1∪ V2 ， G 中有聯(lián)結(jié) u 和 v 的路，故 d (v, u)有定義。因?yàn)槿魏我粭l以 v為起點(diǎn)的路交替地經(jīng)過 V1和 V2 的點(diǎn)，可知一個(gè)點(diǎn) u∈ V2 當(dāng)且僅當(dāng) d (v, u)是奇數(shù)。這準(zhǔn)則唯一地決定了 G的 2部劃分。 定理 17 n階完全偶圖 的邊數(shù) m = n1n2 ，且有 ??????? 42nm21,nnK符號(hào) 表示不大于實(shí)數(shù) x 的最大整數(shù)； ??x??x 表示不小于實(shí)數(shù) x的最小整數(shù) 證明 m = n1n2 是顯然的。 又 m = n1n2 = n1(nn1) = n1n n12 = n2 /4 (n1n/2)2 （配方） ≤ n2 /4 考慮到 m 是正整數(shù)，故 ???????42nm定理 18 n階 l 部圖 G有最多邊數(shù)的充要條件是 G≌ Tl,n。 證明 由代數(shù)學(xué)知， l個(gè)正整數(shù) n1 ,n2 ,…, nl 的函數(shù) ，在約束條件 下達(dá)到極大值的充要條件是對(duì)任何1≤i j≤l，有 |ninj| ≤ 1. ijijf n n???nnli i???1 故若取 nj = k (j = r+1,r+2,… ,l)，而 ni = k +1 ( i= 1,2,… ,r) 使得 |V1| = |V2| = … = | Vr| = ni= k + 1， |Vr+1| = |Vr+2 | = … = |Vr| = nl = k，此時(shí) n階 l部圖 G的邊數(shù)必極大，而這時(shí)的G≌ Tl,n。 下面的定理是 Turan（ 1941）提出的一個(gè)著名的定理。它確定了有 n個(gè)頂點(diǎn)而不包含 Km+1為其子圖的簡(jiǎn)單圖所能具有的最大邊數(shù)。 定理 20 （ Tur225。n）若 G 是簡(jiǎn)單圖，并且不包含 Kl+1，則邊數(shù) m(G)≤m(Tl,n)。此外，僅當(dāng) G ≌ Tl,n 時(shí)有 m(G) = m(Tl,n)。 問題： 一個(gè)小組 n個(gè)人在一個(gè)平原地區(qū)執(zhí)行一項(xiàng)排雷任務(wù)。其中任意的兩個(gè)人，若其距離不超過 g米，則可用無線電保持聯(lián)系；若發(fā)生觸雷意外，地雷的殺傷半徑為 h米。問：在任意的兩個(gè)人之間均能保持聯(lián)系的條件下，若發(fā)生意外，平均傷亡人數(shù)最低的可能值為多少？ Tur225。n定理的一個(gè)應(yīng)用 對(duì)此問題，按問題的條件若某人 A觸雷，則與 A的距離大于 h米的人將是安全的，但究竟哪個(gè)人會(huì)發(fā)生觸雷意外，事先是不知道的，所以此問題實(shí)際上是求在任意的兩個(gè)人之間的距離不超過 g米的條件下，距離大于等于 h米的人數(shù)對(duì)最多能達(dá)到多少對(duì)。為建立此問題的數(shù)學(xué)模型，先引入平面點(diǎn)集的直徑這一概念。 有限平面點(diǎn)集 A的直徑 : 指 A中點(diǎn)對(duì)的距離的最大值 , 其中距離是指歐氏距離。 先前的問題可轉(zhuǎn)化為計(jì)算在直徑為 g 的點(diǎn)集 {x1, x2,…, xn}中最多有多少點(diǎn)對(duì)，其距離大于 h。下面我們對(duì) g =1， h = 展開討論。 2/1 先觀察 n = 6時(shí)平面點(diǎn)集的分布的兩種特殊情況。一種情況為六個(gè)點(diǎn) x1, x2, x3, x4, x5和 x6位于一個(gè)正六邊形的頂點(diǎn)上，并使點(diǎn)對(duì)（ x1, x4），（ x2, x5）和（ x3, x6）的距離為 1，如圖 1。 x1 x6 1/2 1/4 x2 A 0 x5 x3 x4 圖 1 容易計(jì)算該點(diǎn)集的直徑為 1，線段 x1 A的長(zhǎng) ， Ax5的長(zhǎng)為 3/4（ x1A, Ax5如圖所示），從而可計(jì)算出 x1與 x5的距離為 。同理，點(diǎn)對(duì)（ x1, x3） ,（ x2, x4） ,（ x2, x6） ,（x3, x5） ,（ x4, x6）均為 。因 。所以此種情況距離大于 的點(diǎn)對(duì)有 9對(duì)。 4/32/32/3 2/3 2/22/2 下面的定理回答了 12已是最大數(shù)目。該定理的證明用到 Tur225。n定理。 x1 x4 B x5 x6 x2 A x3 圖 2 另一種情況如圖 2所示。其中 x1, x2和 x3處于一個(gè)邊長(zhǎng)為 1的正三角形的頂點(diǎn)上； x4, x5和 x6也位于一個(gè)正三角形的頂點(diǎn)上。由于線段 x2 A的長(zhǎng)為 1/2，可使線段 x5 B的長(zhǎng)大于 。這是可以實(shí)現(xiàn)的。這樣 , 除點(diǎn)對(duì)（ x1, x4） ,（ x2, x5） ,（ x3, x6）外，其余十二個(gè)點(diǎn)對(duì)的距離均大于 。 2/24/2定理 21 設(shè) A={x1, x2,…, xn}為任意一個(gè)直徑為 1的平面點(diǎn)集，則 A中距離大于 的點(diǎn)對(duì)的最大數(shù)目為 。并且對(duì)每個(gè) n，存在直徑為 1的點(diǎn)集 A* = {x1, x2,…, xn}，它恰有 個(gè)點(diǎn)對(duì)，其距離大于 。 2/2 ? ?3/2n? ?3/2n 2/2 由定理 21， n=6 時(shí)， 。所以圖 2的 12是最大數(shù)目。 ? ? 123/363/2 ??nThank you