A tree is a graph that is connected but contains no cycles.
1
vote
1answer
1k views
Maximum number of distinct binary tree possible with 4 nodes
what is the maximum number of distinct binary tree is possible with 4 nodes?
ans is 6 but how?
acc to me it should be 14
2
votes
1answer
188 views
Recursive Generating function for enumerating leaf labeled binary trees
Let be B(z) the exponential generating function for the number $b_n$ of different rooted unordered binary trees with exactly n leaves labeled only at their leaves (so the internal nodes are ...
3
votes
3answers
187 views
Cheapest spanning tree
I am trying to prove the following:
Let $x_1$ be any vertex of a weighted connected graph $G$ with $n$ vertices and let $T_1$ be the subgraph with the one vertex $v_1$ and no edges. After a tree ...
2
votes
0answers
61 views
Embedding tree metric isometrically into $\ell_\infty$
I just started (independent) learning on metric embeddings from the Fall 2003 offering of the course at CMU. I have a limited mathematical background and alas, it made me stumble at the first exercise ...
2
votes
1answer
84 views
Showing two recurrences to be identical
I am trying to prove Cayley's formula for number of labelled trees on n vertices using multinomial coefficients.
The multinomial coefficient satisfies the recurrence:
$\tbinom{n}{r_1,\cdots ...
3
votes
0answers
84 views
Number of spanning arborescences
I am trying to prove the following result from my book:
Let $G$ be a directed graph with vertices $x_1,x_2,\cdots x_n$ for which a directed Eulerian circuit exists. A spanning arborescence with root ...
0
votes
2answers
492 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, ...
10
votes
2answers
546 views
Partition a binary tree by removing a single edge
The question is :
B-3 Bisecting trees
Many divide-and-conquer algorithms that operate on graphs require that the graph
be bisected into two nearly equal-sized subgraphs, which are induced by a ...
2
votes
1answer
176 views
Proof about trees
Show that in any tree there exists a node such that, if we remove this
node and the edges adjacent to it, we will obtain trees which have at
most n/2 nodes (the removed node is not counted ...
1
vote
1answer
187 views
Depth distribution of normalized decision trees?
Lets work with the following inductive definition of a decision tree:
1) $\bot$, $\top$ are decision trees.
2) If $x_i$ is a variable and $T_0$, $T_1$ are decision
trees then $(\lnot x_i \land T_0) ...
3
votes
1answer
164 views
On the number of caterpillars
A caterpillar is a tree with the property that if all the leafs are removed then what remains is a path. Could you help me to prove that there are $2^{n-4}+2^{\lfloor n/2\rfloor-2}$ caterpillar on $n$ ...
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 ...
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 ...
2
votes
2answers
313 views
Number of undirected trees with labeled edges, one repeating
I need to find the number of undirected trees on $n$ vertices such that the edges (and not the vertices) are labeled and exactly one label appears twice (i.e. there are $n-2$ possible labels and they ...
4
votes
1answer
118 views
An identity on the number of trees
Let $T_n$ be the number of labelled trees on $n$ vertices, then
$$ T_n=\sum_kk\binom{n-2}{k-1}T_kT_{n-k} \tag{1}$$
Using this question, I was able to prove that
$$ T_n= \frac{n}{2} \ ...
0
votes
1answer
257 views
Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves
What is an example of a direct bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves?
1
vote
2answers
97 views
A bijection between ordered trees and ballot lists
Could you help me to prove that there is a bijection between ordered trees with $n+1$ leaves and ballot lists with $n$ A's and $n$ B's?
A ballot list is a sequence of A's and B's such that all ...
3
votes
1answer
351 views
Spanning Trees of the Complete Graph Avoiding a Given Tree
EDIT: I think everyone understood, but I never explicitly stated that I am looking at labeled spanning trees.
Let $T$ be a tree contained in $K_n$ (the complete graph on $n$ vertices). How can one ...
3
votes
4answers
865 views
Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed
Update:
This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution.
http://www.youtube.com/watch?v=VbSwwos4R2E
Hi, I ...
4
votes
0answers
87 views
Identify this combinatorial construction
I am no combinateur, but I stumbled across the following construction when studying an operad arising from information theory (actually it's a special algebra of an A$_\infty$-operad). It looked ...
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 ...
2
votes
2answers
298 views
Number of inner nodes in relation to the leaf number N
I am aware that if there is a bifurcating tree with N leaves, then there are (N-1) internal nodes (branching points) with a single root node. How is this relationship proved?
Best,
0
votes
0answers
112 views
Terminology, mapping a tree to a tree
I have stumbled upon a problem, unfortunately I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
3
votes
0answers
95 views
Are almost all rooted trees asymmetric?
It's well known that almost all graphs are asymmetric (have trivial automorphism group) and that almost all free trees are symmetric.
By which argument do I see whether almost all rooted trees are ...
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?
4
votes
1answer
309 views
Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$
I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$.
I'm now searching for an intuitive, or geometric, or visual proof of ...
2
votes
1answer
212 views
Fast question about minimum spanning trees
If any edge from a given spanning tree T0 is contained in some minimum spanning tree T*, does this imply that T0 is also a minimum spanning tree ?
Right now, I'm trying to draw on paper some graphs ...
