グラフ理論
- 握手補題
- Σ deg(v) = 2|E|
- 完全グラフ
- |E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
- 正則グラフ
- |E| = n·k/2
- 木と森
- |E| = n − 1, |E| = n − c
- 木の葉
- L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
- オイラー
- 閉路：すべての次数が偶数； 路：奇数次数がちょうど 2 つ
- Kn のハミルトン閉路
- (n − 1)!/2
- ダイクストラ法の更新
- d(v) = min(d(v), d(u) + w(u, v))
- 長さ L の歩道
- (Mᴸ)ij
解き方
- 各頂点の次数を書き出します。次数の総和は辺の数の 2 倍になります。
- オイラーの問題では、グラフが連結であることを確かめ、奇数次数の頂点を数えます。
- 木では、辺が n − 1 本であることと握手補題を使います。
- ダイクストラ法では、暫定距離の表をつくり、毎回、未確定の頂点のうち最小のものを確定します。
- 最小全域木では、辺を重みの順に並べ、閉路をつくる辺を飛ばす方法（クラスカル法）か、始点から 1 本の木を成長させる方法（プリム法）を使います。