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

0
votes
1answer
58 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
1
vote
1answer
33 views

Number of binary trees with same X-order and Y-order

What is the number of binary trees which have the same X-order and Y-order as the given tree? Example: X-order: POSTORDER(T) = POSTORDER(TL) POSTORDER(TR) root Y-order: ANTIORDER(T) = ...
0
votes
1answer
40 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...
4
votes
2answers
256 views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
0
votes
0answers
30 views

Search L leaves smaller than node N

So in my binary $kd$-tree I have a node $N$. Now I search for the number of leafs $L$ "on the left" side of $N$ (this includes the left child branch of $N$ and all parents where the node is a right ...
0
votes
1answer
49 views

Non-Isomorph trees of a graph

Please consider this graph How many non-Isomorph trees with 4 vertex has this graph? Is there any formula that show number of non-Isomorph trees with $n$ vertices? thanks
0
votes
1answer
50 views

Depth of BFS Tree With Different Root Nodes

I need to either prove or disprove that for any node of a graph, the depth of the BFS tree using this node as root is always the same. My intuition is that this is true, but I'm having difficulty ...
2
votes
0answers
40 views

Number of nodes with even offspring

I've been working on a combinatorics assignment, and while the last few questions had clever solutions which didn't involve functional equations and the use LIFT, I fear I'm at my end. Given a ...
1
vote
1answer
30 views

Does the Prim algorith always create the same tree despite the starting node?

Does the Prim algorith always create the same tree despite the starting node? PD: sorry for my english.
0
votes
1answer
74 views

Inserting values left to right in a binary search tree

What does it mean to build a binary search tree by inserting values from left to right starting from an empty tree? The "left to right" part confuses me..I know how to build one by normally inserting ...
0
votes
2answers
1k views

How to find non-isomorphic trees?

"Draw all non-isomorphic trees with 5 vertices." I have searched the web and found many examples of the non-isomorphic trees with 5 vertices, but I can't figure out how they have come to their ...
0
votes
0answers
41 views

How to calculate branching factor of uniform tree

For a uniform tree of depth $d$ and if a particular problem has $N$ nodes then the $b*$ branching factor is $N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d$. For a depth of 5 and N = 52 how is it that the ...
0
votes
2answers
42 views

Finding an equation for a growth formula

Given a tree that has three nodes each level I want to find the formula that predicts the number of all nodes with a given tree height. I fitted the data into Numbers with an exponential function ...
0
votes
0answers
99 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
2
votes
1answer
227 views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
2
votes
1answer
125 views

spanning trees of an edge transitive graph

Let $G$ be an edge transitive graph. Let $t(G)$ be the number f spanning trees on $G$. Show that each edge lies in exactly $\tfrac{(n-1)t(G)}{m}$ spanning trees. Where $|V(G)|=n$ and $|E(G)=m$. ...
1
vote
2answers
1k views

Can Prims and Kruskals algorithm yield different min spanning tree?

In this problem I am trying to find the min weight using the Prims and Kruskals and list the edges in the order they are chosen. For Prims I am getting order ...
0
votes
2answers
327 views

creating a Binary tree based on a prefix expression

I want to find the value of a the prefix expression -/+8,10,2*3,2 and build its binary tree I am trying to learn this for a math course, but have absolutely no clue ...
0
votes
0answers
186 views

D ary tree node math

A d-ary tree is a rooted tree in which each node has at most d children (c) Suppose the tree has n nodes. What is the minimum the depth could possibly be, in terms of n and d? You can leave your ...
1
vote
4answers
829 views

How many labeled trees exist on n vertices with exactly 3 vertices of degree 1?

My combinatorics class is covering spanning trees right now and one of the questions being asked is "What is the number of labeled trees on n vertices with exactly $3$ vertices of degree $1$?" I've ...
0
votes
1answer
59 views

Counting the number of trees on $[n]$

Let $T_{n}$ be the number of trees on $[n]$. Explain the identity below in terms of $T_{n}$ and prove it. $2(n-1)n^{n-2}=\sum_{k=1}^{n-1}\binom{n}{k}k^{k-1}(n-k)^{n-k-1}.$ So far I've got that ...
0
votes
1answer
25 views

Question Concerning Family of Trees

I have the following problem where I am asked to construct a family of trees (one for each $n$) that have exactly 2 leaves. I am having difficulty with this problem mainly because I cannot find a ...
1
vote
0answers
34 views

automorphism of a rooted tree

Nowadays i'm working with tree automorphisms. I couldn't find information about rooted tree automorphism concerning the root. Does an automorphism of a rooted tree fix the root or not? Logically it ...
1
vote
2answers
68 views

In a tree, is there always a sink where every longest path ends in?

Let $T$ be an undirected tree. Can we always find a leaf vertex $s$ such that every longest path of $T$ has its other endpoint in $s$? It's easy to see that every longest path passes through the ...
1
vote
2answers
93 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
0
votes
0answers
16 views

Measuring values at nodes of two independent but now connected trees

I am not sure if this the right forum for this question and I hope I am providing enough details on what I want to accomplish. I have an application that has multiple trees - Tree 1 - is categories/ ...
2
votes
1answer
70 views

Given an $n$ level tree with $b$ branches at each node, how many unique paths are there from the root to the leaves?

I have a tree where, at each node, it splits into $b$ branches for a total number of $n$ levels. I enumerate the paths from the root to the leaf nodes. For example, if $n = b = 2$ then I have the ...
1
vote
1answer
38 views

Connection Trees and Partition

In our lecture we just had a short excursion into the tree-world. But the professor mentioned some connection between Ramsey and König's Infinity Lemma (If $T$ is a tree of hight $\omega$ with all ...
3
votes
2answers
156 views

König's Infinity Lemma and Aronszajn Trees

I am working through the notes of my Set Theory lecture. There my professor wrote: 'Is there an uncountable $\kappa$ such that König's Infinity Lemma holds for $\kappa$? There are models where ...
2
votes
1answer
67 views

questions about binary search tree

Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees. How is it prove ...
0
votes
4answers
2k views

How many edges does an undirected tree with n nodes have?

The following options: a) $n$ b) $n + 1$ c) $n - 1$ d) $n(n - 1)$ e) $(n + 1)(n - 1)$ f) $\frac{n(n - 1)}2$ g) $\lceil \log_2n \rceil$
1
vote
0answers
113 views

Generating Function for edge-rooted labelled trees

Let $T_v(z)$ be the (exponential) generating function for vertex-rooted (non-plane) trees. Im trying to construct the generating function $T_e(z)$ for edge-rooted trees from this. I know the ...
0
votes
1answer
407 views

How many vertices does a complete binary tree of height 1 have?

How many vertices does a complete binary tree of height 1 has? Height 2? Height d? Any hints on how to start to tackle these set of questions?
0
votes
0answers
60 views

Linear constraints on distance (hop) matrix of a tree

I have an optimization problem where I want the constraints to be linear. The variables are elements of an $N\times N$ matrix D. The elements of D, ie $D(i,j)$ are integers and represent the number of ...
1
vote
0answers
94 views

Binary Tree and Geometric Distribution

I have the following algorithm for "constructing" a binary tree: A probability $p_g$ for elongation, i.e. adding an edge A probability $p_b$ for branching, i.e. adding to a node two "child" edges ...
0
votes
0answers
58 views

Binary Index tree with key value pairs

Extend the data structure of the previous problem to support insertions and deletions. Each element now has both a key and a value. An element is accessed by its key. The addition operation is applied ...
1
vote
2answers
138 views

Draw Graph from distance to other nodes

I have a matrix that shows the distance from a node to another node: A B C D E A 0 2 4 3 1 B 2 0 2 1 3 C 4 2 0 2 1 D 3 1 2 0 2 E 1 3 1 2 0 To clearify: The 2 ...
1
vote
0answers
168 views

Binary Tree and Overhead fraction Caluculation

Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes: 2) Only leaf nodes store data; internal nodes store two child ...
0
votes
1answer
74 views

Unique solution for a given pre- and post-order of a rooted tree

Decide the picture of a rooted tree with pre-order $a,b,c,d,e,f,g,h$ and post-order $d,e,f,g,h,c,b,a$. Show that there always is a unique solution for a given pre- and post-order of a rooted tree. My ...
3
votes
2answers
76 views

Number of undirected trees

Given n numbered vertices I want to know the number of different trees that can be created with them. I know that cayley's theorem says it's $n^{n-2}$, but why can't it also be: ...
2
votes
1answer
586 views

Number of distinct path in a graph with $n$ vertices

Let $T = (V , E)$ be a tree with $|V | = n\geqslant 2$. How many distinct paths are there (as sub graphs) in $T$? I already have the answer to this question as $(n/2)$. The problem that I'm having is ...
6
votes
2answers
127 views

What is the average weight of a minimal spanning tree of $n$ randomly selected points in the unit cube?

Suppose we pick $n$ random points in the unit cube in $\mathbb{R}_3$, $p_1=\left(x_1,y_1,z_1\right),$ $p_2=\left(x_2,y_2,z_2\right),$ etc. (So, $x_i,y_i,z_i$ are $3n$ uniformly distributed random ...
2
votes
1answer
48 views

Is there a tree $T$ such that $\text{diam}(T) \geq k$, where $k$ is the number of vertices with degree less than 3?

Let $T$ be an undirected tree, let $d$ be the diameter of $T$, and let $s$ be the number of vertices in $T$ with degree less than 3. Recall the diameter of a graph is the length of the longest ...
0
votes
1answer
50 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
1answer
54 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 ...
6
votes
4answers
186 views

Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

This question appears also in http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this ...
0
votes
1answer
88 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 ...
1
vote
2answers
488 views

Gallery of unlabelled trees with n vertices

Can anyone point me to a gallery (printed or online) of unlabelled trees, sorted according to their order (i.e., number of vertices)? That is, for each order n in oeis.org/A000055 (up to maybe n=11 ...
0
votes
1answer
53 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. And that tree can't have depth 2 or 1.
3
votes
2answers
162 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$ ...