組合せとグラフの理論(塩田)第5回 (3) ハミルトン性

定義

 今度は、全ての頂点を含む道、あるいは閉路を持つかどうかを考えます。
Def.12 オーダー $n$ のグラフ $G=(V,E)$ について、
  1. $P_n$ と同型な部分グラフを持つとき(すなわち全ての頂点を通る道を含むとき)、 $G$ を半ハミルトングラフと言う。
  2. $C_n$ と同型な部分グラフを持つとき(すなわち全ての頂点を通る閉路を含むとき)、 $G$ をハミルトングラフと言う。
それぞれ、その部分グラフを半ハミルトン道、ハミルトンサイクルと呼ぶ。

例と注意

Ex.13 次のグラフはハミルトングラフでしょうか?

Ex.14 次のグラフも全てハミルトングラフです。
  • $C_n$ ( $n \geqq 3$ )
  • $K_n$ ( $n \geqq 3$ )
  • プラトングラフたち
  • $Q_k$ ( $k \geqq 2$ )
Rem.15 
  1. ハミルトン性の判定は NP 完全問題ですので、高速なアルゴリズムはありません。 (オイラー性の判定が、次数を数えるだけなので瞬時にできることと対照的です。)
  2. テキスト Th.7.1 は
    「やたらたくさん辺があればハミルトングラフである」
    という内容ですが、仮定が強すぎるので実社会ではほとんど使えません。
  3. オイラー性は郵便配達員問題に、ハミルトン性は巡回セールスマン問題に関わっています。詳しくは後日。