圖論基礎

圖 (graph) 由頂點與邊組成,是「關係」的視覺化:社交網路、路網、電路、程式相依性。頂點的度數 (degree) 是連到它的邊數。

握手定理:$\sum\deg(v) = 2|E|$(每條邊貢獻兩個端點),推論是奇數度頂點必有偶數個。完全圖 $K_n$ 有 $\binom{n}{2}$ 條邊。樹 (tree) 是連通無環圖,$|E| = |V| - 1$;$k$ 個分支的森林 $|E| = |V| - k$。

Euler 路徑(每條邊走一次):連通圖有 Euler 迴路 ⟺ 所有頂點度數皆偶;有 Euler 路徑但非迴路 ⟺ 恰有 2 個奇度頂點。Königsberg 七橋問題有 4 個奇度頂點,所以無解——這是圖論的誕生。

算例:度數 $2,2,3,3,4$ 的連通圖有 7 條邊、2 個奇度頂點,有 Euler 路徑。

最短路徑 (Dijkstra)、最小生成樹、網路流、著色問題、PageRank 都建立在這些基本概念上。