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

1
vote
0answers
50 views

Ordinals as Trees

I'm trying to understand countable ordinals and their tree representation. I understand that $\omega$ is the first "non branching tree" of infinite height. I also understand that the exponent of ...
1
vote
1answer
25 views

Height of the tree : $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$

Let the tree described by $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$ Can someone explains why the height is $\log_{8/5}{n}$ I don't know how to proceed
0
votes
1answer
48 views

Infinite Search Tree Probibility

I have a question on Search Trees. I have a balanced, infinite, search tree. If you check a node at level $l$, the probability of finding a solution at that node is $p^l$. Questions The first ...
0
votes
1answer
213 views

Prove through structural induction that a binary tree has an odd number of nodes

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes. I dont know how to get started with this ...
0
votes
0answers
67 views

Proof by Induction for Splay Tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay tree ...
1
vote
1answer
230 views

Graph Min Cut Problem

The idea is to give an Flow Network in which the minimum cut goes through a lot of edges. So adding one unit to each edge will change the min cut. The following figure, as a counter example, shows a ...
1
vote
1answer
63 views

$k$-connected graphs containing trees

I've encountered the following problem in the book "Graphs and Digraphs" and I'm not sure how to do it. Show that every $k$-connected graph contains any tree of order $k+1$ as a subgraph.
0
votes
0answers
29 views

mathematical formulation Minimum Cost Flow

I have a problem of minimum cost flow that can be defined as the following matrix. I want to solve it how a linear program (without using kruskal algorithms, prim etc). How can I formulate it like a ...
1
vote
1answer
92 views

Complete Binary Tree [closed]

A balanced binary tree is a full binary tree in which every leaf is either at level l or l-­1 for some positive integer l. The set of balanced binary trees is defined recursively by: Basis step: A ...
0
votes
1answer
66 views

Random Binary Search Tree, expected value of nodes with two children

In class, the professor showed that using a uniform random permutation $$ X_1,..., X_n$$ (each being i.i.d.) we can construct a Binary Search Tree by inserting the values in to the tree by their ...
0
votes
2answers
160 views

All self-complementary trees [closed]

I am looking for all self-complementary trees. Could someone accompany me in this great adventure?
0
votes
1answer
44 views

Calculating the average degree/valency of vertices

If I were to let T be a tree with n vertices, what would be the average degree/valency of the vertices in T? How would I go about calculating this?
2
votes
1answer
173 views

Proving that the height of a 2-3 tree is between $\log_3 N$ and $\lg N$

I am stuck on the problem of trying to prove the upper and lower bounds of a 2-3 tree. I think the most natural recourse is to use induction. However, my instructor told me that this was unnecessary ...
0
votes
0answers
16 views

Is my understanding of realtionship spanning trees and the cycle graphs correct

Any cycle graph C$x$ for example C200 would have only one spanning tree as a spanning tree would be the entire graph minus one edge. And the amount of ways can you remove just one edge from C200 ...
-1
votes
1answer
89 views

Finding a minimum weight spanning tree? [duplicate]

Letting W be the weighted graph created by taking a complete graph K5 on five vertices 1, 2, 3, 4, 5 with the weight of each edge {x,y} given by ({x,y})=x+y, How would I find a minimum weight ...
1
vote
0answers
27 views

Proof for the number of leaves for any Binary Search Tree

A property for binary trees is that the number of leaves is the number of full nodes plus 1, in other words, $L = F + 1$ where $L$ is the number of leaves and $F$ is the number of full nodes. What ...
0
votes
1answer
65 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
-1
votes
1answer
218 views

Question about trees, Let T be a tree with n vertices

Are my answers correct to these 3 questions? Let T be a tree with n vertices. 1) What is the average degree/valency of the vertices in T? Average Degree of of ...
0
votes
1answer
140 views

How many spanning trees does the cycle graph C2014 have?

How many spanning trees does the cycle graph $C_{2014}$ have? How do I create a bipartite graph and use it to solve this problem?
1
vote
1answer
98 views

Postorder and Preorder traversal on a Binary tree

For the tree below, list the labels of the nodes of the tree according to the pre-ordering algorithm, and then re-list them according to the post-ordering algorithm. ...
1
vote
1answer
42 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
6
votes
1answer
765 views

Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: ...
0
votes
1answer
48 views

Spanning tree with unique paths.

Let $G$ be a connected graph and let $r∈V(G)$. Prove that $G$ has a spanning tree $T$ such that for every edge of $G$ with ends $u$ and $v$, either $u$ belongs to the unique path in $T$ with ends $v$ ...
4
votes
1answer
37 views

Expected number of subtree removal in a tree.

I was solving this problem. In a gist the problem is as follows: You are given a rooted tree. On each step you choose a node randomly and remove the subtree rooted by that node and the node ...
0
votes
1answer
47 views

Normalization of data in decision tree

After reading through a few references, I have come to know that for machine learning in general, it is necessary to normalize features so that no features are arbitrarily large ($centering$) and all ...
0
votes
1answer
46 views

The intersection of $k$ subtrees of a tree $T$ is nonempty.

Let $T_1$, $T_2$, . . . , $T_k$ be subtrees of a tree such that any two of them have a vertex in common. Prove that they all have a vertex in common. Any hints/solutions are greatly appreciated. I am ...
0
votes
1answer
31 views

Find the node that we will reach with a given path on a graph (complete binary tree)

This question is regarding a special case of graph i.e. complete binary tree Consider the following tree :- ...
1
vote
2answers
357 views

Prove that if all edge-costs are different, then there is only one cheapest tree.

Prove that if all edge-costs are different, then there is only one cheapest tree (minimum spanning tree). (Use contradiction and make sure to keep track of the costs of the different trees involved.) ...
1
vote
0answers
25 views

AVL, keys where rotations are not required

Suppose the keys {1,2,3.....,n} are inserted into n empty AVL tree in sequence 1,2,3.....,n. Find the key values(1,2...n these are the keys) where rotation(rotations to balance the tree structure) is ...
0
votes
1answer
61 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
0
votes
1answer
155 views

Visiting Node in BFS and DFS in the same order [closed]

if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false? a) G can be a ...
2
votes
1answer
66 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
0
votes
1answer
36 views

A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$. Any solutions or hints ...
0
votes
0answers
27 views

Pascal's Identity and Trees

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
3
votes
1answer
45 views

Automorphism of Tree

Let $\sigma$ and $\theta$ be two automorphisms of tree $X$. I want to show that min$_{v\in V(X)}d(v,\sigma(v))=$min$_{v\in V(X)}d(\theta^{-1}\sigma\theta(v),v)$. I know every automorphism of tree is ...
1
vote
1answer
69 views

Iterations of Pascal's Identity

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
0
votes
1answer
70 views

How to understand the perfect binary tree formula?

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says: I'm ...
3
votes
0answers
48 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
2
votes
1answer
89 views

Infinite Tree Probability Question

Suppose I have 10 dollars and I'm able to make fair 50/50 bets like flipping a coin. Now suppose each bet is for 1 dollar. What is the probability that if I keep making bets until I hit 0 dollars ...
-1
votes
1answer
127 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
0
votes
3answers
66 views

How to write a summation function that counts the number of nodes in a tree?

I come from a programming background and am interested in learning how to represent some things as simple equations, as an entry into thinking mathematically. How do you represent a tree structure as ...
2
votes
1answer
84 views

Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
1
vote
0answers
33 views

Tree of arity n: How to call a vertex that has only k (k<n) children?

What is the correct adjective for a vertex in an n-ary tree that has only k children (k < n)? I was thinking of something like "unsaturated", but I don't know if that is the correct word for this. ...
0
votes
1answer
48 views

Number of distinct Binary tree formed with respect to height h

How many types of distinct Binary Tree can be formed with a height of h? assuming height starts from 0 when the tree has only the root. example: if the height of tree is 1 then root-leftchild ...
0
votes
1answer
26 views

Proof about spanning tress in graphs

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$. Let $f_1 \in F_1$. Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.
0
votes
0answers
25 views

How does inserting $N$ objects one at a time into an ordered AVL tree yield an efficient sorting algorithim

If we assume reblalancing an AVL tree of height n after an insertion or deletion takes $O(n)$ operations. How does inserting $N$ objects one at a time into an ordered AVL tree yield an efficient ...
0
votes
2answers
90 views

Prove that if G is a tree in which all vertices have odd degree then G has odd size.

Prove that if G is a tree in which all vertices have odd degree then G has odd size. Good night, do not know how to approach this "prove". Can you give me tips to solve it?. Please.
0
votes
1answer
99 views

Formula for number of “root” nodes in a tree where Parent shares child nodes?

If I have a tree like this: {a},{b,c},{d,e,f},{g,h,i,j} in this case we have a total of 10 nodes. Is there any equation where given "10" I can calculate how many bottom nodes there are (answer: "4" ...
1
vote
3answers
90 views

Proof of an $\iff$ statement on binary trees

Let $x$ and $y$ be two nodes of a binary tree $B$. Prove that $x$ is an ancestor of $y$ $\iff$ $x$ stands before $y$ in the pre-order traversal of $B$ and $x$ stands after $y$ in the ...
0
votes
2answers
53 views

Why is the height of a heap defined as $\lg n$?

I'm a bit confused about why the height of a heap (or a binary tree in general) is given by the floor of $\lg n$. E.g. if you have a tree with 7 nodes, you would get $h = 0$ instead of $h = 2$. Isn't ...