計算機係統中圖與網路分析(ppt 45頁)

計算機係統中圖與網路分析目錄：
1 圖與網路的基本概念
2 樹圖與最小生成樹
3 最短路問題
4 網路的最大流和最小截
5 歐拉回路和中國郵遞員問題
6 哈密爾頓回路及旅行推銷員問題
7 選址問題

計算機係統中圖與網路分析內容摘要：
哥尼斯堡七橋問題 (K?nigsberg Bridge Problem)
Leonhard Euler (1707-1783) 在1736年發表第一篇圖論方麵的論文，奠基了圖論中的一些基本定理
很多問題都可以用點和線來表示，一般點表示實體，線表示實體間的關聯
圖中可以隻有點，而沒有邊；而有邊必有點
若節點vi, vj 之間有一條邊 eij，則稱 vi, vj 是 eij 的端點(end vertex)，而 eij 是節點 vi, vj 的關聯邊(incident edge)
同一條邊的兩個端點稱為相鄰(adjacent)節點，具有共同端點的邊稱為相鄰邊
一條邊的兩個端點相同，稱為自環(self-loop)；具有兩個共同端點的兩條邊稱為平行邊(parallel edges)
既沒有自環也沒有平行邊的圖稱為簡單圖(simple graph)
在無向圖中，與節點相關聯邊的數目，稱為該節點的“次”(degree)，記為 d ；次數為奇數的點稱為奇點(odd),次數為偶數的點稱為偶點(even)；圖中都是偶點的圖稱為偶圖(even graph)

..............................