グラフの基礎 グラフの連結性 ハミルトン閉路 十分条件、オイラー小道、オイラー回路、必要十分条件、頂点、偶奇、隣接、次数
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第7章(グラフの基礎)、7.2(グラフの連結性)、7.2.5(ハミルトン閉路)、問7.11の解答を求めてみる。
a
グラフは連結で、次数が奇数である頂点は、c、 fの2個なので、オイラー小道が存在する。
その1つ。
b
次数が奇数の頂点が存在するので、オイラー回路は存在しない。
c
頂点の総数は6。
隣接していない頂点の和の最小値は5。
よって、 隣接していない任意の2頂点の次数は
以上なので、ハミルトン路は存在する。
その1つ。
d
ハミルトン閉路。