5

G=(V,E)给定一个没有父节点、叶节点和子节点概念但只有邻域关系的通用图结构，是否有一种算法（或一系列算法）可以找到：

1）G是否是一棵树（检查是否足够|V| = |E|+1？）

2）如果图实际上是一棵树，它的叶子和中心呢？（即最小化树深度的图节点）

谢谢

4

3 回答 3

7

如果树的“中心”被定义为“最小化树深度的图节点”，那么找到它的方法比找到直径更容易。

d[] = degrees of all nodes
que = { leaves, i.e  i that d[i]==1}
while len(que) > 1:
  i=que.pop_front
  d[i]--
  for j in neighbors[i]:
    if d[j] > 0:
      d[j]--
      if d[j] == 1 :
        que.push_back(j)

que中剩下的最后一个是中心。

您可以通过考虑直径路径来证明这一点。为简化起见，我们假设直径路径的长度是奇数，因此路径的中间节点是唯一的，我们称该节点为 M，

我们可以看到：

  1. 在直径路径上的所有其他节点都被推入队列之前，M 不会被推到队列的后面
  2. 如果在 M 已经被推入 que 之后还有另一个节点 N 被推入，则 N 必须在比直径路径更长的路径上。因此 N 不存在。M 必须是 que 中最后一个推入（并离开）的节点
于 2012-10-29T00:10:15.443 回答
2

  1. 不，这还不够——一棵树是一个有n-1边的连接图。未连接的图中可能有n-1边 - 它不会是一棵树。
    您可以运行BFS来查找图是否已连接，然后计算边数，如果图是树，这将为您提供足够的信息

  2. 叶子是具有由等式给出的节点v度数的节点（每个节点只有一个连接的顶点）d(v)d(v) = 1

(1) 答案假设无向图
(2) 在这里，n表示顶点数。

于 2012-10-28T22:09:46.720 回答
2

对于 (1)，您所要做的就是验证 |V| = |E| + 1 并且该图是完全连接的。

对于 (2)，您需要找到一个最大直径，然后在直径路径的中间选择一个节点。我隐约记得有一种简单的方法可以对树木执行此操作。

您从一个任意节点开始a，然后在距离 的最大距离处找到一个节点a，调用它b。然后你搜索b并找到一个距离最大的节点b，调用它c。b从到的路径c是最大直径。

还有其他可能对您更方便的方法，比如这个。 也检查谷歌。

于 2012-10-28T22:10:33.140 回答