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
29 views

Balance factor changes after local rotations in AVL tree

I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation: ...
0
votes
1answer
55 views

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree.

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree. I think i've done this right but i'm not sure.
5
votes
5answers
45k views

The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.

I am confused with this statement The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$. How come this is true. Lets say I have the following tree ...
0
votes
2answers
80 views

Tree. Number of nodes and children

Suppose a given tree $T$ has $n_1$ nodes that have $1$ child, $n_2$ nodes that have $2$ children, . . . , $n_m$ nodes that have $m$ children and no node has more than $m$ children, how many nodes have ...
2
votes
1answer
343 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 \...
1
vote
1answer
29 views

Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
0
votes
1answer
19 views

Remove the root from a binomial tree

I have a binomial tree with height k. How do I proof that when I remove the root, the result will be k new binomial trees, each with with a height from 0 to k-1. Thanks in advance.
1
vote
1answer
125 views

Spanning trees of ladder graphs…

a. Draw the 1-ladder, 2-ladder, and 3-ladder graphs, and calculate the number of spanning trees for each. - I have completed this part and wanted to confirm that these numbers look accurate, I feel ...
2
votes
0answers
27 views

Maximum number of subtree in a spanning tree

Is it possible to determine the theoretical maximum of number of subtree that can be extracted from a spanning tree? Some context (I don't know whether this is useful): I build the spanning tree by ...
0
votes
0answers
47 views

Bottleneck distances for the Steiner problem in graphs

I have been reading the paper "Preprocessing the Steiner Problem in Graphs" by Duin (http://link.springer.com/chapter/10.1007%2F978-1-4757-3171-2_10) and I am having a bit of trouble wrapping my head ...
1
vote
2answers
71 views

Number of reachable vertices in a tree

Given a tree $T$ with infinite nodes. Each node of the tree has exactly $C$ children. I need to figure out that, starting from a node at distance $h$ from root, how many distinct vertices can be ...
0
votes
0answers
8 views

Tree decomposition (Citation needed)

Recently, I read the statement "Fix $k\geq 1$, Any tree with at least $k$ edges may be decomposed as a union of edge-disjoint subtrees, each having between $k$ and $3k$ edges" Now I was wondering ...
1
vote
2answers
34 views

Find all possible topological-sortings of graph G

A topological ordering of G is an ordering of the nodes as $v_1,v_2,...,v_n$ so that all edges point "forward": for every edge $(v_i,v_j)$, we have $i<j$. Moreover, the first node in a ...
1
vote
1answer
40 views

How can I draw a tree to represent combinations?

I understand how to systematically draw a tree for permutations. How do you do this for combinations? In my book, I don't see a system to avoid repetitions. I'd like to draw a tree of 5C3 if possible. ...
0
votes
2answers
100 views

Trees with no vertex of degree 2 have more leaves than internal nodes

There is a question asked by portal about Tree having no vertex of degree 2 has more leaves than internal nodes so we want to prove this claim by induction and an answer from Micheal Biro suggested ...
2
votes
1answer
94 views

What is a “linear chain” in Graph Theory?

What is a linear chain in the context of graphs and trees? For example: a topological sort forms a linear chain What does a linear chain mean in the example above? Another example from ...
1
vote
1answer
37 views

Circuits and Trees

Given a graph G, can it be split into 2 sets of graphs($ G_1, \; G_2 $) such that, $G_1$ consists only trees and $G_2$ consists only circuits ? In other words: Is it possible to construct any graph ...
3
votes
1answer
267 views

Tree having no vertex of degree 2 has more leaves than internal nodes

If $T$ is a tree having no vertex of degree 2, then $T$ has more leaves than internal nodes. Prove this claim by a) induction, b) by considering the average degree and using the handshaking lemma. I ...
0
votes
1answer
62 views

Polynomial time algorithm for finding the chromatic sum of a tree.

As the title goes, a polynomial time algorithm for finding the chromatic sum of a tree is required. NOTE: Finding the chromatic sum of a graph is also called the sum coloring problem - The sum ...
0
votes
1answer
29 views

Intersection of all possible spanning trees of a connected, simple graph.

Is the intersection of all possible spanning trees of a simple, connected graph $G$ equal to the graph $(V_{G}, \varnothing)$? I'm not sure if this is a trivial question or not. Although I'm going to ...
4
votes
0answers
69 views

Why is the intersection of countably many homogeneously Suslin subsets of $\,^{\omega} \omega$ homogeneously Suslin?

I found this assertion in these notes: The derived model theorem (Steel) right in the beginning on page 3, together with the remark that this is 'not too hard to show'. Unfortunately, I'm ...
0
votes
1answer
126 views

Tree with no nodes of degree 2: prove that # leaves ># internal nodes using average degree and handshake lemma

Im really struggling to formalise my thoughts on this one. Basically I understand that if we would allow nodes with degree 2, then we could chain together infinitely many nodes to always produce ...
2
votes
1answer
29 views

Different trees of weighted graph , please check whether my explanation is correct $?$

Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then ...
1
vote
0answers
47 views

Complexity analysis of alpha beta pruning of a full tree

I am trying to understand the derivation of a time complexity for an alpha-beta pruning algorithm but up till now have not found any reasonable recourse. Many recourses claim that if you take a full ...
1
vote
0answers
21 views

Yet another curious convolution

Some time ago, I found the following algorithmic problema: Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors. Given that the ...
0
votes
0answers
86 views

For a k-ary tree with height h, the upper bound for the maximum number of leaves is $k^h$

i want to prove For a k-ary tree with height h, the upper bound for the maximum number of leaves is $k^h$. (assume the complete k-ary tree is a tree that is complete in all levels including the ...
0
votes
0answers
21 views

directed trees versus singly-connected directed graphs

According to wikipedia, a singly connected directed graph (a.k.a. Polytree) is a Directed Acyclic Graph whose underling undirected graph is a tree. How is this different from directed trees (trees ...
1
vote
0answers
42 views

Is there a name for this particular kind of tree graph?

I've recently encountered a problem which heavily involves analysis of structures analogous to weighted trees with no nodes of degree two (such a node along with its adjacent edges would be ...
1
vote
0answers
32 views

Binary Minimum Spanning Tree (from complete graph)

Given a weighted complete graph (or more exactly, a matrix of pairwise metric distances between vertices), I need to find a good approximation of the binary spanning tree of lowest total cost. There ...
3
votes
2answers
205 views

Graph Theory: Trees, leaves and cycles

So, a vertex is called a leaf if it connected to only one edge. a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that G = (V, E) is a graph, V ≠ Ø, where every vertex ...
0
votes
1answer
82 views

Counting spanning trees and hamiltonian paths

Assumption : For any connected graph, every hamiltonian path is a spanning tree but not the other way around. If the assumption is wrong there is no need of reading any furhter. So is the assumption ...
0
votes
0answers
56 views

Extract the overall “structure” (“backbone”) of a set of vertices…

My main problem is that I am struggling to find a good graph-theoretical formulation of my problem, let alone a formal name for it (if it already exists, as I suspect it should)… Informally, given a ...
1
vote
0answers
22 views

Name of operation: changing the root of a rooted tree

What is (if any) the name of the operation of changing the root of a rooted tree? Picking a vertex which is not the root, then reorienting the edges in such a way that the vertex becomes the root?
0
votes
0answers
26 views

is the Root of a binary Tree counted as a node

I am working on this Homework questions and there's one thing I can't seem to understand. We are trying to proof using structural induction that some elements in T hold for the following statement :...
0
votes
1answer
44 views

How would one go about solving these types of problems?

I'm totally lost. All I know is it has to do with binary trees and may need to be solved using induction. Show that every 2-tree with $n$ internal nodes has $n + 1$ external nodes. Show that the ...
0
votes
0answers
19 views

Questions about this type of problem

Problem Consider the general chip-and-be-conquered recurrence relation: $T(n) = b_1T(n - 1) + b_2T(n - 2) + ... + b_kT(n - k) + f(n)$; for $n >= k$ for some constant $k >= 2$. The ...
0
votes
0answers
13 views

Terminology for excluded nodes

Given the following tree: A / \ / \ B C / \ \ / \ \ D E F / \ / \ G H Regarding node ...
0
votes
0answers
41 views

Is the following statement about tree true?

For a rooted tree T of oder n, what is the probability of that T contains a balanced tree of order 7? For example, there are total of 719 rooted trees of order 10, IF among all those 719 rooted trees, ...
0
votes
0answers
30 views

Defining a Nested Tree (set-theoretic)

I am new to the world of trees and I am trying to make a painless addition to this general definition: Let $X$ be a topological space and $\mathfrak{T}$ be a collection of sets. $(\mathfrak{T},\prec)...
0
votes
0answers
29 views

Perron vector of the distance matrix of a tree

Increasing properties of perron vector of distance matrix from the vertex corresponding to which row sum is minimum
0
votes
0answers
21 views

What is considered a unique homeomorphically irreducible tree?

Take, for example, this image that shows the possible trees of size 11 and this tree I created. Based on the 14 trees in the first image, how can I tell if mine is unique or not? Based on the shape ...
1
vote
1answer
64 views

Construction of rooted tree , please check whether my solution is correct?

Problem is A rooted tree with 12 nodes has its nodes numbered 1 to 12 in pre-order. When the tree is traversed in post-order, the nodes are visited in the order 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, ...
0
votes
0answers
31 views

Any implementation of the Roskind-Tarjan algorithm for finding the maximum number of edge-disjoint spanning trees over a graph?

I am looking for an implementation of the Roskind-Tarjan algorithm [1] for finding the maximum number of edge-disjoint spanning trees over a graph. A Matlab implementation would be great. ...
0
votes
3answers
40 views

Probability tree diagrams

Exercice : True or false Let $E$ and $F$ be two events of an experiment. $$\mathbb{P}(E| \bar{F})=1-\mathbb{P}(E| F)$$ Solution : Flase due to the Law of total probability we've: $$\mathbb{...
3
votes
1answer
111 views

Number of spanning trees in a complete split graph

A graph is a complete split graph if we can partition it into an independent vertex set and a clique, such that every vertex of the independent vertex set is adjacent to every vertex in the clique. ...
1
vote
1answer
95 views

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T .

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T . I have no idea what this question is even asking me. What ...
1
vote
1answer
66 views

How to prove that at Complete Binary Tree (CBT) at height $h$ we have $2^h$ leaves

I try to prove it by induction, please tell me if I'm right... The induction assumption - For every CBT at height $h$ there is $2^h$ leaves. The base of the induction is right (I'm writing this proof ...
8
votes
3answers
1k views

Number of spanning trees in a ladder graph

Let $L_n$ be the ladder graph formed from two $n$-vertex paths by joining corresponding vertices. For example $L_4$ is the following I have to find a recurrence $\langle t\rangle$ where $t_n$ is ...
0
votes
2answers
130 views

Sum of roots of binary search trees of height $\le H$ with $N$ nodes

Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees. For example, for $N$ = 3, $H$ = 3: ...