Pythonで隣接リストを持つトーナメントでハミルトニアンパスを見つける

Question

トーナメントは完全な有向グラフで、任意の2つの頂点uとvが与えられたときにそれらの間に有向エッジが存在するエッジはuからvまでです）。

ハミルトニアンパスは常にトーナメントに存在します。したがって、{u：[v、w]、v：[w]}形式の隣接関係リストは、uからw、uからv、wからwへの有向エッジがある場合、ハミルトニアンパスVeritcesを順番に印刷していますか？

あなたがpythonなどを知らなくても、アルゴリズムだけが役に立ちます。私はそれについて考えました、そして、私は最高度の頂点から始める必要があると思いますか？次に、2番目に高い等級の頂点を、最も低い次数の頂点まで追加します。しかし、私はこれがフェールセーフな方法であるとは思わないが、最高度の頂点は2番目に高い頂点で殴られた可能性がある。

ありがとうございました！

Answer 1

この問題は再帰的に解決できます。 n+1頂点の名前がv_0からv_nであるとします。 v_1からv_nまでで、サイズnのトーナメントではそれらの間のエッジであるため、v_1〜v_nを含むハミルトニアンパスがあると仮定できます。そのパスに従って、u_1〜u_nという名前に変更します。 （：v_0がu_1かu_n勝ったv_0勝ったここでは、マージナルノードの世話をする必要があります）今u_iがv_0とv_0勝ったことなどがu_i+1勝ったu_iを見つけます。

u_1 , ... , u_i , v_0 , u_i+1 , ... , u_n 

このアルゴリズムは、Oのランタイム（N^2）を有する。このようなiを発見した後、全体的なハミルトン経路を構築することができます。この問題に対するO（nlogn）アルゴリズムが存在します。