2

私は有向グラフの発信近傍構造を持っています:

a{f}=[d e];
a{d}=[c];
a{e}=[c h];
a{h}=[b];
a{c}=[a b];

ここで、 ノードおよびは ノード の発信近傍であるa{f}=[d e]ことを意味します。def

fここで、私の目標はa、2 つのパスが存在するかどうかを判断することfですb。

この例では、次の 2 つのパスを見つけることができるため、答えは肯定的です。

p1: f->d->c->a
p2: f->e->h->b

しかしh->b、グラフのエッジを削除すると、答えは NO です。パスが 2 つあるとしても、

p1: f->d->c->a
p3: f->e->c->b

ただし、パスにはパスと交差p3するノードがあります。cp1

  f
 / \
d   e
 \ / \
  c   h
 / \ /
a   b

私の質問は: 2 つのパスの存在を確認するアルゴリズムはありますか?

4

2 に答える 2

1

あなたが探しているのは、開始点を持つフローグラフのとのドミネーターです。からへのすべてのパスがを通過する場合、が支配的です。したがって、特定の問題については、次のことができます。ABFVAFAV

  • のすべてのドミネーターを計算して調べ、Aを除く頂点をマークします。F

  • のすべてのドミネーターを計算して通過し、Bそれらの頂点のいずれかがマークされている場合:

    ->AそしてB、少なくとも 1 つの共通ドミネーターを持っているため、すべてのパスとすべてのパスが を通過するDため、2 つの頂点分離Fパス (両方を含む を除く)F->AとF->Bは存在できません。F->AF->BD

http://en.wikipedia.org/wiki/Dominator_(graph_theory)#Algorithmsを参照してください。

于 2013-05-27T13:20:48.307 に答える