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
17 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
31 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
18 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
40 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
39 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
32 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
44 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
22 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
72 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
31 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
25 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
0answers
15 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
16 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
41 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
31 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
0
votes
1answer
37 views

Prove by strong induction on the number of edges that every tree is a bipartite graph. [closed]

Prove by strong induction on the number of edges that every tree is a bipartite graph. Please can anyone help me? Thanks
5
votes
1answer
34 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$ ...
0
votes
0answers
20 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
64 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
0answers
30 views

A little bit more difficult problem regarding rooted plane trees

A question regarding rooted plane trees bothers me. We know that the number of rooted plane trees with $n$ nodes equals to $n-{th}$ Catalan number, that is $|Tn| = Cn$. But what is this number if we ...
0
votes
2answers
55 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} ...
0
votes
1answer
36 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 ...
1
vote
1answer
58 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$ ...
4
votes
2answers
79 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 ...
2
votes
3answers
174 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
57 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
1answer
44 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 ...
1
vote
1answer
27 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
1answer
29 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
28 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
69 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
30 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
44 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 ...
3
votes
2answers
69 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 ...
0
votes
2answers
39 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
16 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
34 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
77 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
33 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
52 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 ...
1
vote
0answers
27 views

How to determine size and height balance of binary search tree?

I've been reading/ learning binary search trees and I've been stuck on the following question for a while now. I have the following tree, how do I determine the height and size balance of it? How do ...
0
votes
1answer
62 views

What kind of tree it is? How to solve the problem?

I have a tree with following configuration: n is the number of different vertices v ($0 \lt v \le n$). Each vertice ...
2
votes
1answer
30 views

Finding a node in a full binary tree: expected number of comparisons

Consider a full binary search tree of height $k$ (the root is on level $1$ and the leaves on level $k$). By full I mean that all leaves are on level $k$ and level $k$ has exactly $2^{k-1}$ leaves. In ...
1
vote
1answer
57 views

Sentences, Formal Grammars with derivation (parse) trees

I've been reading / studying formal grammars for the past few weeks and I came across a question that puzzled me and I cannot seem to get my head around it for some reason. ...
0
votes
1answer
31 views

Directed spanning tree

Consider a directed graph. Is there any theorem on minimum number of outgoing or incoming links for each node of digraph that guarantees the existence of directed spanning tree?
1
vote
2answers
63 views

Shortest Path on Specific Graph with one Property !?

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
0
votes
0answers
17 views

Tree structure by using integer markers

I'm trying to model a situation in witch a group of entities are organized hierarchically. We say that entity A has privileges over entity B if there a direct hierarchical connection between A and B ...
2
votes
1answer
139 views

Longest Path in undirected unweighted graph

I came across a problem where I have to find out the longest path in a given graph. I have list of edges ( eg.{AB, BC} ) which states there is an edge between vertices/nodes (A,B,C). Now i want to ...
-2
votes
1answer
48 views

Graph Theory: labelled tree

I am preparing for the final exam, but struggling with these questions. How many labelled trees with $2n$ vertices such that the vertex with label $1$ has degree $k$, for $k = 1, 2$ and $n$? Also, A ...
2
votes
1answer
131 views

Furthest distance vertices undirected tree

I know in my mind that it's very obvious, but I just can't seem to prove the following statement: Let $G$ be an undirected non-trivial tree with at least $3$ vertices. Let $u$ be an arbitrary vertex ...