離散數學導論（簡體書）

《高等學校教材?離散數學導論:學習指導與習題解析(第4版)》由高等教育出版社出版。《高等學校教材?離散數學導論:學習指導與習題解析(第4版)》除可與《離散數學導論（第4版）》配套使用之外，還可獨立作為離散數學課程的教學參考書，供高等學校計算機及相關專業的學生使用。

第一章 集合論初步
1.1 主要內容
1.2 復習重點
1.3 基本概念及注意事項
1.4 典型例題詳細分析
1.5 相關教材中的習題及解答
1.6 另增配套習題及解答
第二章 關系
2.1 主要內容
2.2 復習重點
2.3 基本概念及注意事項
2.4 典型例題詳細分析
2.5 相關教材中的習題及解答
2.6 另增配套習題及解答
第三章 函數
3.1 主要內容
3.2 復習重點
3.3 基本概念及注意事項
3.4 典型例題詳細分析
3.5 相關教材中的習題及解答
3.6 另增配套習題及解答
第四章 有限集與無限集
4.1 主要內容
4.2 復習重點
4.3 基本概念及注意事項
4.4 典型例題詳細分析
4.5 相關教材中的習題及解答
4.6 另增配套習題及解答
第五章 代數系統
5.1 主要內容
5.2 復習重點
5.3 基本概念及注意事項
5.4 典型例題詳細分析
5.5 相關教材中的習題及解答
5.6 另增配套習題及解答
第六章 圖論
6.1 主要內容
6.2 復習重點
6.3 基本概念及注意事項
6.4 典型例題詳細分析
6.5 相關教材中的習題及解答
6.6 另增配套習題及解答
第七章 數理邏輯
7.1 主要內容
7.2 復習重點
7.3 基本概念及注意事項
7.4 典型例題詳細分析
7.5 相關教材中的習題及解答
7.6 另增配套習題及解答
第八章 離散建模
8.1 主要內容
8.2 復習重點
8.3 基本概念及注意事項
8.4 相關教材中的習題及解答
參考文獻

4設圖G有9個結點，每個結點的次數（度數）不是5就是6，試證G中至少有5個6次結點或至少有6個5次結點。
分析：本題條件是圖G共有9個結點，每個結點的次數是5或6，而只要證明滿足下面兩種情況之一即可。①對于5次結點至少為6個，即可以是6個或8個，而如果只有4個5次結點，那么剩下94=5個結點，而這5個結點的次數為6（即至少有5個6次結點），而如果只有0個、2個5次結點，則對應有9個、7個6次結點，也滿足至少5個的情況；②同理，從至少5個6次結點出發，分析少于5個或多于5個時的情況也能得出相應結論。
證明：根據圖論中的定理，任何圖中奇次結點數為偶數，因此5次結點的個數只能為0，2，4，6，8，此時對應6次結點的個數則為9，7，5，3，1。對這五種情況都滿足至少有5個6次或6個5次結點，故結論成立。
5設G為無向連通圖，有n個結點，那么G中至少有幾條邊？為什么？若是有向圖又如何？
解：至少有n,1條邊，因為G為無向連通圖，設有n個結點v1，v2，，vn，由連通性知，G中每對結點之間都有通路，每個結點都有與其相鄰的結點，因此，每個結點至少關聯一條邊，不妨設按給定結點的順序相鄰（或重新按序編號），則v2與v1相鄰有邊e1，v3與V2或v1相鄰有邊e2vn必與v1，v2，，vn1，中某結點相鄰有邊en1。故G中至少有n1條邊。
若G為有向圖，則將方向略去，對相應的無向圖討論，結果相同。（因為只是討論有多少條邊，并未要求邊的方向。）
7證明每個結點的次數至少為2的圖必包含一個回路。
分析：本題證明時所設L是考慮了能否構成環的最壞情況，除兩頭外，其他結點的次數為2（滿足至少為2的最少次數情況），如果不按L來安排結點在圖中位置的話，則可出現回路。
由于條件給出每個結點的次數至少為2，那么結點a及L中的另一端點的次數就不會是1，故會有情況，由a引出的另一條邊e的另一頭必會去與另一結點相連（如結點b，因為按最差情形所有點均放到了L上），此時已出現了回路。
證明：設L是圖G最長路中的一條，設其長度為m，這條路的一個端點設為a，考察圖G中與a關聯的那些邊，這些邊中任何一條邊的另一個端點必在L上，否則，將這個結點加進L中就可得到一條更長的路。
如果G中每個結點的次數至少為2，那么a也要關聯一條不在L上的邊e。若e是環，則e本身就是回路；否則，邊e的另一個端點b（與a不同的點）在L上，而連通L中a到b的子通路與邊e就組成一個回路。
8證明：如果n個電話局中的任何兩個電話局總是可以通話的，那么至少存在n,1條直通線路。
證明：設n個電話局為n個結點，兩個結點之間有連線，當且僅當對應的這兩個電話局可直通電話因為任何兩個電話局總可以通話（可能中途要通過其他電話局），因此就可構成一個簡單的連通圖。
現證明，對于具有n個結點的簡單連通圖G至少存在n1條邊。用數學歸納法，有：
當n=2時，有一條邊；
當n=3時，至少有兩條邊；
設當n=k時，G至少有k1條邊當再增加一個結點r時，r必與G中的某個結點鄰接，因此，具有k+1個結點的簡單連通圖至少有k條邊。
說明：本題是一道應用題，要善于設法將其轉換為圖論中的問題來進行研究本題中的所有結點均可有通路達到，用數學歸納法證出的是n個結點至少有n1條邊將其連通，但一般情況下可以超過n1條邊。