<p>What are good measures of tree-like-ness of a graph and algorithms for calculating them?</p>

CC BY-SA 3.0
2011-07-04T02:03:22.697Z
There are many ways to measure the "tree-like-ness" of a graph. Which property of the tree would you like to preserve?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-07-04T02:37:00.320Z
I'm not exactly sure.  Since trees don't have cycles, the number and length of cycles in a graph would seem to be a good negative measure of "tree-like-ness".  But (if we consider directed trees), uni-directionality also seems like an important characteristic of trees.  For instance, I would like a measure that says that a graph is _highly_ tree-like if it's a highly overlapping heterarchy with only two top-level nodes, and if directed, a particular dominant (but not necessarily universal) directionality.
mwhite
CC BY-SA 3.0
2011-07-04T06:06:02.540Z
Have a look at http://en.wikipedia.org/wiki/Tree_decomposition
Martin Schwarz
CC BY-SA 3.0
2011-07-04T09:42:11.717Z
Based on the comment, it sounds like you are interested in graphs that resemble an *arborescence*, i.e., a directed rooted tree in which all edges point away from the root node. (In general, a directed tree does not necessarily have any "dominant directionality".)
Jukka Suomela
<graph-theory><co.combinatorics><graph-algorithms><tree>
How to quantify the tree-like-ness of a graph?
mwhite
# How to quantify the tree-like-ness of a graph?

(Asked by: username_0 on 2011-07-04)

What are good measures of tree-like-ness of a graph and algorithms for calculating them?

**Tags:** graph-theory, co.combinatorics, graph-algorithms, tree

> **Comments:**
> **username_1**: There are many ways to measure the "tree-like-ness" of a graph. Which property of the tree would you like to preserve?  
> **username_0**: I'm not exactly sure.  Since trees don't have cycles, the number and length of cycles in a graph would seem to be a good negative measure of "tree-like-ness".  But (if we consider directed trees), uni-directionality also seems like an important characteristic of trees.  For instance, I would like a measure that says that a graph is _highly_ tree-like if it's a highly overlapping heterarchy with only two top-level nodes, and if directed, a particular dominant (but not necessarily universal) directionality.  
> **username_2**: Have a look at http://en.wikipedia.org/wiki/Tree_decomposition  
> **username_3**: Based on the comment, it sounds like you are interested in graphs that resemble an *arborescence*, i.e., a directed rooted tree in which all edges point away from the root node. (In general, a directed tree does not necessarily have any "dominant directionality".)  

---

## 0 answers

