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



How to describe a tree? (depth, degree, balance, ... what else?)
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?


