Graphs and Automata Exercise 5.5

Graphs and Automata Exercise 5.5
April 26
1. 授業で扱った次の定理について, 授業で証明しなかった部分 (4→ 5, 5→6, 6→1) を証明しなさい (『グラ
フ理論入門』の定理 9.1 で扱っています).
定理 グラフ T が頂点を n 個もつとする. 次の命題は同値である.
(a)
(b)
(c)
(d)
(e)
(f)
T
T
T
T
T
T
は木である.
に閉路はなく, 辺が n − 1 本ある.
は連結で, 辺が n − 1 本ある.
は連結であり, すべての辺は橋である.
の任意の 2 点を結ぶ道はちょうど 1 本である.
に閉路はないが, 新しい辺をどう付け加えても 1 つだけ閉路ができる.
2. 林 G が n 個の頂点と k 個の成分をもつとする. このとき G には辺が n − k 本あることを示せ.
3. 完全二部グラフが木であるための必要十分条件を求めよ.
4. 次のグラフがハミルトングラフであることを示せ.
2
3
1
6
4
5
5. 上のグラフについて, どの隣接していない 2 点 v, w でも deg(v) + deg(w) < (頂点の数) となることを
確認せよ.
6. 3 以上の頂点をもつグラフ G について “隣接していない 2 点 v, w で deg(v) + deg(w) < (頂点の数) と
なるなるものがあるなら G はハミルトン・グラフでない” は成り立たないことを示せ.
(講義では “隣接していない任意の 2 点 v と w で deg(v) + deg(w) ≥ (頂点の数) が成立するとき, G は
ハミルトン・グラフである” が成り立つことを証明したことに注意)
7. 次のグラフがハミルトン・グラフでない理由を書け.
(講義の最後の演習では “deg(1) + deg(3) < (頂点の数) だから” “すべての隣接していない点 v, w で
deg(v) + deg(w) < (頂点の数) だから” などという回答が目立ったが, 上の問題からそれは正しい理由で
はないことに注意せよ)
1
3
2
5
4