データ構造とアルゴリズム：直前対策パック

グラフ理論

握手補題

Σ deg(v) = 2|E|

完全グラフ

|E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n

正則グラフ

|E| = n·k/2

木と森

|E| = n − 1, |E| = n − c

木の葉

L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3

オイラー

閉路：すべての次数が偶数； 路：奇数次数がちょうど 2 つ

K_n のハミルトン閉路

(n − 1)!/2

ダイクストラ法の更新

d(v) = min(d(v), d(u) + w(u, v))

長さ L の歩道

(Mᴸ)_ij

解き方

1. 各頂点の次数を書き出します。次数の総和は辺の数の 2 倍になります。
2. オイラーの問題では、グラフが連結であることを確かめ、奇数次数の頂点を数えます。
3. 木では、辺が n − 1 本であることと握手補題を使います。
4. ダイクストラ法では、暫定距離の表をつくり、毎回、未確定の頂点のうち最小のものを確定します。
5. 最小全域木では、辺を重みの順に並べ、閉路をつくる辺を飛ばす方法（クラスカル法）か、始点から 1 本の木を成長させる方法（プリム法）を使います。