6
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 1, 2010 at 13:38
  • 2
    $\begingroup$ 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. $\endgroup$
    – Cam McLeman
    Commented Sep 1, 2010 at 14:18
  • $\begingroup$ I already had a look at all the wikipedia articles. However, none of them explains how to describe a big collection of graphs. $\endgroup$
    – Thomas1972
    Commented Sep 2, 2010 at 9:02

4 Answers 4

Reset to default
2
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • $\begingroup$ >> 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. $\endgroup$
    – Thomas1972
    Commented Sep 2, 2010 at 9:06
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0
2
$\begingroup$

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
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ By "fan-out" do you perhaps mean what is usually termed the degree (or valency) of each node, possibly minus 1? $\endgroup$
    – J W
    Commented Sep 1, 2010 at 18:39
  • $\begingroup$ @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. $\endgroup$
    – Christopher Creutzig
    Commented Sep 4, 2010 at 8:24
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .