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
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
206 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
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
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
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{...
1
vote
1answer
96 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
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. ...
0
votes
0answers
25 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
70 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
59 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
67 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
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: ...
1
vote
0answers
46 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
526 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
50 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
47 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
79 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
58 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
311 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 number....
6
votes
1answer
68 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
96 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
56 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
54 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
23 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= {(ck),(kf),(ib),(bf),(da),(ig),(ae),(di),(...
0
votes
0answers
41 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
34 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
49 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
24 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
49 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
49 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
86 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
175 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
190 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 ...
1
vote
1answer
112 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
42 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
114 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 ...