如何查找图表是否为树及其中心

Question

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

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. 在直径路径上的其他节点都被推入que之前,M不会被推到que的后面
2. 如果在M已经被推入que之后有另一个节点N被推动,那么N必须在比直径路径更长的路径上.因此N不可能存在.M必须是在que中推送(和左)的最后一个节点