ハミルトン路とハミルトニアン閉路
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:56 UTC 版)
「ピーターセングラフ」の記事における「ハミルトン路とハミルトニアン閉路」の解説
ピーターセングラフにはハミルトン路はあるがハミルトン閉路はない。ハミルトン閉路がなく、ブリッジ（それを削除するとグラフが2つの連結グラフに分かれてしまうという辺）のない3-正則グラフとしては最小である。 また、頂点を1つ削除するとハミルトングラフになるので、準ハミルトングラフであり、準ハミルトングラフとしても最小である。 ピーターセングラフは、5種類しか知られていないハミルトン閉路を持たない連結頂点推移グラフである。その5種類以外にそのようなグラフは存在しないという予想がなされている。2-連結で r-正則のグラフで、最大 3r + 1 の頂点を持つグラフは、ハミルトングラフかピーターセングラフのどちらかである。
※この「ハミルトン路とハミルトニアン閉路」の解説は、「ピーターセングラフ」の解説の一部です。
「ハミルトン路とハミルトニアン閉路」を含む「ピーターセングラフ」の記事については、「ピーターセングラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「ハミルトン路とハミルトニアン閉路」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ハミルトン路とハミルトニアン閉路のページへのリンク
