How to describe a tree? (depth, degree, balance, ... what else?) Hello,
I do have a collection of trees (mind maps, actually) and want to formally describe this collection of trees. 
My first question: how can I describe a tree? Are there any metrics to express how a tree looks like? Of course, it has a height and it might be balanced or not. But are there any other metrics (e.g. to say how balanced a tree is)?
The second question: How can I describe a collection of different trees. Do you know of any metrics that make sense? Of course I could calculate the mean height etc. but are there some more sophisticated metrics?
Best,
Thomas
 A: One metric on trees that has received a lot of attention over the past ten years is the one introduced by Billera, Holmes, and Vogtmann in their paper, "Geometry of the space of phylogenetic trees."  I am not sure what you mean by "mind maps", but this metric has been of particular interest for statistical and biological applications, so it is probably worth a look.
A: As others indicated, trees are an active research area and there are lots of characteristics to choose from. For mind maps especially, the following characteristics come to mind:


*

*fan-out: every node has a fan-out. The average/min/max fan-out of non-leaf nodes could be of interest

*longest path: Similar to depth, but ignoring the current root node

*average length to leafs, the distribution of these lengths (the statistics of these should give you various possible measures of balanced-ness)

*number of distinct labellings (up to isomorphisms): This indicates how asymmetric the tree is

A: Mind maps, as desribed on their wikipedia page, are a way of mapping or placing a graph structure onto a collection of data.
Items can be linked together with directed edges and with a label on the edge describing the relationship.  Each data item at a vertex can taken on multiple tags (coloring) to describe their type.
If you have a Linux distribution that has the KDE (Kommon Desktop Environment, as opposed to the CDE Common Desktop Environment in Solaris) environment, you can see an implementation of mind maps in a note taking and note organizing software package

BasKet Notepads http://basket.kde.org/

The wikipedia page for BasKet is rather sparse and uninformative at http://en.wikipedia.org/wiki/BasKet_Note_Pads and does not really describe the full potential of the note organizing software.
The Mind Map software seems to be made for "rapid collaborating" and "brainstorming", very fuzzy words that seem to match the warm soft fuzzyness of the software.  I have played with it, but it is poorly structured and not amazingly useful for organizing my research information.
It is, however, very useful for laying out quick hierarchical diagrams or tree diagrams.  It does not easily allow one to export the graph structure in a useful and easy to reuse file format.
As for describing the structure: just look at it as a graph.  Do you have any one-way oriented relationships on it?  (e.g. links such as PARENT-OF, REFERS-TO, DERIVED-FROM, COMES-AFTER)  If so, then you have a directed graph, otherwise you have an undirected graph.
How many elements are there?  That is the number of vertices.
How many relations/links are there?  That is the number of edges.
How many edges are there connecting each vertex?  The number of edges on a vertex is the degree of the vertex.  In a directed graph, you can have out-degree for outward-linking edges and in-degree for inward linking  edges.  What is the fewest number of edges?  What is the largest number of edges on a vertex?
Draw a histogram of how many vertices have zero edges (free disconnected vertices), how many have one, two, etc.  List them in order and you have the degree sequence of the graph.
Look at all of the elements; can you reach them all from one to another by following edges?  Then you have a single connected graph.  If you have separate islands that are not linked, count the number of islands as the number of components in the graph.  Recursively describe each of these islands as listed above.
This is a simple way to. start.  Treat the diagram as a graph and describe it in good detail.  Could you please provide more details about what you are doing, or perhaps an example structure?
A: A collection of trees is called a forest, unsurprisingly.  Your graphs are considered trees only if the edges are undirected, i.e. the relationships described are "two-way", e.g. X is related to Y can be restated validly as Y is related to X.  This is known as a symmetric binary relationship.  If your edges are directed, then the graphs are not correctly called trees.  The relationships described above are asymmetric, creating links which are also not symmetric.  
You might consider searching for "forest mathematics" on wikipedia and in mathematical journals to get some other terms to consider for evaluating and describing your collection of graphs.
