一、圖
1、圖的基本概念
握手定理：無向圖中，所有節點度數之和為邊數的二倍
有向圖中，所有節點入度之和等于出度之和等于邊數
推論：任何圖都有偶數個奇結點
各種圖(V,E) = (n,m)
| 零圖 | 隻有孤立結點的圖 |
| 平凡圖 | 階零圖 |
| k度正則圖 | 所有節點度數均為k的無向圖 |
| 完全無向圖 | k = n - 1的正則圖;邊數=C(n,2) |
| 完全有向圖 | 所有節點入度 == 出度 == n - 1,邊數 = A(n,2) |
路徑：起點和終點不相同
回路：起點和終點相同
基本路徑——沒有重複的點——n階圖中基本路徑長度<= n - 1
簡單路徑——沒有重複的邊
2、圖的矩陣表示&&矩陣攜帶的資訊
e.g.鄰接矩陣の圖特性
連通/強連通圖——可達性矩陣（矩陣的可傳遞閉包）全1
3、圖的連通性
無向圖——連通/不連通
有向圖——強連通/單向連通/弱連通
4、圖的相關應用&特殊的圖
1)哈密爾頓圖
充分條件：任意u,v屬于V，d(u)+ d(v) >= n,n為頂點數目且n >=3
必要條件：...
應用：
1 判斷哈密爾頓圖的存在性
2 求出哈密爾通路/回路
e.g.1 給定一個立方體圖，求出哈密爾頓回路
e.g.2安排考試日程
6天安排6門課，ABCDEF，的考試，每天考一門，假設選課情況有：
DCA BCF EB AB 如何安排日程使得沒有兩個人是同一天考試？
2)二部圖
充分條件：
- 集合分為兩部分，每部分的點之間沒有直接連線，隻有跨部分的連線
必要條件
- 所有回路長度均為偶數
性質：
完全二部圖 邊數e = |V1| * |V2|
3)歐拉圖
含有歐拉回路的有向圖或者無向圖叫歐拉圖
n為奇數時，非平凡完全無向圖為歐拉圖
二、樹
二叉樹の定義：有根樹，結點出度不是0就是2
字首碼：各個符号串互不為字首
無向樹：沒有回路的連通的無向圖