Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [trees]

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.

Trees are an important topic in graph theory. A tree is a connected graph with no cycles. They are of enormous practical importance in applied mathematics.

For example, in a connected weighted graph, it is interesting to know how to find a subgraph which is a tree and which maximizes or minimizes the total weight of the subgraph. A subgraph of a graph $G$ which is a tree that touches all nodes of $G$ is called a spanning tree for $G$.

For instance, imagine a network of electrical systems, such as a telephone system, between nodes. Suppose that signals can travel through any path in the network, passing through intervening nodes to get to the final destination. The amount of wiring can be reduced by deleting portions of cycles in the graph of the network. The graph can eventually be reduced to a tree, and all nodes remain connected and accessible through the network.

Dijkstra's algorithm is an effective way to determine the lowest-weight spanning tree for a given connected graph.

2015 questions
1
vote
1 answer

Why is this induction wrong on Trees?

I just learned it in class that when using induction to prove a tree problem, we should always remove a vertex instead of adding one in induction. Why is that? For example, prove that tree with $n$ vertices has $n-1$ edges. Why would it be wrong to…
CJ Lin
  • 13
1
vote
0 answers

Is there a specific way to handle equations to convert it into such a form that it gives right value for any value substituted?

I was trying to find relation between total number of nodes in a complete binary tree and the leaf nodes. Note that a complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as…
Amisha Bansal
  • 11
1
vote
1 answer

Number of rooted trees

Compute the number $t_n$ of rooted trees with n nodes described by the following equation: We know that we cannot construct such tree for all $n$ (where $n$ is natural number). For example, we can construct trees for $n's$ based on formula…
glion14
  • 63
1
vote
0 answers

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 most $\frac{d}{d+1} \vert V \vert+1$ I have tried…
user46317
  • 155
  • 4
1
vote
0 answers

Labelled Trees on $n$ vertices

Let f : [n] → [n] be a function, and let Tf be a labelled tree on n vertices, constructed from f. Suppose that T contains a vertex of degree at least k. Show that f takes at most n-k+2 different values. I don't really know how to start here. Thanks.
TedMosby
  • 503
1
vote
1 answer

Binary Trees: relationship between height and number of children

Lets take a Binary Tree with n nodes (and n-1 edges). If h is the height of the tree, then hϵ[log2(n), n] depending if the tree is balanced or not. The minimum height is reached if the tree is "completed", i.e. the nodes either have two children or…
Asghabard
  • 53
1
vote
1 answer

Number of distinct tours in a binary tree?

We have a binary tree T with N leaves (each leaf corresponds to a city ID) and N-1 internal nodes. Every internal node has exactly two children. We have a tour when we visit all of the cities and close the tour by returning to the point at which we…
user3487243
  • 61
1
vote
1 answer

Find number of possible root values for an n nodes avl tree

Be an avl tree with 20 nodes with values from 1 to 20. What are the possible values for the root node. ? I was thinking to find minimum and maximum height but I don't know what to do after that. Does anybody have an idea? UPDATE: THe problem is to…
MSD561
  • 113
1
vote
0 answers

KD-Tree implementation with lat/lon coordinates

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct results (same nearest neighbor) if I use…
dimitris93
  • 155
1
vote
1 answer

Tree question proving

Let $T_1$ be a tree of height $h$ such that the root has one child, and the branching factor at each level is one more than the branching factor at the previous level. Thus, the root has one child, that child has two children, each of those children…
John
  • 69
1
vote
3 answers

Finding element in binary min-heap

I am trying to answer two questions. Can some one check my answer and let me know if its correct or not? Question 1: Which locations in a binary min-heap of n elements could possibly contain the third-smallest element? Answer 1: So I know this is a…
user292758
  • 11
1
vote
1 answer

No. of Comparisons to find maximum in $n$ Numbers

Given $n$ numbers, we want to find the maximum. In order to find the maximum in a minimal amount of comparisons, we define a binary tree s.t. we compare $n'_1=\max(n_1,n_2)$, $n'_2=\max(n_3,n_4)$; $n''_1=\max(n'_1,n'_2)$ and so on. How many maximum…
a1337q
  • 379
1
vote
1 answer

Prove that in every tree, any two paths with maximum length have a node in common.

Prove that in every tree, any two paths with maximum length have a node in common. This is not true if we consider two maximal (i.e. non-extendable) paths. What does this even mean?
Jean
  • 151
  • 1
  • 2
  • 8
1
vote
3 answers

Traversing through a binary tree

Consider a full binary tree of n nodes numbered from 1 to n in the common top-down left-to-right manner. For the sake of the question, we can consider the following tree: 1 / \ 2 3 / \ / \ 4 5 6 7 I need to traverse from the…
zbr
  • 113
1
vote
1 answer

Get number of vertices when number of internal vertices is known ofr a full binary tree

But I can find a counter example: * / \ * * / \ / \ * * * * Here $k = 2$, but number of vertices is 6, and number of terminal vertices is 4.
qed
  • 1,083
1 2
3
4 5 6