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

Transforming spanning trees through a sequence of intermediate trees

the problem is as follows: Let $G$ be a connected graph, and let $T_1$ and $T_2$ be two of its spanning trees. Prove that $T_1$ can be transformed into $T_2$ through a sequence of intermediate trees, ...
0
votes
1answer
75 views

Inserting values left to right in a binary search tree

What does it mean to build a binary search tree by inserting values from left to right starting from an empty tree? The "left to right" part confuses me..I know how to build one by normally inserting ...
0
votes
1answer
423 views

How many vertices does a complete binary tree of height 1 have?

How many vertices does a complete binary tree of height 1 has? Height 2? Height d? Any hints on how to start to tackle these set of questions?
0
votes
1answer
56 views

Correspondence between fractal sets and trees

In Hillel Furstenberg's series lectures on ergodic theory in fractal geometry, he mentioned his search on finding a one-to-one correspondence between fractal sets and trees, however, I couldn't not ...
0
votes
1answer
175 views

Let T be a tree with sub-trees which each set has a vertex in common - hence T has a vertex in all of its sub-trees?

The question is: Let T be a tree with sub-trees $T_1,T_2,..,T_n$ such that all trees $T_i,T_j$ have a vertex in common which each set has a vertex in common - show that T has a vertex in all $T_i$. ...
0
votes
1answer
210 views

Relationship between ordered and binary trees

I am looking for a formula for the number of ordered trees with $n$ vertices and $l$ leaves as well as for a formula for the number of binary trees with $l$ left and $r$ right children. Finally, I ...
0
votes
1answer
385 views

How to find the maximum number of vertices in a tree with respect to maximum path length and maximum degree value

Given a tree, find the maximum number of vertices $v$ in that tree using the maximum path length $p$ and a maximum degree that applies to all vertices $d$. Assuming that I drew my test tree ...
0
votes
1answer
78 views

Constructing a tree from disjoint graphs

I will preface my question with the definition of a simple tree that applies to my question: -"A simple tree is an undirected and connected graph with no cycles."- I am having difficulty coming up ...
0
votes
1answer
143 views

Prove equivalence of conditions for a tree

Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent. $G$ is a tree. Any two vertices in $G$ can be connected by a unique simple path. $G$ is ...
0
votes
1answer
82 views

Natural order of rational trees?

What would be a natural order of rational trees? Rational trees arise naturally from free algebras if we view a term as a finite tree. For example the term f(a,g(b,c)) could be viewed as the ...
0
votes
1answer
458 views

How to make a parse tree for the following propositional logic formula?

I have a formula $\neg (( q \rightarrow \neg q) \vee p \vee ( \neg q \rightarrow ( r \wedge p)))$. As it contains 3 subformulas between the $\vee$'s, how can I put it into a parse tree. Would it be ...
0
votes
1answer
408 views

Proving terminal vertices and total vertices of a full binary tree?

I am trying to make a proof by induction of the following theorem. ...
0
votes
2answers
465 views

graph theory and forests

We were given an this question in my class: Prove that a forest with n vertices and m components has n-m edges using induction on m. Induction is not my strongest point and I was wondering if anyone ...
0
votes
1answer
350 views

Proving by induction

I'm having a problem relating to proving by induction that the Preorder(T) and Postorder(T) algorithms both print out all the nodes in the tree without repetition. I'm not quite sure where to start.. ...
0
votes
1answer
83 views

How can the jth level of a binary tree with n nodes has problems of size $({\frac{n}{2}})^j$?

I read from a book that the jth level (starting from j=0 or the root) of a binary tree with n nodes divides a problem into $2^j$ subproblems, each of size $\frac{n}{2^j}$. I understand where $2^j$ ...
0
votes
1answer
300 views

Graph Theory - Spanning Trees

Consider a graph $G$ composed of two cycles which share an edge. $C_x$ is the cycle of length $x$ and $C_y$ is the cycle length $y$, for $x,y \ge 3$. (for example, if $x = 6$ and $y = 5$, then $C_x$ ...
0
votes
1answer
157 views

How many arguments are there in a Merkle tree?

I want to calculate the amount of elements in a Merkle tree given the number of leaf elements. The number of elements at a given level n is equal to number of elements at a level n+1, divided by two ...
0
votes
1answer
145 views

Need help performing a tree method to test for satisfiability

For those who commented on my previous questions, sorry for the lack of information and explanation. Clearly I did not do a good job of explaining myself so I deleted the question and hope this one ...
0
votes
1answer
36 views

Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
0
votes
0answers
13 views

Tree of arity n: How to call a vertex that has only k (k<n) children?

What is the correct adjective for a vertex in an n-ary tree that has only k children (k < n)? I was thinking of something like "unsaturated", but I don't know if that is the correct word for this. ...
0
votes
1answer
29 views

Number of distinct Binary tree formed with respect to height h

How many types of distinct Binary Tree can be formed with a height of h? assuming height starts from 0 when the tree has only the root. example: if the height of tree is 1 then root-leftchild ...
0
votes
0answers
21 views

How does inserting N objects one at a time into an ordered AVL tree yield an efficient sorting algorithim

If we assume reblalancing an AVL tree of height n after an insertion or deletion takes O(n) operations. How does inserting N objects one at a time into an ordered AVL tree yield an efficient sorting ...
0
votes
0answers
38 views

Min. Spanning Tree - Same weight

Prove that every minimum spanning tree of a connected graph, $G$, has the same maximum edge. Intuitively, this makes sense to me. You need to have that heavy edge because that is the cheapest ...
0
votes
2answers
43 views

Tree with $k$ edges is a subgraph of any graph with all vertices of degree $\geq k$.

Let $T$ be a tree with $k$ edges. Let $G$ be a graph where every vertex has a degree of at least $k$. Show that $T$ is a subgraph $G$. I know this implies that in a graph where every vertex is at ...
0
votes
1answer
33 views

How to compute a marginal probability

Given a weighted graph, using the Kirchhoff's matrix tree theorem, how can I compute the marginal edge presence probability: $$P_\beta(ij)=Z_\beta^{-1}\sum_{\text{T spanning tree:$(i,j)\in ...
0
votes
0answers
26 views

Can a non-cyclic infinite proof tree with always-reachable provable nodes be used to construct a proof?

Suppose that I have a finite number of basic elements x,y,z ... and a finite number of operators +, * ... Terms X,Y,Z ... are created by combining basic elements and operators. For example, x+y, and ...
0
votes
0answers
19 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
0
votes
1answer
24 views

Finding the number of spanning trees on a set of vertices.

I need to find the number of spanning trees on $V = \{1,2,3,4,5,6,7,8,9\}$, where $\{1,2,3,4\}$ are leaves. Can anyone tell me how?
0
votes
0answers
20 views

A function for the branches of a tree

Imagine that we have to calculate the number of branches of a tree. Now I made a formula that associates the "level" (number of the times that a branch replicates itself) $k$ of the tree and the ...
0
votes
1answer
28 views

Distinct MST Edge Proof

Suppose that T1 and T2 are distinct MSTs for an undirected graph G. Let (u,v) be the lightest edge that is in T2 and not in T1. Let (x,y) be any edge that is in T1 and not in T2. What can you say ...
0
votes
1answer
20 views

Find MST based on new definition

Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the ...
0
votes
0answers
36 views

heavy path decomposition/heavy-light decomposition

I'm reading about the heavy path decomposition of trees and its application. I would like to know its time and space complexity. In addition, can the algorithm be implemented in distributed way? What ...
0
votes
0answers
14 views

Which cut-off for collapsing this tree?

I have a Newick tree that is built by comparing similarity (euclidean distance) of Position Weight Matrices (PWMs or PSSMs) of DNA regulatory motifs that are ~5-9 bp long sequences. An interactive ...
0
votes
0answers
27 views

prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
0
votes
0answers
13 views

What is a first-order dependency tree?

From the definition of Chow–Liu trees. Obviously, a tree is a graph with no loops; with first-order do they mean that it is a tree similar to those followed by a depth-first search?
0
votes
0answers
17 views

Representing trees in Set builder notation?

Is there a way to represent graphs and minimum spanning trees using set builder notation? e.g. I have a weighted graph of n nodes, all connected to each other in a mesh network manner. I am to ...
0
votes
1answer
32 views

Expected number of feed-forward/backward triangles in a random graph with internal nodes.

Suppose we have a graph with N* nodes (these are internal nodes. they all have at least one child). Every directed link in the network exists with probability p. What would be the expected number of: ...
0
votes
2answers
52 views

Finite trees and embedding in infinite regular trees.

Assume that you have a finite tree $T=(V,E)$, where $V$ and $E$ are the set of vertices and edges of $T$, respectively. Let $d_{max}$ be the maximum degree the some vertice(s) $v\in{V}$. Assume also ...
0
votes
0answers
39 views

How can I find the height of the Recursion Tree?

How do I determine the height of a Recursion tree? For example for the recursion $T(n) = 3T(\frac{2n}{3}) + O(1) $. Could you give me a hint?
0
votes
1answer
38 views

Proving that a sub-graph of a tree is a tree

The proof that P ::== any sub-graph, G* of the tree G, is also a tree, involves proof by contradiction. We can suppose that the sub-graph has a cycle --> the whole graph has a cycle --> the whole ...
0
votes
1answer
37 views

Definition of a leaf in a tree

Across two different texts, I have seen two different definitions of a leaf 1) a leaf is a node in a tree with degree 1 2) a leaf is a node in a tree with no children The problem that I see with ...
0
votes
1answer
310 views

Minimum number of nodes in balanced binary search tree

I'd like to know if anyone could help me verify a recursive formula for the minimum possible number of nodes a binary search tree would require to be balanced. So far, I know that the recursive ...
0
votes
0answers
63 views

Structural induction on internal nodes of a binary tree

I know my language is not super mathematic, but I want to make sure I have the logic down. Here is my proof for the number of internal nodes in a binary tree being equal to the floor_function(n/2), ...
0
votes
1answer
55 views

Binary Search Tree Traversals

Draw a BST when you insert, $O,V,E,R,F,L,C,W$ from left-to-right and determine the order of the nodes when using post-order traversal and pre-order traversal. My attempt at drawing the BST: ...
0
votes
0answers
33 views

Can an arbitrary network of nodes be effectively visualized as a circular “treemap”?

We all know that a treemap is effective for visualizing hierarchical tree data (i.e. where there are only 1 to many relationships like in a computer file system): But how difficult algorithmically ...
0
votes
1answer
47 views

Some questions about first-order logic (arising from a book by Raymond M Smullyan)

Recently, I got confused when reading a book about first order logic written by Raymond M smullyan. Chapter 1 page 9:When introducing the notion "Formation tree", smullyan define a formation tree for ...
0
votes
0answers
20 views

Can a search-tree be reversed in order to find more solutions?

consider a search-tree that we already know that if we start from the start-node (S), and go to nodes A1, B2, C1, then we get to the Goal-node. We have this solution, but we don't know the other nodes ...
0
votes
1answer
88 views

proof: center of a tree lies on the longest path

how can I make a proof of this property? I mean, given a weighted tree(with positive costs), how can I proof that the center of such a tree lies on the longest path?? I read to the first answer of ...
0
votes
1answer
58 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
0
votes
1answer
41 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...