[Algorithm] ハミルトン経路とオイラー経路の違い



Answers

ハミルトニアンパスは各頂点を正確に一度訪れなければならないが、オイラーパスは各エッジを正確に一度訪れなければならない。

Question

ハミルトニアンパスとオイラーパスの違いを教えてくれる人もいます。 彼らは似ているようです!




私は生物学における共通の例を使用します。 DNAサンプルを作ることによってゲノムを再構成する。

デノボアセンブリ

短い読み込みからゲノムを構築するには、それらの読み込みのグラフを構築する必要があります。 読み込みをk-mersに分解し、それらをグラフに組み立てることでそれを行います。

我々は、図のように各ノードを一度訪れてゲノムを再構成することができる。 これはハミルトニアン経路と呼ばれます。

残念ながら、そのようなパスを構築することはNP困難です。 それを解決するための効率的なアルゴリズムを導き出すことは不可能です。 代わりに、バイオインフォマティクスでは、エッジがオーバーラップを表すオイラー周期を構築します。




オイラーパスは、グラフのすべての辺(注釈)を正確に1回使用するグラフです 。 オイラー回路は、 すべてのエッジをカバーした後に始点に戻るオイラーパスです。

ハミルトンパスはすべての頂点(注釈)を一度正確にカバーするグラフです。 この経路がハミルトン回路と呼ばれる経路よりも出発点に戻ると、




ハミルトニアンのパスは、すべてのノード(または頂点)を1回だけ訪れ、オイラーパスはすべてのエッジを正確に1回通過します。




Links