How to find if a graph is a tree and its center

Question

Is there an algorithm (or sequence of algorithms) for searching taking into account the general structure of the graph G=(V,E) without the concept of a parent node, leaf node and child node, but only relations with neighbors:

1) If G is a tree or not (just check |V| = |E|+1 ?)

2) If the graph is actually a tree, then the leaves and its center? (i.e. node graphics that minimize tree depth)

thanks

Answer 1

If the "center" of a tree is defined as the "node of the graph that minimizes the depth of the tree", there is an easier way to find it than to find the diameter.

 d[] = degrees of all nodes que = { leaves, ie 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) 

and the last remaining in que is the center.

you can prove it by thinking about the diameter path. for simplicity, we assume that the length of the diameter path is odd, so that the middle node of the path is unique, let's say that node M,

we can see that:

• M will not be placed at the end of the queue until all node else on the diameter path has been placed in que
• if there is still a node N that is pushed out after M has already been placed in the que, then N should be on a longer path than the diameter path. Therefore, N cannot exist. M should be the last node pressed (and left) in que

Answer 2

• No, this is not enough - the tree is a CONNECTED graph with edges n-1 . An unconnected graph may have n-1 edges, and it will not be a tree.
  You can run BFS to find out if a graph is connected, and then count the number of edges, which will give you enough information if graph is a tree

• Leaves are nodes v with the degree of nodes denoted by d(v) given by the equation d(v) = 1 (which have only one connected vertex)

---

(1) The answer involves undirected graphs.
(2) Here n denotes the number of vertices.

Answer 3

For (1) all you have to do is check | V | = | E | + 1 and that the graph is completely connected.

For (2) you need to find the maximum diameter and then select node in the middle of the diameter path. I vaguely remember that there is an easy way to do this for trees.

You start with an arbitrary node a , then find the node at the maximum distance from a , name it b . Then search b and find node at the maximum distance from b , name it c . The path from b to c is the maximum diameter.

There are other ways to do this, which may be more convenient for you, for example this one . Check google too .