algorithm - 如何查找图是否是树及其中心

Question

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

1) 如果 G 是否是树(检查 |V| = |E|+1 是否足够？)

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

谢谢

Answer 1

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

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)

队列中剩下的最后一个是中心。

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

我们可以看到:

1. M不会被推到que的后面，直到每个节点都在直径路径已被插入队列
2. 如果有另一个节点N在 M 已经被插入队列之后被插入，那么 N 必须在比直径路径更长的路径上。因此N不可能存在。 M必须是最后一个节点在队列中被插入(并离开)