2

我有一个有向图的传出邻域结构：

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

其中a{f}=[d e]表示节点d和e是节点的传出邻域f。

现在，我的目标是确定是否存在两条路径，一条是 from fto a，一条是 from fto b，谁的节点不允许相互交叉？

对于这个例子，答案是肯定的，因为我们可以找到两条路径：

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

但是当我们删除h->b图中的边时，答案是否定的，因为即使有两条路径：

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

但是，路径p3有一个c与路径相交的节点p1。

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

我的问题是：是否有任何算法来检查这两条路径的存在？

4

2 回答 2

1

您正在寻找的是带有起点的流程图中的支配者。如果从到 的每条路径都经过，则占主导地位。因此，对于您的特定问题，您可以：ABFVAFAV

  • 计算并遍历 的所有支配者A，标记除了F

  • 计算并遍历 的所有支配者B，以及是否标记了这些顶点：

    ->A并且B至少有一个共同的支配者D，所以没有两条不相交的（除了包含的F）路径F->A并且F->B可以存在，因为每条路径F->A和每条路径都F->B通过D.

请参阅http://en.wikipedia.org/wiki/Dominator_(graph_theory)#Algorithms

于 2013-05-27T13:20:48.307 回答
1

您可以通过以下方式使用最大流量算法解决此问题：

  1. 通过将每个顶点拆分为入口顶点和出口顶点来构造有向图
  2. 根据顶点 i 为每对添加一条从 entry(i) 到 exit(i) 的边，容量为 1
  3. 为原始图中的每条边 i->j 添加一条从出口（i）到入口（j）的边，容量为 1
  4. 添加一个额外的终端顶点 e
  5. 从每个目的地的出口顶点（在您的情况下为出口（a）和出口（b））添加一条边到容量为1的顶点e
  6. 计算从 exit(f) 到 e的最大流量

当且仅当最大流量为 2 时，从 f 到 a/b 有两条顶点不相交的路径。

示例 Python 代码

import networkx as nx
G=nx.DiGraph()
a={'f':'de','d':'c','e':'ch','h':'b','c':'ab','a':'','b':''}
for v in a:
    i='entry_'+v
    j='exit_'+v
    G.add_edge(i,j,capacity=1)
    for dest in a[v]:
        G.add_edge(j,'entry_'+dest,capacity=1)
for dest in 'ab':
    G.add_edge('exit_'+dest,'e',capacity=1)
print nx.max_flow(G,'exit_f','e')

G.remove_edge('exit_h','entry_b')
print nx.max_flow(G,'exit_f','e')

这打印

2 (meaning that in the original graph there are 2 vertex disjoint paths)
1 (meaning that once we remove h->b, there is only 1 vertex disjoint path)
于 2013-05-27T17:43:46.510 回答