ハミルトン路の存在とその最短性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:20 UTC 版)
「多面体グラフ」の記事における「ハミルトン路の存在とその最短性」の解説
P. G. テイトは「3次の多面体グラフはハミルトン路を持つ」というテイト予想 (グラフ理論)を1884年に提唱したが、この予想1946年にはW. T. Tutteによってタットグラフと呼ばれるハミルトン路を持たない多面体グラフはにより反証された。更に、4次以下の多面体グラフと言う条件ならばより小さな11頂点・18辺からなるハーシェルグラフ、4次以上の頂点を含むが、面が三角形のみである多面体グラフならば11頂点27辺からなるゴールドナー・ハラリーグラフがハミルトン路を持たないグラフとして知られている。 より強い主張として、ある α < 1 （shortness exponent）に対し最長の道が無限個の多面体グラフが存在し、頂点数 n に対してO(nα)個ある。
※この「ハミルトン路の存在とその最短性」の解説は、「多面体グラフ」の解説の一部です。
「ハミルトン路の存在とその最短性」を含む「多面体グラフ」の記事については、「多面体グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「ハミルトン路の存在とその最短性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ハミルトン路の存在とその最短性のページへのリンク
