ハミルトン閉路問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > ハミルトン閉路問題の意味・解説 

ハミルトン閉路問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/04/19 10:23 UTC 版)

ナビゲーションに移動 検索に移動

ハミルトン閉路問題(ハミルトンへいろもんだい)とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。

概要

与えられたグラフが有向グラフ(グラフ理論参照)の場合は有向ハミルトン閉路問題、無向グラフ(通常のグラフ)の場合は無向ハミルトン閉路問題と呼ばれる。

この問題はどちらも、NP完全問題であることが知られている。また、無向ハミルトン閉路問題は巡回セールスマン問題の特殊ケースでもある。

始点と終点が一致するという閉路の条件を取り去ると、ハミルトン路問題になる。

NP完全性の証明

ハミルトン閉路問題は NP完全問題の頂点被覆問題が有向ハミルトン閉路問題に多項式時間変換可能であることが証明され、さらに有向ハミルトン閉路問題は無向ハミルトン閉路問題に多項式変換可能であることが証明できることで、NP完全問題であると証明された。




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ハミルトン閉路問題」の関連用語

ハミルトン閉路問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ハミルトン閉路問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのハミルトン閉路問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS