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
6 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
18 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
57 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
24 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 ...
0
votes
0answers
34 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
19 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
57 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
18 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
36 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
25 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
56 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
41 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
40 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
109 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
41 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
44 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
49 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
17 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
11 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
33 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
129 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
34 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
51 views

Complete labeled Graph $K_6$ and Spanning Tree [on hold]

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
34 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
72 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 ...
-3
votes
3answers
119 views

How many spanning trees are there? [closed]

I see a Strange and Nice Ex on Discrete Math. How many Spanning Tree is there for following Labeled Graph !!? How we can solve such a question? Thanks to ...
1
vote
3answers
43 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
66 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
56 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
18 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?
3
votes
2answers
80 views

Find a Generating Function for Ordered Rooted Ternary Trees

The Full Question If we let $T=$ the family of rooted ternary trees, $t_n =$ be number of trees in $T$ with $n$ nodes and $T(x) = \sum\limits_{n=0}^{\infty}w_nx^n$ be the generating function of $T$. ...
0
votes
0answers
33 views

Proving number of leaves in $m$-ary tree.

Prove that a full $m$-ary tree with $i$ internal vertices has $l=(m-1)i +1$ leaves. I'm having trouble finding any good information about $m$-ary trees online I've got a few pictures but they don't ...
-1
votes
1answer
61 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 ?
0
votes
0answers
21 views

Adjacency of vertices from Prufer sequence

Is adjacency of vertices can be known from Prufer sequence without decoding? Thanks!
1
vote
1answer
7 views

Get number of vertices when number of internal vertices is known ofr a full binary tree

But I can find a counter example: * / \ * * / \ / \ * * * * Here $k = 2$, but number of vertices is 6, and number of terminal ...
1
vote
1answer
34 views

Leftish Heap and Its Right Spine

Purely Functional Data Strutures presents the following question: Chapter 3, Question 1: "Prove that the right spine of a leftist heap of size n contains, at most, floor ( log ( n + 1) ) ...
2
votes
1answer
60 views

Number of rooted subtrees with m edges of a p-regular tree

I have the following question: Assume I have an infinite $p$-regular tree, that is a tree where every node has degree $p$ (so also the root should have degree $p$). Then how many subtrees containing ...
2
votes
1answer
73 views

Prove that the vertex degree of a minimum spanning tree is in $\mathcal{O}(1)$

I have given a set of points $S$ in $\mathbb{R}^2$. From the this points I create a mininum spanning tree MST. The euclidean distance of the points is used as the weight for the edges. The ...
2
votes
1answer
104 views

Relax function on Bellman Ford Algorithms

In a Weighted Directed Graph $G$ (with positive weights), with $n$ vertex and $m$ edges, we want to calculate the shortest path from vertex $1$ to other vertexes. we use $1$-dimensional array $D = ...
2
votes
1answer
74 views

what is an “edge disjoint spanning tree”?

if there are n = 2 vertices in a connected graph, i am supposed to have "n/2 edge disjoint spanning trees". This means i should have 1 edge disjoint spanning tree for a n = 2 graph? My best guess ...
0
votes
1answer
19 views

Graph Theory: proof about the number of vertices in a Tree's component

I'm having some problem understanding the question below: Let T = (V,E) be a tree. Show that T has a vertex v such that for all e that exists in E, the component of T-e containing v has at least ...
1
vote
0answers
51 views

How to find the number of connected components of a graph by using its 16x16 adjacency matrix?

Good day, I have this exercice that provides me with the 16x16 matrix of adjacency of a graph and it asks me to find the number of connected components of the graph and I need to give a spanning tree ...
3
votes
0answers
99 views

Associativity of the tensor product of dendroidal sets

For any smal category $A$, I shall write $\widehat A$ for the category $[A^{\text op}, \mathbf{Set}]$ of presheaves on $A$, and $y_A\colon A \to \widehat A$ for the Yoneda embedding relative to $A$. ...
1
vote
2answers
49 views

Rooted Tree and Greedy Algorithms

In a Rooted Tree, we have a message on Root. in each step, each node that has a one copy of message, can transfer this message to at most one of it's childeren. we want to use minimum step and send ...
2
votes
1answer
108 views

Two disjoint spanning trees, spanning subgraph with all even degrees

Show that if a graph has two edge-disjoint spanning trees then it has a connected, spanning subgraph with all degrees even. I start by looking at the union of the two spanning trees. I know it has ...
2
votes
0answers
60 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...