A tree is a graph that is connected but contains no cycles.
0
votes
0answers
5 views
Minimal Red-Black tree with depth 3
I'd like to ask what is minimal RBT with black depth 3. Is this following RBT ? Values are not important.
3
votes
2answers
38 views
In any tree, what is the maximum distance between a vertex of high degree and a vertex of low degree?
In any undirected tree $T$, what is the maximum distance from any vertex $v$ with $\text{deg}(v) \geq 3$ to the closest (in a shortest path sense) vertex $y$ with $\text{deg}(y) \leq 2$? That is, $y$ ...
2
votes
2answers
26 views
Embedding of Tree
Q.
Proof for every Tree can be embedded into the plane.
Conditions.
We cannot use Euler Formula for Planar Graphs. We can use definition of tree, $V-E=1$, no-cycles, every edge is critical, there ...
1
vote
3answers
31 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?
...
4
votes
2answers
53 views
How many vertices of degree 1 in a tree?
How many vertices of degree 1 are there in a tree with no vertices of degree more than 4?
The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of ...
0
votes
2answers
48 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 ...
1
vote
2answers
43 views
Trees with vertex set
I am having hard time understanding and solving the following question:
There are exactly three trees with vertex set {1,2,3}. Note that all these trees are paths; the only difference is which ...
3
votes
1answer
44 views
How many vertices of degree 3 or more can have a tree have at most?
It is known that a tree $T=(V,E)$ has at least $\Delta$ leaves, where $\Delta$ is the maximum degree of $T$. But how many vertices of specific degree at least $k$ can a tree have at most? I'm ...
1
vote
1answer
142 views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
Moderator Note: This is a current contest question on codechef.com.
What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i ...
1
vote
0answers
28 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 ...
0
votes
2answers
59 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
36 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 $ ...
2
votes
1answer
18 views
Proof of the Converse of Kraft's Theorem
So I have already proven Kraft's theorem for ternary trees, and I have been tasked with proving the converse. That is, I need to show that there is a ternary tree with $k$ leaves, such that leaf $i$ ...
0
votes
0answers
20 views
Simplification of a dervived binary tree with n nodes [duplicate]
hi I need help with this problem how do simplify this equation and what are the steps and approaches to this problem
14
votes
2answers
192 views
Is there a “tree-like” proof of compactness theorem in the case of uncountably many variables?
I like proofs using trees and König's lemma, since they are very visual.
One of the applications of König's lemma you can show to students is proving compactness theorem for propositional calculus, ...
0
votes
0answers
44 views
What is the algorithm to sort 5 elements in 7 binary comparisons?
I'm tasked with finding the algo that sorts 5 elements in 7 binary comparisons. (The 7 is derived from ceilingFunction(log 5!), which our text states is the minimum number of comparisons required for ...
2
votes
2answers
91 views
Tree pruning question…
all. I'm facing the question:
"A chain letter starts when a person sends a letter to five others. Each person who receives the letter either sends it to five other people who have never received it ...
0
votes
0answers
18 views
2-3-4 Tree: how to insert numbers to optimise the layers?
Let's imagine I have number in a list from 1 to 15, then the way to have 2 full rows is to insert them with this order into an empty 2-3-4 tree
2,4,6,8,10,12,14,1,3,5,7,9,11,13,14,15
(you can test ...
2
votes
0answers
31 views
Mathematical notation for formulas involving trees
I am working on document that requires me to write such things as "$T_1$ is a descendant of $T_0$", or "$N_1$ is an parent of $N_2$". For now, I've been highjacking set notation for use in formulas, ...
1
vote
1answer
57 views
Show that Minimum Spanning Tree is unique
Show that MST is unique in case the edge weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$.
I thought that the proof can be done for example by contradiction,
saying that we ...
1
vote
1answer
71 views
How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?
Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
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.
0
votes
1answer
37 views
Identify Type of Recursive Sequence?
I would love to learn techniques for solving the following, but I can't seem to identify this type of sequence: let $N > 0$ and let $k$ be an arbitrary positive integer between $0$ and $N-1$ ...
0
votes
1answer
30 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
0answers
42 views
Nilpotency of the adjacency matrix of a directed tree network
Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and ...
1
vote
1answer
49 views
Proofs involving subtrees of a tree
I have found some claims about trees in my graph theory text, and I am wondering if corresponding proofs can be found, as I cannot find any online or in another text.
First,
If $T_1$ and $T_2$ ...
0
votes
1answer
46 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 ...
1
vote
1answer
32 views
What is the length of the Minimum Spanning Tree
What is the length of the Minimum Spanning Tree for the following weighted graph?
Solution. The length of any minimum spanning tree for this graph (and there is more
than one) is 60.
The graph and ...
5
votes
1answer
148 views
Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:
I ...
3
votes
1answer
26 views
Prong Corollary, $G$ has a subgraph isomorphic to $T$
There is a corollary in Diestel textbook Graph Theory.
Corollary 1.5.4. if $T$ is a tree and $G$ is any graph with $\delta(G) \geq |T|-1$, then $T \subseteq G$, i.e. $G$ has a subgraph isomorphic ...
1
vote
2answers
132 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 ...
2
votes
0answers
198 views
Algorithm for generating homeomorphically irreducible trees of size n
In this video they talk about generating all the homeomorphically irreducible trees of size 10.
I was wondering if there is a generating algorithm for generating all the homeomorphically irreducible ...
3
votes
1answer
47 views
What's the rank of this well founded relation?
Definition A tree is an ordered list of trees. (N.B these are finite objects and there is a very simple computable bijection of them with $\mathbb N$)
Examples [] and [[],[],[]] and ...
0
votes
0answers
57 views
Straight skeleton is a tree
Can anybody give me a hint on how to prove that the straight skeleton of every polygon is a tree. Here is the definition of the straight skeleton (taken from Wikipedia):
The straight skeleton of a ...
0
votes
1answer
145 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
1answer
70 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 ...
2
votes
3answers
99 views
Graphs: trees, induction proof
I was wondering if you could help me prove the following.
$G$ is a tree $\iff$ deleting any edge will disconnect it.
And a similar one:
$G$ is a tree $\iff$ adding any edge will create a cycle.
I ...
0
votes
2answers
127 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. ...
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 ...
2
votes
1answer
42 views
Number of upper sets of size $n$ in a finite tree
Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
1
vote
2answers
103 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 ...
4
votes
1answer
88 views
Is the graceful labeling conjecture still unsolved?
From the Wikipedia article on graceful labeling:
... A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that ...
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 ...
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 ...
2
votes
2answers
120 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 ...
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
242 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
...
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?
