木が完全に一致するかどうかをテストする線形時間アルゴリズム を与えます。つまり、ツリーの各頂点に正確に一度接触するエッジの集合です。木が線形時間に完全に一致するかどうかをテストするにはどうすればよいですか？
これはのアルゴリズムからです.Dasguptaがこの問題を解決することはできません。私は貪欲なアプローチを何らかの方法で使う必要があることを知っていますが、これを理解することはできません。助けて？
擬似コードは問題ありません。いったん私がそのアイディアを持ったら、どんな言語でも簡単に実装できます。
アルゴリズムは何かで線形でなければなりません。 O（V + E）は問題ありません。
私は解決策があると思います。グラフはツリーであることがわかっているので、リーフノード、エッジが1つで、子がないノードが存在することがわかります。このノードが完璧なマッチングに含まれるためには、そのエッジが最終的な解決策に存在しなければならない。
私たちは、葉ノードに接続しているすべての辺を見つけ出し、解に追加し、グラフからタッチされた辺を削除することができます。このプロセスの最後に、残っているノードがアントゥルー状態のままになると、完璧なマッチングは存在しません。
リニアin what？エッジの数でリニアは、いくつかの合計順に（V 私、V J）、すなわち、注文した入射リストとして、すべてのエッジをエッジを保ちます。次に、エッジのO（n）の2つのリストを比較できます。
私はそれがグラフでハミルトン経路を見つけるの単純化された問題だと思う： http://en.wikipedia.org/wiki/Hamiltonian_path
http://en.wikipedia.org/wiki/Hamiltonian_path_problem
私はこの問題へのインターネット上の多くのソリューションがあると思いますが、一般的にハミルトン閉路を見つけますNP問題です。
私は、問題の文脈でエッジを接続する必要がある（またはできない）と考えていません。それぞれの辺が各頂点に一度接触すると、その辺は接続された辺を含むことはできません。しかし、私は問題を誤解しているかもしれません。 –
"グラフ"の場合 問題の最初のステップは、接続されたコンポーネントを見つけることです。
最終的な回答の各エッジは2つの頂点を結ぶため、接続されたコンポーネントのうち最大1つに属します。
次に、接続されたコンポーネントごとに完全一致が見つかりました。
もう少し問題を明確にすることはできますか？また、これが宿題の場合は、そのようにタグ付けする必要があります。人々はまだあなたを助けます。 –
これはコースの本ですが、それは自分のポストクラスの問題の探究です。本当に宿題ではありません。 –