📐ハミルトングラフとNP完全

2023年8月30日 18:52

オイラーグラフ:
- オイラーグラフは、グラフの全ての辺を一度だけ通る閉路、すなわちオイラー閉路を持つグラフを指します。オイラー閉路とは、グラフのある頂点からスタートし、全ての辺を一度だけ通って最初の頂点に戻る経路のことです。
- あるグラフがオイラーグラフであるための必要十分条件は、そのグラフが連結であり、全ての頂点の次数（接続されている辺の数）が偶数であることです。
ハミルトングラフ:
- ハミルトングラフは、グラフの全ての頂点を一度だけ通る閉路、すなわちハミルトン閉路を持つグラフを指します。ハミルトン閉路とは、グラフのある頂点からスタートし、全ての頂点を一度だけ通って最初の頂点に戻る経路のことです。
- ハミルトングラフであるかどうかを判定する一般的な条件は存在しないため、与えられたグラフがハミルトングラフであるかどうかを判定するのはNP完全問題です。

グラフ理論では、オイラー軌跡（またはオイラー・パス）とは、有限グラフの軌跡のうち、すべての辺を正確に一度だけ訪れる軌跡のことである（頂点を再訪することは可能）。同様に、オイラー・サーキットまたはオイラー・サイクルとは、同じ頂点を始点とし、同じ頂点を終点とするオイラー軌跡のことである。これらは、1736年に有名なケーニヒスベルクの7つの橋の問題を解いていたレオンハルト・オイラーによって初めて議論された。この問題を数学的に説明すると次のようになる：

画像のグラフが与えられたとき，各辺をちょうど1回ずつ訪れるような経路（あるいはサイクル；同じ頂点を始点とし，同じ頂点を終点とする経路）を構成することは可能か？
オイラーは，オイラー回路が存在するための必要条件は，グラフのすべての頂点が偶数次であることであることを証明し，すべての頂点が偶数次である連結グラフはオイラー回路を持つことを証明なしに述べた．この後者の主張の最初の完全な証明は、1873年にCarl Hierholzerによって死後に発表された：

連結グラフがオイラー・サイクルを持つのは、すべての頂点の次数が偶数である場合に限られる。
オイラー・グラフという用語は、グラフ理論において2つの一般的な意味を持つ。1つはオイラー・サイクルを持つグラフであり、もう1つはすべての頂点が偶数の次数を持つグラフである。これらの定義は連結グラフでは一致する[2]。

オイラー回路が存在するためには、0個か2個の頂点が奇数次であることが必要であり、これはケーニヒスベルク・グラフがオイラー回路でないことを意味する。奇数の次数を持つ頂点が1つもない場合、オイラー・トレイルはすべて回路である。奇数次の頂点がちょうど2つあれば、すべてのオイラー・トレイルはそのうちの1つから始まり、もう1つで終わる。オイラー的軌跡を持つが、オイラー的回路を持たないグラフを半オイラー的と呼ぶ。

グラフ理論の数学分野では、ハミルトン・パス（または追跡可能パス）とは、無向グラフまたは有向グラフにおいて、各頂点をちょうど1回訪れるパスのことである。ハミルトン・サイクル（またはハミルトン回路）とは、各頂点をちょうど1回訪れるサイクルのことである。隣接する頂点で始まり、隣接する頂点で終わるハミルトン・パスは、さらに1つの辺を追加してハミルトン・サイクルを形成することで完成させることができ、ハミルトン・サイクルから任意の辺を取り除くとハミルトン・パスができる。このような経路とサイクルがグラフに存在するかどうかを決定すること（ハミルトン経路問題とハミルトンサイクル問題）は、NP完全である。

ハミルトン・パスとハミルトン・サイクルは、正十二面体の辺グラフからハミルトン・サイクルを見つけるというイコシアン・ゲーム（現在はハミルトンのパズルとも呼ばれる）を考案したウィリアム・ローワン・ハミルトンにちなんで名付けられた。ハミルトンはこの問題を、同じくハミルトンが発明した四元数（クォータニオン）と多くの類似点を持つ、単根に基づく代数構造であるイコシアン微積分を用いて解いた。この解法は任意のグラフには一般化しない。

ハミルトンにちなんで命名されたにもかかわらず、多面体におけるハミルトンサイクルは、その1年前にトーマス・カークマンによっても研究されており、特にハミルトンサイクルのない多面体の例を示している[1]。さらに以前には、チェス盤の騎士のグラフ（ナイトツアー）におけるハミルトンサイクルとパスは、9世紀にインドの数学でルドラタによって、また同じ頃にイスラム数学でアル・アドリ・アル・ルーミによって研究されていた。18世紀のヨーロッパでは、アブラハム・ド・モワブルとレオンハルト・オイラーによって騎士のツアーが発表された。

NP完全の求め方を教えてください

NP完全 (NP-Complete) 問題を識別する方法は、主に以下のステップに従います。NP完全問題とは、NP（Non-deterministic Polynomial time）に属し、かつNPの中で最も「難しい」問題群を指します。つまり、すべてのNP問題がその問題に多項式時間で帰着可能である場合、その問題はNP完全であるとされます。

問題がNPに属することを示す:
- まず、与えられた問題がNPに属することを示す必要があります。NP問題とは、ある「証拠」（または解）が与えられた場合、その解が正しいかどうかを多項式時間で検証できる問題のことです。
NP困難（NP-Hard）であることを示す:
- NP困難であるとは、すべてのNP問題がその問題に多項式時間で帰着できることを意味します。これを示すためには、既にNP困難であると証明された問題から始め、その問題を多項式時間で与えられた問題に変換する方法を見つける必要があります。
多項式時間帰着:
- このステップでは、既知のNP完全問題から新しい問題へと「帰着」を行います。帰着とは、ある問題のインスタンスを別の問題のインスタンスに多項式時間内で変換することです。つまり、もし既知のNP完全問題を新しい問題に多項式時間で変換できれば、その新しい問題もNP完全であると証明できます。
具体的な帰着の例:
- 具体的には、最もよく知られているNP完全問題の一つである「サティスファイアビリティ問題（SAT）」から始め、それを新しい問題に多項式時間で変換する方法を見つけることが一般的です。SAT問題は、論理式が与えられたとき、その論理式を真にする変数の割り当てが存在するかどうかを判定する問題です。

NP完全問題を証明することは、コンピュータ科学における重要な研究分野の一つであり、新しい問題がNP完全であることを示すことは、その問題の計算複雑性を理解する上で重要な意味を持ちます。このプロセスを通じて、特定の問題に対する効率的なアルゴリズムの存在の可能性を探求することができます。

NP完全かを判別するpyuthonライブラリはありますか？

NP完全問題を識別するための直接的なPythonライブラリは存在しません。NP完全性を判断する過程は、一般的には数学的な証明に基づいており、特定の問題がNP完全であるかどうかを自動的に評価するアルゴリズムやツールはありません。

お願い致します