What are some features of trees (graph theory)?

51 Views Asked by At

I understand that trees have a center and longest path(s). Are there any other features trees have? Also, are there different types of "longest paths"?

I'm really sorry if this question doesn't make sense, but I wasn't able to find a lot of information on this online.

1

There are 1 best solutions below

3
On

There are two features of trees that I always found interesting. First, they are minimally connected: the removal of any edge creates a disconnected graph; second, they are maximally acyclic on their set of vertices: joining any two vertices with a new edge produces a cycle.

So, trees are delicately balanced between diconnected graphs and graphs with cycles.

A standard way to define length of a path in a tree is by the number of edges it uses. However, one may assign weights to each edge and interpret the length of a path as the sum of the weights of the edges in the path. This setup allows for the somewhat disconcerting situation in which a path using more edges may actually be "shorter" than one using fewer edges.

EDIT: Re my comment to Neal. I have been sloppy. I am thinking in terms of paths connecting arbitrary pairs of vertices, not a specific pair. So, the path connecting a particular pair of vertices may use fewer edges than the path connecting a different pair, yet still be longer due to the weights of the edges in the two paths,