从DAG创建强连通分量 [英] Creating Strongly Connected Components from a DAG

问题描述

我想从一个向无环图创建强连接组件。

输入是边缘中形成一个列表

  1 2
3 5
等等
 

我需要创建的一组被添加到给定的图中边的最小的外点，使强连通分量的曲线图....

任何想法？

下面是一个例子就是我要找：

由于输入：

  1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9
 

的输出将是必要的边缘，除了创建强连接部件的最少数量。

输出：

  3 1
4 5
7 6
8 1
9 2
 

解决方案

假设不存在孤立的顶点，你只需要添加最多的图（|来源|，|水槽|）边缘，使其强连接

让T =【T <子> 1 ，...，T <子> N }是水池和{S <子> 1 ，...，S <子>米}是DAG的来源。假设N'LT; = M。 （另一种情况是非常相似）。考虑如下定义的两个集合之间的二分图G（T，S）。 G（T，S）具备优势（T <子>我，S <子>Ĵ），当且仅如果T <子>我可以从s <子达>Ĵ。

设M是G（T，S）的最大匹配。不失一般性假设是m由k条边：{（T <子> 1 ，S <子> 1 ），（T ₂ ，S <子> 2 ），...，（T <子> K ，S <子> K ）}。在原来的DAG图G，加上定向边缘{(t₁->s₂),(t₂->s₃),…,(t_k−1->s_k),(t_k->s₁)}.很容易看出，通过将这些边缘，诱发M中的顶点是密切联系的G中。

现在考虑G（T，S）剩余的顶点。因为中号最大，在S〜M（相应T-M）每个顶点应连接到一个顶点T中（相应地，S〜M）。因此，我们配对剩余的顶点随意，说{（T <子> K + 1 ，S <子> K + 1 ），...，（T <子> N ，小号<子> N ）}，并添加相应的向边在G中其余的每个源点源S <子>我（i属于{N + 1，...，M}我们添加边缘（T <子> 1 - >取值<子>我）在G这样的边缘添加的总数为max（|来源|，|水槽|）

。

编辑：添加了几个例子的

有关在您输入的例子。我们拳头计算最大匹配，说：

  3--1
4--2
7--5
8--6
 

所以我们增加了边缘：

  3→2
4-大于5
7→6
8-大于1
 

剩余的（汇）顶点不是present的匹配是9，所以我们从9添加弧线任意源顶点的匹配，比如 9＆GT; 1 。

下面是另一个例子，说明了算法的所有步骤：

输入图：

  12 3 5 9 10（来源）
\ | / / | \ \ /
 4 6 7 8 11（片）
 

极大匹配：

  4--1
6--5
11--9
 

所以我们增加了边缘：

  4-→5
6＆GT; 9
11-→1
 

现在剩下的接收器是 {7,8} ，其余源 {2，3，10} 。我们随心所欲对7说2和8说，3，添加：

  7＆GT; 2
8-→3
 

最后，剩余的（源）的顶点为10，我们增加：

  4-→10
 

I am trying to create strongly connected components from a directed acyclic graph.

The input is a list of edges in form

1 2
3 5
etc

I need to create an outpoint of a minimal set of edges to be added to the given graph to make a graph of strongly connected components....

Any ideas?

Here's an example of what I'm looking for:

Given the input:

1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9

The output would be the minimum number of edges necessary for addition to create strongly connected components.

Output:

3 1
4 5
7 6
8 1
9 2

解决方案

Assuming there are no isolated vertices in the graph you only need to add max(|sources|,|sinks|) edges to make it strongly connected.

Let T={t₁,…,t_n} be the sinks and {s₁,…,s_m} be the sources of the DAG. Assume that n <= m. (The other case is very similar). Consider a bipartite graph G(T,S) between the two sets defined as follows. G(T,S) has an edge (t_i,s_j) if and only if t_i can be reached from s_j.

Let M be a maximal matching in G(T,S). Without loss of generality assume that M consists of k edges: {(t₁,s₁),(t₂,s₂),…,(t_k,s_k)}. In the original graph DAG G, add directed-edges {(t₁->s₂),(t₂->s₃),…,(t_k−1->s_k),(t_k->s₁)}. It's easy to see that by adding these edges, the vertices induced by M are strongly connected in G.

Now consider the remaining vertices in G(T,S). Because M maximal, each vertex in S−M (resp. T−M)should be connected to a vertex in T (resp. S−M). So we pair up the remaining vertices arbitrarily, say {(t_k+1,s_k+1),…,(t_n,s_n)} and add the corresponding directed edges in G. For each remaining source vertex source s_i (i belongs to {n+1,…,m} we add the edge (t₁->s_i) in G. Thus the total number of edges added is max(|sources|,|sinks|).

EDIT: Adding a couple of Examples

For the example in your input. We fist compute a maximal matching, say:

3--1
4--2
7--5
8--6

So we add the edges:

3->2
4->5
7->6
8->1

The remaining (sink) vertex not present in the matching is 9 and so we add the arc from 9 to any source vertex in the matching, say 9->1.

Here's another example that illustrates all the steps of the algorithm:

Input Graph:

12 3   5    9 10  (sources)
\|/   /|\    \/
 4   6 7 8   11   (sinks)

Maximal Matching:

4--1
6--5
11--9

So we add the edges:

4->5
6->9
11->1

Now the remaining sinks are {7, 8} and the remaining sources are {2, 3, 10}. We arbitrary pair 7 with say 2 and 8 with say 3 and add:

7->2
8->3

Finally, the remaining (source) vertex is 10 and we add:

4->10

这篇关于从DAG创建强连通分量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！