For questions about trees in graph theory, which are connected graphs with no cycles. Also can be used for questions about forests, which are graphs that are disjoint unions of trees.

learn more… | top users | synonyms

1
vote
1answer
246 views

For BSP generation, How to intersect or locate a triangle with a plane defined by another triangle?

I've hit a stumbling block in my project to draw the Utah teapot. I want to generate a binary space partition tree of a set of 3D triangles. The decision step in the recursive tree-construction ...
1
vote
0answers
50 views

Enumeration of symbols in grammatical expressions or vertices in tree graphs

I have expressions (type of a function) like e.g. $$f:(A\to B)\to C \to (D\to E)\to F.$$ (Where I understand $A\to B\to C$ as $A\to (B\to C)$, in case that is relevant.) There might be information ...
1
vote
2answers
622 views

single elimination tournament, don't understand question?

A single elimination tournament is performed in rounds. In each round the teams each play exactly one game and the winners continue, and the losers are knocked out of the competition. So, in each ...
6
votes
0answers
319 views

Certain permutations of the set of all Pythagorean triples

The fact that the set of all primitive Pythagorean triples naturally has the structure of a ternary rooted tree may have first been published in 1970: http://www.jstor.org/stable/3613860 I learned ...
0
votes
1answer
188 views

Computational Complexity of Parallel Algorithms

Does parallelism factor in when deriving the computational complexity of a parallel algorithm? Suppose I have a perfect binary tree $T$ with leaves numbered $1$ to $n$, and an algorithm ...
2
votes
0answers
94 views

Presentation of tree decompositions (and related concepts) in terms of continuous maps?

A tree decomposition of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure: Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$; The union ...
2
votes
1answer
94 views

A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing): What I need is a ...
0
votes
1answer
735 views

Is this formula for the number of nodes for a complete tree or a full and complete tree?

In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer: $$ \sum^{h}_{i = 0}k^i $$ where h is the height and k is the max number of ...
3
votes
2answers
3k views

What does lg x mean? is it $\log_2 x$ or $\log_{10} x$ in binary trees

I'm a bit confused, $\log_{10} x = \log x $ right? I believe I've read somewhere that $\log_{2} x = lg x$ but some people say lg = $\log$. So what does lg really stand for? specifically when talking ...
4
votes
2answers
107 views

Real tree and hyperbolicity

I seek a proof of the following result due to Tits: Theorem: A path-connected $0$-hyperbolic metric space is a real tree. Do you know any proof or reference?
2
votes
2answers
3k views

Proof by induction and height of a binary tree

I need some help with a simple proof. I want to know if this proof is correct: Let's define the height of a binary tree node as: 0, if the node is a leaf 1 + the maximum height of the children ...
4
votes
1answer
74 views

Tree formalisms

The intuitive notion of a tree in mathematics is quite straightforward. However, there are several different formalisms of the tree concept. The link http://ncatlab.org/nlab/show/tree lists several ...
4
votes
1answer
286 views

characteristic polynomial of the adjacency matrix of a tree

I have read that if $A$ is the adjacency matrix of a tree $T$, then we have that $$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k} $$ where $N_k(T)$ is the number ...
0
votes
1answer
265 views

Relationship between ordered and binary trees

I am looking for a formula for the number of ordered trees with $n$ vertices and $l$ leaves as well as for a formula for the number of binary trees with $l$ left and $r$ right children. Finally, I ...
1
vote
2answers
357 views

Breadth first search tree's cycles [duplicate]

Possible Duplicate: Proof related to breadth first search I'm trying to prove the following: Suppose a connected graph $G$ has a cycle $C$ of length $n$. Prove that in any breadth-first ...
5
votes
2answers
357 views

Suppose there are two different spanning trees for a simple graph. Must they have an edge in common?

My instinct is yes, but I don't know how to formalize it into a proof. I still haven't wrapped my head around spanning trees yet. Any thoughts are appreciated!
0
votes
1answer
553 views

How to find the maximum number of vertices in a tree with respect to maximum path length and maximum degree value

Given a tree, find the maximum number of vertices $v$ in that tree using the maximum path length $p$ and a maximum degree that applies to all vertices $d$. Assuming that I drew my test tree ...
3
votes
2answers
390 views

Bijection between binary trees and plane trees?

I would like to describe a bijection between binary trees and plane trees. A binary tree has a root node and each node of the tree has at most 2 children (left and right). A plane tree has a root node ...
4
votes
1answer
5k views

Determining if two graphs are isomorphic

The answers are already given after the $=$ sign of each question. But I don't know how they arrived at these answers. What does it mean to say $f(A)=1$ and so on? I can't find the connection.
1
vote
1answer
185 views

Depth first search on graph

I have a homework problem I think I know the answer to, but want to double check Consider the graph with three nodes, $a$, $b$, and $c$, and the two arcs $a \rightarrow b$ and $b \rightarrow c$. ...
1
vote
0answers
49 views

What is the runing time of this algorithm involving length and depth?

I'm hoping that someone can shed some light on this running time. I have a "tree", for lack of a better description, that has a length $l$ and depth $d$. I want to maximize the tree size, which ...
2
votes
1answer
320 views

Length of Shortest Path in a Generated Binary Tree

Let's say I have a binary tree of $2$-tuples of positive integers starting with $(1,1)$. The left-child of any element $(A,B)$ is $(A,A+B)$, and the right-child of any element is $(A+B,A)$. Hence, the ...
0
votes
1answer
1k views

M-ary tree problem

A full $m$-ary tree $T$ has 81 leaves and height 4 1) Give the upper and lower bounds for $m$ 2) What is $m$ if T is also balanced? [with $m^h=l$ for maximum leaf in a m-ary tree $m^4=81$ then m=3 ...
1
vote
2answers
174 views

existence of a spanning tree

Let $T$ and $T'$ be two spanning trees of a connected graph $G$. Suppose that an edge $e$ is in $T$ but not in $T'$. Show that there is an edge $e'$ in $T'$, but not in $T$, such that ...
0
votes
2answers
251 views

Tree problem about preorder notation

Show that an ordered rooted tree is uniquely determined when a list of vertices generated by a preorder traversal of the tree and the number of children of each vertex are specified.
2
votes
1answer
176 views

Probability of passing through 3 specific nodes along a binomial tree

Consider a re-combining binomial tree with probability of up = $p$ and probability of down = $(1-p)$. Let $n$ be the number of time steps in the binomial tree (the $x$-axis is time, and each column of ...
2
votes
1answer
664 views

Oriented trees and ordered trees

I have this confusion regarding ordered and oriented trees. I know they are both rooted and in ordered trees, the order is important. So lets say I have four nodes 1,2,3,4 then it is given that the ...
2
votes
0answers
74 views

Groups acting on (regular) trees with finite quotient

Let $T$ be a regular tree, and suppose that $G \leq \mathrm{Aut}(T)$ has finite quotient graph, $T / G$. Is it true (in general) that $G$ will have trivial centralizer in the full automorphism group? ...
1
vote
0answers
84 views

How can I prove this property of a $d$-ary tree?

I have the following homework (algorithms lecture): Every $d$-ary tree $G=(V,E)$ contains a vertex $v$ such that the size of the subtree with root $v$ is at least $\frac{1}{d+1} \vert V \vert$ and at ...
0
votes
1answer
523 views

Help in understanding search of Vantage-Point tree

This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
1
vote
1answer
37 views

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set. Give some clue please! Thanks anyway!
0
votes
1answer
84 views

Constructing a tree from disjoint graphs

I will preface my question with the definition of a simple tree that applies to my question: -"A simple tree is an undirected and connected graph with no cycles."- I am having difficulty coming up ...
1
vote
3answers
1k views

Graph with cycles proof questions

Two questions I'm stuck with: If C is a cycle, and e is an edge connecting two nonadjacent nodes of C, then we call e a chord of C. Prove that if every node of a graph G has degree at least 3, then ...
0
votes
1answer
85 views

Natural order of rational trees?

What would be a natural order of rational trees? Rational trees arise naturally from free algebras if we view a term as a finite tree. For example the term f(a,g(b,c)) could be viewed as the ...
5
votes
1answer
715 views

Every automorphism of a tree with an odd number of vertices has a fixed point

If $T$ is a tree, and $T$ has an odd number of vertices, then $\forall f$, where $f$ is automorphism $\Rightarrow \exists$ fixed point (vertex). What it means: Formally, an automorphism of a tree $T$ ...
0
votes
1answer
674 views

How to make a parse tree for the following propositional logic formula?

I have a formula $\neg (( q \rightarrow \neg q) \vee p \vee ( \neg q \rightarrow ( r \wedge p)))$. As it contains 3 subformulas between the $\vee$'s, how can I put it into a parse tree. Would it be ...
0
votes
2answers
599 views

Proof for Full Binary Tree Using Handshaking Lemma?

I asked a question a few days ago and figured out the proof for this theorem using induction. ...
0
votes
1answer
710 views

Proving terminal vertices and total vertices of a full binary tree?

I am trying to make a proof by induction of the following theorem. ...
0
votes
1answer
225 views

A binary tree in 3-ary tree

We have an infinite $3$-ary tree, with root $R$. In coloring $C(p)$ each edge is black with probability $p$ and white with probability $1 - p$, and edges are independent. Show that there is a ...
3
votes
2answers
234 views

Why for number of leaves in a tree (all types of trees) is it true

I have to prove the following claim, given the tree $T=(V,E)$, $|V|\geq3$: $$|V_1| \leq \frac { |V| \times (\Delta (V) - 2) + 2 }{ \Delta (V) - 1 } $$ where $|V_1| - $ number of leaves in a tree, and ...
1
vote
0answers
54 views

How to formulate a best-search algorithm limited by a count of nodes visited?

The problem I'm doing a search by computer program. Each node takes about 5 minutes of wall time to get a result so I'm looking to carefully choose the nodes to inspect so as to find the best result ...
1
vote
2answers
700 views

graph theory and forests

We were given an this question in my class: Prove that a forest with n vertices and m components has n-m edges using induction on m. Induction is not my strongest point and I was wondering if anyone ...
2
votes
1answer
92 views

About finiteness of trees

I am reading a book of Michael Sipser "Introduction to the theory of computation", and there is a theorem, which he gives without a proof: "If every node of a tree has only finitely many children and ...
2
votes
3answers
599 views

Applications of the number of spanning trees in graphs

Let $G$ be a simple graph and denote by $\tau(G)$ the number of spanning trees of $G$. There are many results related to $\tau(G)$ for certain types of graphs. For example one of the prettiest (to ...
3
votes
2answers
124 views

Bounds on how far away most leaves are from the average height of a binary tree

I'm wondering if anyone can help me prove (or disprove) this statement? Say there is a rooted full binary tree (each non-leaf node has exactly two children) with a height of $h$, an average height ...
0
votes
1answer
500 views

Proving by induction

I'm having a problem relating to proving by induction that the Preorder(T) and Postorder(T) algorithms both print out all the nodes in the tree without repetition. I'm not quite sure where to start.. ...
0
votes
2answers
336 views

Category of Trees as sub-category of Category of Graphs

A tree (like a binary search tree) is a direct graph with some limitations (no cycles, connected). How can I express the category of trees as "sub-category" of a graphs? There is a way? I'm not sure ...
0
votes
2answers
604 views

Explanation of why the height of a binary tree $\theta({lg}(n))$.

From Heap Sort chapter of Introduction to algorithms : Since a heap of n elements is based on a complete binary tree , its height is $\theta({lg}(n))$. I know this is correct but how can this ...
0
votes
1answer
80 views

Number of leaves in a tree that represents a kind of permutations

Consider the following rooted tree, each of whose vertices (except for the root) is labeled with an integer $\in\{1,\dots,n\}$: let $s(v)$ be the sequence consists of the labels on the path from the ...
6
votes
1answer
662 views

Understanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.

I was reading the Wikipedia article on Friedman's finite form of Kruskal's tree theorem, and am interested in the large numbers TREE(n). I would like to verify TREE(2)=3 myself, but find conflicting ...