第10章演習解答

演習問題１解答
10-1
ハミルトングラフには，すべての頂点をちょうど１度だけ通る閉路が
ある．この閉路を辿る向きに各辺に向きをつけるならば，任意の２
頂点の間に有向道が存在する．したがって，ハミルトングラフは向
きづけ可能である．
例
演習問題２解答
10-2
Kn を構成する各頂点を v1, v2, …, vn とする．完全グラフであるから，
辺 vi vi+1 （i = 1, 2, …, n – 1），vn v1 が存在．たとえば，vi → vi+1 の向
きに向きづけしたとすると，閉じた有向道 v1 → v2 → v3 → … → vn
→ v1 が存在し，任意の２頂点の間に有向道が存在する．したがっ
て，その他の辺には任意に向きを付けることにより強連結グラフが
得られ，Kn は向きづけ可能である．
演習問題３(1) 解答
10-3
頂点数（n）が 1の場合は自明．
頂点数が 2 以上の場合について．
頂点数が 2 以上の推移的トーナメント T を任意に選び，T には入
次数が 0 の頂点がないと仮定する．T の頂点を１つ任意に選び，
これを v とする．仮定（入次数が0の頂点がない）より，uv が T の
弧であるような頂点 u が存在する．さらに，仮定より同様にして，tu
が T の弧であるような頂点 t が存在する．頂点は有限個であるか
ら，このようにして頂点を辿っていくと，いずれ，v に戻る．つまり，v
から弧を順方向に辿って u に至る有向道が存在する．推移的であ
るから弧 vu が存在することになる．しかし，弧 uv が存在しており，
トーナメントの定義に矛盾する．
t
u
v
演習問題３(2) 解答
10-4
頂点数 n に関する数学的帰納法で証明する．
Basic step : n ≤ 2 の場合，推移的トーナメントは以下の有向グラフ
と同形である．それぞれ，入次数は 0 と 0, 1 であるから命題成立．
n = 1 の場合
n = 2 の場合
10-5
Inductive step:
頂点数が n – 1（ただし，n ≥ 3）の任意の推移的トーナメントで命
題が成立すると仮定．
T
頂点数が n の推移的トーナメント
T を任意に選ぶ．T には，入次数
が 0 の頂点が存在し（∵ (1)），こ
v0
れを v0 と命名する．
T’
T から v0 を除去したグラフを T’
とする．T’ は頂点数 n – 1 の推
移的トーナメントであるから，帰
0
1
2
n–3 n–2
入次数
納法の仮定より，全頂点の入次
数を小さい方から列挙すると，0,
1, …, n – 2 である．
T
T において，v0 は残りのすべて
の頂点と弧で結ばれている（v0
1
2
3
n–2 n–1
が弧の元）ので T の全頂点の入 0
入次数
次数は 0, 1, …, n – 1 である．
?
?
?
演習問題３(3) 解答
10-6
(1)の結果より，入次数 0 の頂点（v0）が存在する．頂点数が2以上
であるから， v0 以外の頂点が存在する．
vi （ i > 0）から v0 への有向道は存在しないので，強連結とは成りえ
ない．

Download Report