有向グラフで少なくとも5つの辺を持つ単純なパスを見つける

Question

質問があります。 有向グラフ（G = V、E）とVのグループからのソース頂点sを与えます。 sから少なくとも5つの辺を持つGの任意の頂点までの単純なパス（円なし）があるかどうかを確認したい。 できるだけ効率的なアルゴリズムを提供し、円を含むことができるグラフGの問題を解決します。

私は我々が頂点sから始まるパスを向けられた5-エッジを簡単に見つける必要がある

Answer 1

:-)

おかげであなたの助けを必要としてください。今度は、（s以外の任意の頂点）cのすべての可能な値を通過させ、その後、すべてのc値のために、我々はsとc頂点を含まないすべてのエッジを通過することができ、

s -> a -> b -> c -> d -> e (all distinct) 

：このパスは次のようになります

if edge (s, x) exists and edge (y, c) exists 
    put (x, y) in AB edges list 
if edge (c, x) exists 
    put (x, y) in DE edges list 

これはO(|E|)で行うことができますエッジ(x, y)ために次の手順を実行します。次に、E1がABであり、E2がDEであり、共通の頂点を共有しないようなエッジのペア(E1, E2)を見つける必要があります。後者はO(|E|)で行うことができます。

グラフG' = (V, DE)を取り、頂点の次数を見つけることができます。その後ABからのすべてのエッジ(a, b)のために、私たちは

degree(a) + degree(b) = |DE| + x  

x = 1(a, b)場合は、DEで特にx = 0ある場合ことを確認する必要があります。この等式が成り立たない場合、には、aもbも含まれていない辺があり、答えを見つけるにはDE全体を反復することができます。

全体的な複雑さはO(|V||E|)となり、メモリはO(|E|)になります。