習題參考解答
習題十1. 設g是乙個(n，m)簡單圖。證明：，等號成立當且僅當g是完全圖。
證明：（1）先證結論：
因為g是簡單圖，所以g的結點度上限 max(d(v)) ≤ n-1, g圖的總點度上限為 max(σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根據握手定理，g圖邊的上限為 max(m) ≤ n(n-1)/2,所以。
（2）=〉g是完全圖
因為g具有上限邊數，假設有結點的點度小於n-1,那麼g的總度數就小於上限值，邊數就小於上限值，與條件矛盾。所以，g的每個結點的點度都為n-1，g為完全圖。
g是完全圖 =〉
因為g是完全圖，所以每個結點的點度為n-1, 總度數為n(n-1)，根據握手定理，圖g的邊數。■
2. 設g是乙個（n，n+1）的無向圖，證明g中存在頂點u，d（u）≥3。
證明：反證法，假設,則g的總點度上限為max(σ(d(u)) ≤2 n，根據握手定理，圖邊的上限為max(m) ≤ 2n/2=n。與題設m = n+1，矛盾。
因此，g中存在頂點u，d（u）≥3。■
3．確定下面的序列中哪些是圖的序列，若是圖的序列，畫出乙個對應的圖來:
（1）（3，2，0，1，5）； （2）（6，3，3，2，2）
（3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）
解：除序列（1）不是圖序列外，其餘的都是圖序列。因為在（1）中，總和為奇數，不滿足圖總度數為偶數的握手定理。
可以按如下方法構造滿足要求的圖：序列中每個數字ai對應乙個點，如果序列數字是偶數，那麼就在對應的點上畫ai/2個環，如果序列是奇數，那麼在對應的點上畫(ai-1)/2個環。最後，將奇數序列對應的點兩兩一組，新增連線即可。
下面以（2）為例說明：
(6 , 3, 3, 2, 2 ) 對應圖g的點集合v=
每個結點對應的環數(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
將奇數3，3 對應的結點v2,v3一組，畫一條連線
其他序列可以類式作圖，當然大家也可以畫圖其它不同的圖形。■
4．證明：在（n，m）圖中。
證明：圖的點度數是一組非負整數，那麼這組數的算術平均值一定大於等於其中的最小值，同時小於等於其中的最大值。對應到圖的術語及為：
最大值為，最小值為δ，平均值 = (d(v1)+d(v2)…+d(vn))/n = 2m/n,所以。■
5．證明定理10.2。
【定理10.2】 對於任何（n,m）有向圖g =（v，e），
證明：有向圖中,每條有向邊為圖貢獻一度出度，同時貢獻一度出度，所以總出度和總入度相等，並和邊數相等。因此，上述關係等式成立。■
6．設g是（n，m）簡單二部圖，證明：。
證明：本題目，我們是需要說明n階的簡單二部圖的邊數的最大值 =即可。
設n階的簡單二部圖，其兩部分結點集合分別為v1，v2,那麼|v1| + |v2| = n。此種情況下，當g為完全二部圖時，有最多的邊數，即max(m) = |v1||v2|,變形為，max(m) =( n-|v2|)|v2|.此函式的最大值及為n階二部圖的邊的上限值，其上限值為當|v2|=n/2 時取得。
及max(max(m)) = ,所以n階二部圖(n,m), ■
7. 無向圖g有21條邊，12個3度數結點，其餘結點的度數均為2，求g的階數n。
解：根據握手定理有： 21 =( 3χ12 + 2(n-12))/2, 解此方程得n = 15■
8．證明：完全圖的點誘導子圖也是完全圖。
證明：方法1
為證明此結論，我們先證兩個引論：
引論1：設g(v,e)為母圖，,則g的任意子圖g'(v』,e』)是g關於v』的點誘導子圖g''(v』,e』』)的子圖。
引論2：引論1中g』』(v』,e』』)的任意點誘導子圖，也是g圖的點誘導子圖。
證明：略，請讀者證明。
設有完全圖kn( n≥1),現根據其p階點誘導子圖作歸納證明。
kn的1階點誘導子圖，顯然是完全圖，且都是k1圖。當n≥2，kn的2階點誘導子圖，顯然是完全圖，且都是k2圖
假設kn的p(n>p>2)階點誘導子圖，為kp圖，那麼對任意的p+1階點誘導子圖g，根據引理2結論，g的任意p階點誘導子圖g』為kn的p階點誘導子圖，且為kp圖。因此，g必為kp+1圖。
根據以上論證可得原命題成立■
方法2因為完全圖的任意兩個頂點均鄰接，所以點匯出子圖任意兩個頂點也鄰接，為完全圖。■
9．若，稱g是自補圖。確定乙個圖為自補圖的最低條件；畫出乙個自補圖來。
解：設g為(n,m)圖，為(n,m`)圖， 根據補圖的定義有，至少應該滿足
m+m`=n(n-1)/2 (1根據同構的定義有，至少應該滿足
m=m2)
(1),(2)聯立求解得：m=n(n-1)/4, 及乙個圖為自補圖，最低條件為結點數為4的倍數或為4的倍數加1。
圖示略■
10．判斷圖10.29中的兩個圖是否同構，並說明理由。
解：題中兩個圖不同構，因為左邊圖的唯一3度點有2個1度點為其鄰接點，而右圖唯一的3度點只有1個1度點為其鄰接點。因此這兩個圖不可能同構■
11．證明： 圖10.30中的兩個圖是同構的。
解：略■
12. 求具有4個結點完全圖k4的所有非同構的生成子圖。
解：我們可以把生成子圖按總度數不同進行分類，不同總度數的子圖類決不同構。總度數相同的子圖類中，再去找出不同購的子圖。因此求解如下：
σd(v) = 0: (0,0,0,0)
=2: (1,1,0,0)
=4: (2,1,1,0) (1,1,1,1)
=6: (3,1,1,1) (2,2,1,1)(2,2,2,0)
=8: (2,2,2,2) (3,2,2,1)
=10: (3,3,2,2)
=12: (3,3,3,3)
總共10個不同構生成子圖■
13. 設有向圖d=如下圖10.31所示。
(1) 在圖中找出所有長度分別為1，2，3，4的圈 (至少用一種表示法寫出它們，並以子圖形式畫出它們)。
(2) 在圖中找出所有長度分別為3，4，5，6的迴路，並以子圖形式畫出它們。
解：(1)
(2)子圖略
長度為三的迴路：ae1ae1ae1a,ae1ae3de2a,ae4be7ce5a,ae4be8ce5a
長度為四的迴路：aaaaa，aaada，aabe7ca,aabe8ca,abe7cda,abe8cda
長度為五的迴路：aaaaaa,aaaada,aaabe7ca,aaabe8ca,aabe7cda,aabe8cda, aadada,aaae4be7ce5a,aaae4be8ce5a, adae4be7ce5a,adae4be8ce5a■
14. 試證明在任意6個人的組裡，存在3個人相互認識，或者存在3個人相互不認識。
證明：設a為6人中的任一人，那麼a要麼至少與3人認識，要麼至少與3人不認識，二者必居其一。
假設a與b，c，d三人認識，如果b，c，d三人互不認識，結論成立
如果b，c，d三人中，至少有兩人相互認識，則它們和a一起，構成相互認識的3人，結論成立。
同理，a至少與3人不認識，結論也成立。因此，題設結論成立■
15. 若u和v是圖g中僅有的兩個奇數度結點,證明u和v必是連通的。
證明：反證法，假設u和v不連通，那麼他們必然分布於此圖的兩個連通分支中。那麼它們將分別是各連通分支中唯一的奇數度結點。
根據握手定理，乙個圖中奇度點的個數為偶數。而兩個連通分支中，奇度點的個數為奇數。矛盾。
矛盾的產生，是由於假設不連通導致的，因此，題設結論成立■
16. 證明:g是二部圖當且僅當g的迴路都是偶長迴路。
證明：設二部圖g，頂點分為兩個集合v1 ，v2
充分性：
先證明在二部圖中，奇長路的道路的兩個端節點一定分別在兩個頂點集合中，對道路長度使用歸納法，
（1） 當道路長度為1是，根據二部圖的定義，每條邊的兩個頂點分別在兩個點集合中，結論成立
（2） 假設道路長度為2n-1 ( n≥2)時結論成立
（3） 當道路長度為2n+1時，設p=v1v2…v2n-1v2nv2n+1,在此路徑上刪除最後兩個結點，那麼道路p將變為長度為2n-1的奇長道路，根據假設，v1,v2n-1分別在兩個頂點集合中，那麼v2n和v1在同一頂點集合中，而v2n+1和v1在不同頂點集合，結論成立
因為g中的任何迴路，寫成道路的形式，起點和終點時乙個結點，當然在同乙個頂點集合中，因此長度必為偶數；
必要性：（僅對連通分支證明）
在圖中任意取一點著色為白色，將和此點最短距離為奇數的點著色為黑點，為偶數的著色為白點，那麼將結點分為白色和黑色連個點集，任何同色點之間沒有邊相連。否則將形成奇數長度的迴路，例如同色結點v1，v2 相鄰，那麼從初始著色點v開始通過最短路徑可以形成如下迴路v…v1v2…v,因為v…v1,v2…v長度和為偶數，那麼迴路v…v1v2…v長度為奇數，與題設矛盾。所以是二部圖
17.設(n, m)簡單圖g滿足,證明g必是連通圖。構造乙個的非連通簡單圖。
證明：假設g不連通，分支g1，g2．．ｇｋ，那麼他們的邊數的最大值所以，只有當k=1時，才能滿足題設要求，g是連通圖。如果將頂點集合分成兩個點集，|v1|=1，|v2|=n-1,構成如下的有兩個分支的非連通簡單圖，g1=（1，0），g2=kn-1,滿足題設條件■
18. 設g是階數不小於3的連通圖。證明下面四條命題相互等價:
(1）g無割邊；
(2) g中任何兩個結點位於同一迴路中；
(3) g中任何一結點和任何一邊都位於同一迴路中；
(4) g中任何兩邊都在同一迴路中。
證明：（1）=〉（2）
因為g連通，且g無割邊，所以任意兩個結點u,v，都存在簡單道路p=u…wv.又因為g無割邊，所以，刪除邊wv後，子圖依然連通，即w,v存在簡單道路p』,以此類推，可以找到一條核p每條邊都不相同的p』』=v…u,這樣p和p』』就構成了一條迴路。
四川大學試卷B
概率論與數理統計 一 填空 20 2 1 一盒中有16個球，其中10個木質球，6個玻璃球。木質球中有3個紅球，7個白球 玻璃球中有2個紅球，4個白球。今從盒中任取一球，記a 取到白球 b 取到玻璃球 則 2 設隨機變數x在 0，4 上均勻分布，則 3 設x有密度函式則 4 設是來自總體的樣本，設統計...
四川大學畢業實習報告
四川大學 畢業實習報告 學生姓名 學號專業 行政管理 班級 2012年春季 實習單位 礦業公司 實習日期 2013.12.20 2014.01.20 行政管理畢業實習報告 一 實習目的 紙上得來終覺淺，絕知此事要躬行。僅僅憑藉書本知識是不能掌握工作實務上的經驗的，因此，我進行了為期乙個月的實習，鍛鍊...
四川大學班級活動策劃方案
四川大學大一新生滿懷期待的湧入了他們心儀已久的大學，經過磨練人意志的軍訓周，大家終於可以騰出時間來好好搞一次活動了，我們班班長劉茜嬌，考察了很久，最好決定在成都威廉別墅進行我們第一次的班級活動，活動策劃由我也就是我們班的素拓委員王強負責，大家做飯用的食材以及活動中的獎品和零食由副班長劉小毛負責採購，...