📂グラフ理論

ハミルトニアングラフ

定義 ¹

$G$ を連結グラフとする。

$G$の全てのヴァーテックスを含む閉じたパスが存在する場合、$G$をハミルトングラフと呼び、そのサイクルをハミルトニアンサイクルという。全てのヴァーテックスを含むが閉じていないパスが存在する場合、$G$をセミハミルトングラフという。

説明

オイラーグラフが全てのエッジを通るトレイルに関心があるように、ハミルトングラフは全ての頂点を通るパスに関心がある。オイラーグラフとハミルトングラフは、論理的に関係はない。例えば、次のグラフは順番に、ハミルトンだがオイラーではないグラフ、ハミルトンでオイラーも兼ねるグラフ、ハミルトンではないがオイラーのグラフを示している：

一見すれば、全てのエッジを通らなくても良いという点で、簡単に見えるかもしれないが、逆に一つのヴァーテックスをただ一度だけ通ることができるため、より複雑になる。そのため、オイラーグラフはその度数できちんと同値条件が与えられているが、ハミルトングラフはそうではない。

ただし、十分に多くのエッジがあれば、そのグラフがハミルトンであることを保証する定理が知られている。これは一般的にディラックの定理Dirac’s Theoremとして知られている。ディラックの定理は1952年に証明された後、1960年にオーレ^oreによって簡単な証明で一般化され、オーレの定理の帰結となったが、今でもディラックの定理と呼ばれることが多い。

併せて見る

• 全てのエッジを含む閉じたトレイルが存在するグラフ：オイラーグラフ