A tree is a graph that is connected but contains no cycles.
0
votes
1answer
144 views
Determining Ambiguity in Context Free Grammars
What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have?
For example, consider the following Grammar G:
$S \rightarrow ...
1
vote
0answers
26 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
101 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
215 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
36 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 ...
0
votes
2answers
3k views
The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.
I am confused with this statement
The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$.
How come this is true. Lets say I have the following tree
...
2
votes
0answers
40 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 ...
0
votes
0answers
67 views
Spanning Tree question regarding fundamental cycle / cutset
Hello i have a question regarding this graph and i am not sure about the answer.
Given the following graph (image in link), where the dotted lines are edges of a spanning tree, find the fundamental ...
2
votes
1answer
46 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
58 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 ...
2
votes
2answers
117 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 ...
3
votes
2answers
65 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
240 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
...
2
votes
1answer
43 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
0answers
53 views
Free medial magmas
A medial magma is a set $M$ with a binary relation $*$ satisfying $(a*b)*(c*d) = (a*c)*(b*d)$. Medial magmas constitute an algebraic category $\mathsf{Med}$, therefore there is a functor $\mathsf{Set} ...
0
votes
0answers
43 views
Constructing steiner tree
Given 4 nodes with edge values as stated below, is it possible to build a minimum spanning tree using Steiner tree?
...
2
votes
3answers
1k views
How to show that every connected graph has a spanning tree, working from the graph “down”
I am confused about how to approach this. It says:
Show that every connected graph has a spanning tree. It's possible to
find a proof that starts with the graph and works "down" towards the
...
4
votes
1answer
102 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
132 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
169 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
141 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
198 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
91 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 ...
3
votes
1answer
2k 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
99 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
41 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
115 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
0answers
75 views
Bootstrap sampling
The usual way to create bootstraps is by sampling with replacement from the original data set.
The resulting resampled bootstraps have the same length (N records/data points) as the original data ...
0
votes
0answers
82 views
Bounding the number of nodes in a sub-tree of a Red Black Tree
Let T be a Red Black tree with n nodes.
Let v be a child of a child of the root.
Find a tight asymptotic lower bound as a function of n to the number of nodes in the sub-tree of v (meaning the root of ...
0
votes
0answers
49 views
Upper bound for number of unlabelled trees?
Is there even a remotely good formula for the upper bound for the number of unlabelled trees. I know of Knuth's formula for asymptotic behaviour, but that is not always above the actual value. The ...
0
votes
1answer
40 views
How to establish bijective between the set of rooted trees and natural numbers, using Godel numbering?
Consider the structure of a rooted tree independent of its underlying set, (i.e. in the sense of trees as combinatorial species). I know a number of ways which we can encode any such tree in natural ...
0
votes
1answer
102 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
96 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
100 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
98 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
207 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
37 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
48 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 ...
1
vote
0answers
15 views
Is there a fast tree balancing algorithm when addition > deletion
Is there a tree balancing algorithm / tree structure that is faster on addition of nodes than on deletion?
0
votes
1answer
58 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
35 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!
1
vote
2answers
604 views
Minimum Number of Nodes for Full Binary Tree with Level $\lambda$
If the level ($\lambda$) of a full binary tree at zero is just a root node, than I know that I can get the maximum possible number of nodes (N) for a full binary tree using the following:
N = ...
0
votes
1answer
49 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 ...
0
votes
3answers
275 views
What is the main difference between a free tree and a rooted tree?
In graph theory what is the difference between a rooted tree and a free tree ? What is normally meant when just the plain "tree" is used ?
1
vote
3answers
490 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
68 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
152 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
234 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
156 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
171 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.
...
