algorithm - グラフ内の 1 対 1 のノードのすべてのチェーンを見つける

Question

私は無向グラフに行きます。私の目標は 、1 対 1 の関係にあるノードGよりも長い可能性のあるすべてのチェーンを見つけることです。N

例えば：

次のグラフでは、1 対 1 の関係にある 2 つを超えるノードの長さの「チェーン」は次のとおりです。

- d -> e -> f -> g
- c -> k -> l -> m

では、この問題を解決するための最良のアプローチまたはアルゴリズムは何ですか?

Answer 1

各頂点の次数が 2 以下になるようにすべてのパスを見つけたい場合、単純な方法は次のようになります。

次数が 2 を超えるすべての頂点をグラフから削除します。各頂点の次数が 2 以下のグラフが残ります。このようなグラフのすべての接続されたコンポーネントが単純な方法または単純なループであることを証明するのは簡単で、それらを簡単に区別できます (たとえば、あるノードから DFS を実行し、それに戻るかどうかを確認します)。 .

したがって、パスであるすべてのコンポーネントは、探しているパスです。ループであるすべてのコンポーネントは、検索するパスでもあります。必要なパスとしてループを許可するかどうかに応じて、エッジまたは頂点を削除することで、そのようなパスに簡単に変換できます。