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

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. ...
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
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 ...
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
19 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 ...
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 ...
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
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
124 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
114 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
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
87 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, ...
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 ...
3
votes
0answers
123 views

Condition for a graph to have only one MST (Minimum Spanning Tree)?

Can somebody tell me if there is a condition for an edge-weighted graph to have exactly one MST? I know that it can have more minimum spanning trees, but can it have only one? Thanks in advance!
1
vote
2answers
61 views

Algorithm to cut the graph into a tree.

Given a finite connected graph $G$, I can make a finite number of cuts on the edges to obtain a tree. What is the most efficient algorithm to perform this procedure? Thanks, Vladimir
5
votes
1answer
38 views

Spare storage of a tree

I can store any undirected simple graph N vertices using $b = (N-1)N/2$ bits, by creating a mask of the edges on the upper diagonal of the adjacency matrix. For example the adjacency matrix of $K_3$ ...
1
vote
0answers
43 views

Existence of increasing pair of labeled trees in an infinite sequence

Assume labeled rooted trees with labels from a fixed set $\{1\ldots m\}$. For a tree $T$, we have: $V(T)$ the set of vertexes, $root(T)$ the root of the tree, $l_T: V(T)\rightarrow \{1\ldots m\}$ ...
0
votes
2answers
2k views

Number of nodes in binary tree given number of leaves

How would I prove that any binary tree that has n leaves has precisely $2n-1$ nodes ? Given that a binary tree is either a single node "o" or a node with the left and right subtrees contains a binary ...
4
votes
2answers
130 views

Need a counter example for cycle in a graph

Could anyone give a counter example for that theorem : A graph G has exactly one vertex of degree $1$, then it contains a cycle. I am so confused. I wonder that may I give a counter example ...
1
vote
2answers
213 views

How do you find the value of n in this example

$$n^{n-2} = 16$$ I know $n = 4$ through trial and error but how do you find $n$ in a conventional manner? I'm basically trying to solve how many nodes are in a tree that has $16$ spanning trees ...
0
votes
2answers
78 views

solve recurrence relation: comparisons to construct binary search tree with maple

I would like to solve the recurrence relation for the average number of comparisons necessary to the construction of a binary search tree. the recurrence is $$ i(n) = n - 1 + \frac{2}{n} ...
2
votes
1answer
66 views

Existence of infinite subsequence of trees with a special condition

For rooted trees, define $children(v)$ as the number of children of the vertex $v$. Assume two operations on rooted trees: contract an edge: choose an edge $E$, join two vertices adjacent to $E$ ...
2
votes
1answer
149 views

What is the “true” minimum spanning forest of a connected graph?

Normally, a minimum spanning forest of a graph G is defined as the union of minimum spanning trees of each of its components. This definition is a generalization of the minimum spanning tree of a ...
0
votes
1answer
39 views

Calculating Entropy

Hi there kind people, I'm studying for an Artificial Intelligence test in a week or so, and this question is from a past paper - and it has really stumped me. Any help would be appreciated. Thank ...
0
votes
2answers
341 views

Number of labeled non-isomorphic trees on $n$ vertices

Is there any algorithm to build or count the labeled non-isomorphic trees on $n$ vertices ?
4
votes
2answers
103 views

Computing Ancestors of # for Stern-Brocot Tree

Reading about the Stern-Brocot tree, the article gives this example: using 7/5 as an example, its closest smaller ancestor is 4/3, so its left child is (4 + 7)/(3 + 5) = 11/8, and its closest ...
1
vote
1answer
63 views

Is my graph a tree?

Let M be a smooth connected manifold. G is a group act on M cocompactly and suppose there is a harmonic function $h$ on M with minimal energy.$h:\rightarrow [0,1]$ such that h is nonconstant and ...
2
votes
3answers
381 views

What is the maximal path of a tree?

Could anyone explain obviously what the maximal path is ? Is it necessary for a tree that has two maximal paths that share no common vertex ?
1
vote
1answer
44 views

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)$; ...
0
votes
0answers
56 views

How to tell if a directed graph has a cycle?

If I have the directed graph here: I am confused whether or not this is a cycle or not. Because in the underlying graph, this is a 3-cycle for sure, but in the directed graph, there is no cycle if ...
0
votes
1answer
34 views

Where does the root of this tree come from?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
0
votes
1answer
76 views

Minimum Spanning Trees Weight Question

Given any undirected connected graph. If we redefine the weight of a spanning tree to the maximum weight of an edge (if the largest weight is 10 the weight of the tree is 10) are there any cases where ...
2
votes
3answers
146 views

Showing that the complete bipartite graph $K_{a,b}$ is a tree if and only if $a=1$ or $b=1$.

Let $K_{a,b}$ be the complete bipartite graph. Show that $K_{a,b}$ is a tree if and only if $a = 1$ or $b = 1$. The way my professor showed us for a complete graph is as below. I just don't know how ...
0
votes
1answer
248 views

Min and max height of a binary tree

Suppose I have n nodes, how can I find the max and min height of a tree? I've seen varying statements for the min height such as log2 (n) and log2 (n+1) but I wasn't sure which was correct and I am ...
0
votes
1answer
82 views

Computing the Value of a minimax tree

I am asked to compute the value of a minimax tree, which each node labeled with its initial value. I am just unsure how to do it. I know that it is a minimax tree if: the root is a min node, the ...
0
votes
2answers
185 views

Drawing a binary tree based on a traversal sequence

I'm given a sequence of characters that are from a pre-order traversal of a binary tree. I'm not given the binary but I need to draw the binary tree based on the sequence of characters from the ...
0
votes
0answers
44 views

Consider a B-Tree of order n and of height 3

Consider a B-Tree of order n and of height 3. i. Give the maximum number of pages in the tree (as a function of n) ii. Give the minimum number of pages in the tree (as a function of n) iii. ...
1
vote
1answer
52 views

Prove number of edges in an edge-disjoint spanning tree

I have the following problem. It isn't homework--it's additional work I want to do to further grasp the material in my Combinatorics class. Show that if a graph $G$ contains $k$ edge-disjoint ...
2
votes
0answers
107 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
2
votes
1answer
67 views

Dual graph of a tree

It is stated here that: For any connected embedded planar graph G define the dual graph G* by drawing a vertex in the middle of each face of G, and connecting the vertices from two adjacent ...
1
vote
0answers
83 views

The number of edges in a tree is $n-1$

I am trying to prove that the number of edges in a tree is $n-1$ where $n$ is the number of vertices. I do not wish to use induction. I already have established that a tree is a planar graph. Now my ...