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
0answers
17 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
0answers
18 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
1answer
43 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
13 views

Terminology for excluded nodes

Given the following tree: A / \ / \ B C / \ \ / \ \ D E F / \ / \ G H Regarding node ...
0
votes
0answers
40 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. ...
0
votes
0answers
25 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
19 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
47 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
25 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
39 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: ...
1
vote
1answer
85 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 ...
3
votes
1answer
87 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. ...
0
votes
0answers
23 views

How many nodes in a K-ary tree with L leaf nodes

Assuming that we have a k-ary tree with L leaf nodes, can the average number of nodes in the tree be calculated if we were to know the average number of children for each node? If not, what other ...
0
votes
1answer
56 views

Dijkstra’s algorithm / path is this done correctly?

im doing this assignment and it seems as if my teacher has made a mistake. according to me in order to find the minimum spanning treee from a-z , you start from a and then go to : a,f,d,c,b,e,z,g ...
0
votes
1answer
57 views

Dijkstra's algorithm, am I or the teacher mistaken?

Imagine that Dijkstra’s algorithm has been used to show the length of the shortest path from $a$ to $g$ in the graph in figure 1. Which of the following vertices is added first to the set $S$? It's ...
0
votes
0answers
58 views

minimum number of leaves in a perfect binary tree

I'm trying to prove that the number of leaves in a perfect binary tree is at least H+1 where H is the height of the tree. This is what I've done up til now: No of leaves at height $H = 2^H$ Base ...
0
votes
2answers
125 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: ...
1
vote
0answers
39 views

Completeness in M-ary trees where the value of M is variable.

Definitions of complete trees are typically limited to some specific kind of tree, often an $m$-ary tree, where the number of children each internal node must have is a positive integer $m$. Consider ...
1
vote
2answers
443 views

Number of binary search trees on $n$ nodes of height up to $h$

How can I find the number of binary search trees up to a given height $h$, not including BSTs with height greater than $h$ for a given set of unique numbers $\{1, 2, 3, \ldots, n\}$? For example, if ...
0
votes
1answer
43 views

Binary tree node value by level

How can I calculate the value of given node level, for example: (let's use this image I found on Google Images and invert the level: starting at bottom 0..1..2..3..4) Knowing that each node pays ...
0
votes
1answer
45 views

$ G=(V,E_1 \cup E_2) $ is a triangle free graph, where $ G_1=(V,E_1) $ is planar and $ G_2 = (V, E_2)$ is a tree. Prove that: $ \chi (G) < 7 $

can anyone help with this, any direction could be helpfull? I've tried using the fact that $ G_1 $ satisfies that it's planar and is triangle free because G is. So we should have $|E_1| \leq 2|V|-4 $ ...
2
votes
0answers
53 views

Generating all coprime pairs

The Wikipedia article on coprime integers has a brief section on generating all coprime pairs. All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint ...
1
vote
1answer
50 views

A tree has a root, leaves, and what?

The root of a tree is special, in that it has no parents. The leaves are special in that they have no children. The other nodes each have exactly one parent and more than zero children. Is there a ...
2
votes
2answers
218 views

How to find the number of all the possible ordered trees with n edges and k leaves?

We know that a tree with n edges have n+1 nodes.So if $|B_{n+1}|$ is the number of all possible ordered trees with n+1 nodes then its true that $C_{n+1} = |B_{n+1}|$ where $C$ is the Catalan ...
6
votes
1answer
64 views

Let $T$ be the set of full binary trees. In what way $T^7 \cong T$?

I was reading the slides of a talk by Tom Leinster. I have trouble understanding the last line of page 17 (pages 1-15 are irrelevant and can be skipped). Could someone please explain it to me? If I ...
0
votes
4answers
67 views

sum of heights in perfect binary tree

the question: what is the sum of heights of the vertices of a perfect binary tree (n vertices, the height of a leaf is 0)? explain shortly. a. $\theta(logn) $ b. $\theta(nlogn) $ c. $\theta(n) $ d. ...
0
votes
1answer
55 views

how to define this directed graph satisfying these conditions?

I want to know the definition of a type of directed graph that satisfies these conditions: 1) this is a directed graph; 2) there is a directed spanning tree in this graph; 3) there is not any ...
2
votes
0answers
43 views

Possible Paths in Pipe Network

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit i have to ...
0
votes
1answer
17 views

Vertices of RSMT

I've been looking into RSMT trees recently. For those unfamiliar with them, it's the smallest possible tree that connects a set of points using only vertical and horizontal edges. One of the ...
0
votes
0answers
21 views

Minimum spanning tree of this graph

I'm trying to find a minimum spanning tree for this graph below using Krusal's and Prim's algorithm. This is what I got for each algorithm: Krusal: visited= ...
0
votes
0answers
21 views

Lower bound on the number of nodes in a subtree of a red black tree

Can someone give a direct proof (NOT an inductive proof) showing that a subtree rooted at any node $x$ in a red black tree has at least $2^{bh(x)}-1$ internal nodes ? $bh(x)$ means the black height ...
0
votes
0answers
27 views

Notation for “set of leaves of a tree” when leaves are “repeated”

Having this tree, I need to specify the number of leaves (6) and the set of leaves. Question: is this the correct notation to specify the set of leaves when there are some repeated or is there ...
1
vote
1answer
42 views

how to define a “directed spanning tree”?

In all my books and articles about "graph theory", I didn't find the definition of "directed spanning tree". Could you please give this definition and the reference? How to judge if a directed graph ...
1
vote
0answers
45 views

How to mathematically judge if there is a spanning tree in a graph?

Given a graph $G=(V,E,A)$ where $V$ is the set of the vertices, and $E$ is the set of sides, and $A$ is the adjacency matrix of dimension $n\times n$. $G$ is undirected or directed. We define the ...
1
vote
0answers
21 views

All possible depth first spanning trees of a directed graph.

I am looking for an algorithm that generates all possible depth first spanning trees of a directed graph that has a known root.
0
votes
1answer
44 views

How to find right child in a pyramid number?

A pyramid number: 0 1 2 3 4 5 6 7 8 9 So is there any equation like: ...
3
votes
1answer
43 views

How many ways can I connect labeled trees into a tree.

Suppose I have the labeled trees $T_{1}, \ldots, T_{n}$ with $b_{1}, \ldots, b_{n}$ vertices respectively. I would like to know how many ways I can compose a tree from these trees by using all trees? ...
0
votes
0answers
56 views

Standard notation for the set of children of a node in a rooted tree

In graph theory, given a rooted tree $T$ and a node $a \in V(T)$, is there a standard way to refer to the set of all children of $a$? I have seen $CHILDREN_T(a)$ being used, but this seem quite clumsy ...
0
votes
0answers
125 views

Minimum spanning tree for a weighted square grid

I have a particular grid with weighted edges connecting each vertex: From this I'm looking for an easy method to obtain a Minimum Spanning Tree. I can easily check columns or rows and remove all ...
1
vote
2answers
115 views

How many trees does a forest with n vertices and m edges contain?

Concerning trees in graph theory: How many trees does a forest with $n$ vertices and $m$ edges contain? This has to do with combinatorics apparently but I'm struggling with these assignments ...
0
votes
0answers
51 views

constructing directed graphs using leaves of a non-isomorphic directed binary trees

I have a simple binary tree with 4 leaves: a / \ b c / \ / \ 0 1 2 3 I want to find an algorithm that constructs all directed graphs using the tree ...
1
vote
1answer
95 views

Maximum nodes in AVL tree with distinct positive integers

Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ? We ...
1
vote
0answers
40 views

Is there a polynomial time algorithm for Poly-trees (oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
1
vote
3answers
88 views

How to find the number of spanning trees for a cube?

Can you tell me a way of finding the total number of spanning trees in a $Q_d$ undirected labelled graph for $d = 3$. I know that the answer is 384, but the way (I know there are many.) of finding ...
1
vote
1answer
50 views

How to determine lexicographically the smallest Prüfer-Code of a spanning tree?

First, lexicographically the smallest means e.g. 112 < 121 and 121 < 211. EDIT: Then how to determine the minimal Prüfer-Code of a spanning tree from the given graph: Should I first find ...
1
vote
3answers
37 views

Proving the number of leaves is larger by at least two than the number of vertices with a degree of at least 3

Prove that in every tree, the number of leaves is larger by at least two than the number of vertices with a degree of at least 3. Trying induction, I get something that is too short to be right, ...
0
votes
1answer
27 views

Proving that the number of appearances of $i$ in $F(T)$ (Prufer sequence) is $d_i-1$

Let $T$ be a labeled tree on the set of vertices $\{1,...,n\}$, and its sequence of degrees is $d_1,...,d_n$. Prove that for all $1\le i \le n$ the number of appearances in $F(T)$ (Prufer sequence) ...
1
vote
1answer
34 views

Prove that in the union of two trees there exist a vertex with degree of at most $3$

Let $T_1=(V, E_1), T_2=(V,E_2)$ be trees on the same set of vertices, and let $G=(V,E_1 \cup E_2)$ be the graph resulting from the union of the two trees. Prove that there exist a vertex with ...