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

How do you find the value of n in this example

$n^(n-2) = 16$ meant to say n^(n-2) = 16 I know n = 4 through trial and error but how do you find n in a conventional manner? Im basically trying to solve how many nodes are in a tree that has 16 ...
0
votes
0answers
26 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 ...
1
vote
2answers
42 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
33 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
52 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$ ...
3
votes
1answer
63 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
147 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 ?
0
votes
1answer
52 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
33 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
24 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
28 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
20 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
60 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
16 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
36 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
64 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
19 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
12 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
28 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
72 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
29 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
42 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
23 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
60 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
24 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
44 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
27 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
59 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
16 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
62 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 ...
-1
votes
1answer
42 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
117 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 ...
0
votes
0answers
75 views

Modifying Kruskal's algorithm for Maximum Spanning Tree

So in our class, we did a proof on Kruskal's algorithm for finding Minimum Spanning Tree. Now, based on that, I have to modify it to find me a Maximum Spanning Tree. I know the idea, taking ...
1
vote
1answer
44 views

Collection of spanning trees for a simple connected graph

Consider a graph $G$ whose edges are labelled $\{1, 2, ..., k\}$. Then the set of spanning trees is a collection of subsets of $[k]$. a) Let $T$ = $\{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$. Can $T$ be ...
1
vote
1answer
46 views

Tree-related problem, counting leafs

I am studying Graph Theory right now, and I have solved tons of problems so far. However, I got a tree-related problem, where it asks me to prove that a tree, in which maximum node degree is 6, the ...
3
votes
1answer
52 views

Proofs involving some general formulae for trees and binary trees.

So here I have 3 tree-related questions. 1) Let $n\geq2$ and let $d_1 ≤d_2 ≤···≤d_n$ be a sequence of integers. Show that there is a tree with degree sequence $d_1,d_2,...,d_n \Leftrightarrow \sum ...
1
vote
0answers
28 views

Traversing multi-way tree, computational complexity

This is a computational challenge. I am looking for a clever simplification or heuristic. Imagine a multi-way tree. Each node has three child branches. Consider them to be decisions; do A, do B, do ...
0
votes
0answers
12 views

Tranform a set of tree in a DAG

It is possible transform a set of directed tree into a DAG? in this way transform a set of tree in wich there are repeated nodes into a DAG where exist no pair of nodes repeated, in such a way these ...
0
votes
1answer
41 views

Proof verification: Prove that a tree with n vertices has n-1 edges

This question is not a duplicate of the other questions of this time. I want to ask is how strong is the following proof that I am going to give from an examination point of view? Proof: Consider a ...
0
votes
1answer
51 views

Prove graph cannot have exactly two distinct spanning trees [closed]

Prove that a graph cannot have EXACTLY two distinct spanning trees.
1
vote
1answer
144 views

Prove that a graph cannot have two distinct spanning trees

I'm confused with this proof. More so that I think I'm confused as what distinct in this context means? Initially I thought it was that these 2 possible spanning trees cannot share the same edges, but ...
0
votes
0answers
43 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
2answers
55 views

Complete labeled Graph $K_6$ and Spanning Tree [closed]

I ran into a nice interview question, anyone could described it for me? from Complete labeled Graph $K_6$, remove one edge, how many spanning tree, the resulted graph has? Mathematician Learn ...
3
votes
1answer
46 views

Number of spanning trees of a labeled graph

This labeled graph is given, I need to find the number of its spanning trees. The number of spanning trees of the following graph is 3 and the number of spanning trees of this is 8 So as a ...
-1
votes
2answers
73 views

How many Hamiltonian cycles are there in $K_{10,10}$?

I want to calculate the number of Hamiltonian cycles in $K_{10,10}.$ Could anyone help me? I think in $K_{10}$ we have $9!$ Hamiltonian cycles.
1
vote
2answers
27 views

Trees-related proof

I just began my Graph Theory course, so I'm pretty knew in this area, at least when it's about formal proofs(I have some experience on intuitive level, implementing certain algorithms related to graph ...
1
vote
3answers
45 views

Traversing through a binary tree

Consider a full binary tree of n nodes numbered from 1 to n in the common top-down left-to-right manner. For the sake of the ...
5
votes
4answers
78 views

What is the number of full binary trees of height less than $h$

Given a integer $h$ What is $N(h)$ the number of full binary trees of height less than $h$? For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't ...
2
votes
1answer
65 views

what' is the number of full subtrees of a full binary tree?

I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are: Now my question is: What is $N(h)$ the maximum number of full sub-trees of a ...
0
votes
0answers
19 views

Determining whether two trees are isomorphic

Is there a (probably recursive) algorithm that can be used to determine whether two not necessarily binary ordered (sub)trees are isomorphic or not?