A tree is a graph that is connected but contains no cycles.
1
vote
3answers
86 views
Comparison trees
You have 60 coins. You know that 1 coin is either lighter or heavier than the other coins. How many comparisons are needed in a worst case scenario to discover which coin is the false one and ...
1
vote
2answers
360 views
Graph - Minimum spanning tree
I have a graph with a cycle ($v_1,\ldots,v_k, v_1=v_k$).
Claim: If there is a cycle with 2 edges of the same weight, and they are the heaviest edges in this cycle, then there is more than one Minimum ...
1
vote
3answers
33 views
Parent and childs of a full d-node tree
i have a full d-node tree (by that mean a tree that each node has exactly d nodes as kids).
My question is, if i get a random k node of this tree, in which position do i get his kids and his parent?
...
1
vote
0answers
59 views
Finding number of homeomorphically irreducible trees of degree N
There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree 10. This is discussed in many places, such as here and is ...
1
vote
0answers
37 views
Red Black Binary Search Trees
Give an example of a Red-Black tree and a value, for which inserting the value, and then
immediately deleting it yields a tree that is different from the tree before the insertion.
1
vote
0answers
29 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
1answer
106 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 ...
1
vote
1answer
130 views
What is the fairest solution/formula for rewarding points in a hierarchical network?
Introduction
The nature of this hierarchical network is based on the concept of Multi-Level Marketing strategy.
Example 1 - Unfair Situation
Ancestor receives 1 point for every descendant ...
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
16 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?
1
vote
0answers
31 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
0answers
161 views
A tree that does not satisfy: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$?
It is a strange question on a book.
Give an example of a tree $T$ that does not satisfy the following property: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$.
I ...
1
vote
0answers
42 views
Keeping consistency in subjective ranking
I'm doing some work on a computer program that aids in ranking items which don't have a way to objectively compare to each other.
As it is now, it takes each item and pairs it up with each other ...
1
vote
0answers
146 views
Finding the number of spanning trees of a given height
I hope I can avoid being confusing, but here goes.
I have a graph $(V, E)$, connected, undirected and with no loops. I also have an assignment of integer-valued weight to each edge of the graph. ...
1
vote
0answers
77 views
Concerning The 'Price-Collecting Steiner Tree'
I'm a Master student at the University of Leuven, Belgium. I have to make a report of a case concerning the 'Price-Collecting Steiner Tree'. We have our model and our restrictions. We are just looking ...
0
votes
2answers
493 views
Searching a binary search tree for a specific value
suppose numbers from 1 to 1000 are saved in a binary search tree and we want to find 363. Which of the following sequences cannot be the order of elements while reaching the searched value?
925, ...
0
votes
2answers
146 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
141 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
40 views
Getting a values from nodes
The goal: get horizontal values of vertical level N where level 1 is pinacle node (1).
Example: level 4 as input should produce: | 1 | 3 | 3 | 1 |
Note: the sum ...
0
votes
3answers
301 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 ?
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
...
0
votes
2answers
569 views
About balanced and complete binary tree
I found this and I just couldn't verify it. How come it is true?
The maximum number of nodes that a balanced binary tree with depth $d$ is a complete binary tree with $2^d-1$ nodes.
Let say I have ...
0
votes
1answer
283 views
Maximum height of a quad tree
If we have a quad tree where each node must have 0 or 4 children, is there an expression that can me the maximum height of a quad tree with $n$ nodes?
0
votes
1answer
54 views
Prove that there are two end points in a tree with a common neighbor
Let $T=(V,E)$ be a tree with at least $3$ vertices. Assume that every vertex has either degree $1$ or a degree of at least $3$ (so there are no vertices with degree $2$). Prove that there are two end ...
0
votes
2answers
51 views
Prove there is a tree with $n$ vertices having degrees $d_1, d_2…d_n$
For $n â„ 2$ suppose $d_1, d_2,....d_n$ are positive integers with sum $2n - 2$. Prove there is a tree with n vertices having degrees $d_1, d_2....d_n$. I'm at a loss on this one. I'm sure it's pretty ...
0
votes
2answers
65 views
Question: Graph Theory and Trees
In a group of 2n schoolchildren each one has at least n friends. On an outing, the teacher tells them to hold hands in pairs. Show that this can be done with each child holding a friendâs hand, and ...
0
votes
2answers
38 views
how to store a math problem in a binary tree?
If I have the following problem: $\ 12 - (2 +3) - (3 *4)/ (5 -7) $
How would it be stored in a binary tree?
following the order of operations, would you start with $\ (3*4) $ at the top or $\ 12 $ ...
0
votes
1answer
50 views
Recurrence relation for the number of spanning trees in a connected graph proof
The number of spanning trees in a graph $G$ containing an edge $e$ is equal to the number of spanning trees in $G/e$. The number of spanning trees in a graph $G$ not containing an edge $e$ is equal to ...
0
votes
2answers
154 views
Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle
When proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle, is it sufficient to just remove that edge that created a cycle, then it ...
0
votes
2answers
133 views
Confusion related to a graph problem
I have this question related to this graph problem
Suppose that an n-node undirected graph G = (V , E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. ...
0
votes
1answer
39 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
1answer
42 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
2answers
105 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.
0
votes
2answers
162 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
165 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 ...
0
votes
1answer
71 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 ...
0
votes
2answers
74 views
Narrowing a Stern-Brocot tree
Say I only wanted to enumerate the rational numbers between 0 and $a$. Is there a way to "narrow" a Stern-Brocot tree to provide this? I tried keeping my left bound at "$\frac{0}{1}$" and setting my ...
0
votes
1answer
157 views
Is smallest binary tree simply root node? Or does it need to have two child nodes?
Apologies for this rather simplistic question, I've just started looking at binary trees and the material I've been provided wasn't explicit about this.
Presumably a parent node of a binary tree can ...
0
votes
1answer
33 views
Correspondence between fractal sets and trees
In Hillel Furstenberg's series lectures on ergodic theory in fractal geometry, he mentioned his search on finding a one-to-one correspondence between fractal sets and trees, however, I couldn't not ...
0
votes
1answer
35 views
Let T be a tree with sub-trees which each set has a vertex in common - hence T has a vertex in all of its sub-trees?
The question is:
Let T be a tree with sub-trees $T_1,T_2,..,T_n$ such that all trees $T_i,T_j$ have a vertex in common which each set has a vertex in common - show that T has a vertex in all $T_i$.
...
0
votes
1answer
209 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 ...
0
votes
1answer
135 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 ...
0
votes
1answer
214 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 ...
0
votes
1answer
80 views
Prove equivalence of conditions for a tree
Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent.
$G$ is a tree.
Any two vertices in $G$ can be connected by a unique simple path.
$G$ is ...
0
votes
1answer
69 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
...
0
votes
1answer
246 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
1answer
201 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
2answers
182 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 ...
0
votes
1answer
162 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..
...
