Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
1. I retagged from [decision-trees] to [co.combinatorics] [graph-theory], but I am not sure if these tags are the right ones. 2. The question is very vague and may not be suitable on MathOverflow. –  Tsuyoshi Ito Sep 1 '10 at 13:38
2  
There are many many adjectives which describe trees. I'd recommend you spend some time with a nice survey article (or maybe even the wikipedia page) to get acquainted with them. Your question about how balanced a tree is sounds potentially interesting, but I think you'll be able to ask it better after having done some more reading. –  Cam McLeman Sep 1 '10 at 14:18
    
I already had a look at all the wikipedia articles. However, none of them explains how to describe a big collection of graphs. –  Thomas1972 Sep 2 '10 at 9:02
add comment

4 Answers

up vote 2 down vote accepted

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?

share|improve this answer
    
>> Could you please provide more details about what you are doing, or >>perhaps an example structure? Look here, for instance: mindmeister.com/maps/public There is a collection of around 14,000 mind maps. I have a similar collection and want to describe this collection. So I would like to create statements such as -80% of all mind maps in the collection have more than 100 nodes -The average depth of a mind map is 5 ... Now I am looking for some more metrics like this that help me to describe how the collection of mind maps looks like. –  Thomas1972 Sep 2 '10 at 9:06
add comment

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
share|improve this answer
1  
By "fan-out" do you perhaps mean what is usually termed the degree (or valency) of each node, possibly minus 1? –  J W Sep 1 '10 at 18:39
    
Thank you very much, this answer was helpful :-). –  Thomas1972 Sep 2 '10 at 9:01
    
@JW: In an undirected graph, degree - 1, right. Else, outdegree - indegree. From what I have seen, this term is mostly used when the trees describe some sort of process or search space. –  Christopher Creutzig Sep 4 '10 at 8:24
add comment

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.

share|improve this answer
    
thank you, i will have a look at it! –  Thomas1972 Sep 2 '10 at 9:02
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.