Centered tree

In discrete mathematics, a centered tree is a tree with only one center, and a bicentered tree is a tree with two centers.

On the left a centered tree, on the right a bicentered one. The numbers show each node's eccentricity.

Given a graph, the eccentricity of a vertex v is defined as the greatest distance from v to any other vertex. A center of a graph is a vertex with minimal eccentricity. A graph can have an arbitrary number of centers. However, Jordan (1869) has proved that for trees, there are only two possibilities:

  1. The tree has precisely one center (centered trees).
  2. The tree has precisely two centers (bicentered trees). In this case, the two centers are adjacent.

A proof of this fact is given, for example, by Knuth.[1]

Notes
  1. (Knuth 1997), p. 387 and p. 589
gollark: It might actually be worse in that case, because at least for the universe thing you can just lean on the anthropic principle - if things *had* gone differently such that we did not exist, we would not be here to complain about it.
gollark: I am saying that gods are also complicated so this doesn't answer anything.
gollark: For purposes only, you understand.
gollark: There are lots of *imaginable* and *claimed* gods, so I'm saying "gods".
gollark: So basically, the "god must exist because the universe is complex" thing ignores the fact that it... isn't really... and that gods would be pretty complex too, and does not answer any questions usefully because it just pushes off the question of why things exist to why *god* exists.

References
  • Jordan, Camille (1869). "Sur les assemblages de lignes". Journal für die reine und angewandte Mathematik (in French). 70 (2): 185–190.
  • Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley Professional. ISBN 0-201-89683-4.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.