2

有谁知道从有向图计算线有向图的有效算法？请参阅http://en.wikipedia.org/wiki/Line_graph（维基百科文章在底部附近提到了二合字母案例（在概括部分中）。理想情况下，我希望在线性时间内做到这一点。

从那个部分：

  • 如果 G 是有向图，则其有向线图或有向线图对 G 的每条边都有一个顶点。
  • 当 v = w 时，表示 G 中从 u 到 v 和从 w 到 x 的有向边的两个顶点由线有向图中从 uv 到 wx 的边连接。

令 G 为有向图 令 L(G) 为有向线图

在给定 G 的情况下，我可以想出的生成 L(G) 的算法是：

  • 遍历 G 的所有边以产生 L(G) 的节点
  • 遍历 L(G) 中的所有节点对 (uv, wx) 并在 v = w 时连接

这是一个 O(n^2) 算法。

似乎应该有一种方法可以将其降低到 O(n) 时间。我要考虑一下，但我想我会问堆栈溢出，以防万一有一些我不知道的著名（或不那么著名）算法可以做到这一点。

4

2 回答 2

1

嗯...我认为经过一番思考后可能会有一种更省时的算法...但是这样做需要大量的簿记和大量的额外内存。

我的基本想法是遍历 G 中的所有节点，并从连接到每个节点的边创建连接节点。通过一个额外的链接来跟踪 G(edge) 到 L(G)(node)，您可能只需一个循环通过 G 上的节点就可以逃脱。

于 2009-06-03T21:57:53.287 回答
1

您无法从 O(n^2) 中进行扩展，因为有些图具有线性图，其边的基数等于原始顶点的基数的平方：例如，在具有 n+1 个顶点的图，其中一个顶点连接到其他所有顶点：然后您必须构建一个具有 n 个顶点的集团，因此具有 (n-1)^2 条边。

算法的复杂性从底部开始受到它产生的输出大小的限制。

当然，这并不意味着我们不必寻找智能算法。我当时是这么想的：

LG(LN,LE) getLinearGraph(G(N,E)) {
  LN = EmptySet();
  LE = EmptySet();
  for (Vertex v : N) {
    verticesToAdd = EmptySet()
    for (Vertex i : out-degree(v) {
      toAdd += textual-rep((v,i));
    }
    LN += toAdd;
    LE += make-clique(toAdd);
  }
}
于 2009-06-03T22:03:52.713 回答