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

Infinite Search Tree Probibility

I have a question on Search Trees. I have a balanced, infinite, search tree. If you check a node at level $l$, the probability of finding a solution at that node is $p^l$. Questions The first ...
0
votes
1answer
137 views

How many spanning trees does the cycle graph C2014 have?

How many spanning trees does the cycle graph $C_{2014}$ have? How do I create a bipartite graph and use it to solve this problem?
0
votes
1answer
36 views

Normalization of data in decision tree

After reading through a few references, I have come to know that for machine learning in general, it is necessary to normalize features so that no features are arbitrarily large ($centering$) and all ...
0
votes
1answer
31 views

The intersection of $k$ subtrees of a tree $T$ is nonempty.

Let $T_1$, $T_2$, . . . , $T_k$ be subtrees of a tree such that any two of them have a vertex in common. Prove that they all have a vertex in common. Any hints/solutions are greatly appreciated. I am ...
0
votes
1answer
83 views

Visiting Node in BFS and DFS in the same order [closed]

if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false? a) G can be a ...
0
votes
1answer
54 views

How to understand the perfect binary tree formula?

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says: I'm ...
0
votes
3answers
50 views

How to write a summation function that counts the number of nodes in a tree?

I come from a programming background and am interested in learning how to represent some things as simple equations, as an entry into thinking mathematically. How do you represent a tree structure as ...
0
votes
1answer
52 views

Formula for number of “root” nodes in a tree where Parent shares child nodes?

If I have a tree like this: {a},{b,c},{d,e,f},{g,h,i,j} in this case we have a total of 10 nodes. Is there any equation where given "10" I can calculate how many bottom nodes there are (answer: "4" ...
0
votes
1answer
32 views

Proof that a local minimum in a spanning tree is also a minimum spanning tree.

Be $G$ a connected graph with weights associated to its edges. Be $T(G)$ the graph that has the spanning trees of $G$ as vertex, and two spanning trees are adjacent to each other if and only if each ...
0
votes
1answer
144 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...
0
votes
1answer
37 views

How I can prove the one order homology of a tree is zero

When T is a tree and d1 is boundary operator fromC_1(T) to C_0(T) how to prove kernel of d1 is {0} I think acyclic is key point but i don't know next step.
0
votes
1answer
74 views

Parse Trees - Arithmetic Expressions

In regards to the right side of this expression (c * (a-b)) how is it factored to include (-) instead of * and then (-) again? I cant understand what steps my teacher made to do this.
0
votes
1answer
55 views

What's an efficient algorithm for walking to a minimum spanning tree?

Given a connected directed acyclic graph $G(V, E)$, is there an algorithm for changing a spanning tree to a minimum spanning tree through a series of edge swaps? We can use Prim's or Kruskal's ...
0
votes
1answer
46 views

Finding the parent of a node in recombining binomial tree

I have posted an earlier question: Finding the child node in the recombining binomial tree. Now I would like to find the parent of a node in recombining tree. The tree looks like this: Now I need ...
0
votes
1answer
50 views

Proofs with binary trees [duplicate]

Now I have a binary tree which is How would I go about proving binary tree with $n$ leaves has exactly $2 n - 1$ nodes ?
0
votes
1answer
79 views

Are the structure of logical expression based on formative constructions like sequences or trees ?

Recently, I get confused when reading the book Principles of Mathematical Logic written by D. Hilbert. How to define the term 'logical expression'? I just envisage that it might be defined as anyone ...
0
votes
1answer
87 views

How to prove this necessary and sufficient condition for tree in graph theory?

Let $0<d_1\leq\ldots\leq d_n$ be integers. Show that there exists a tree with degrees $d_1,\ldots,d_n$ if and only if $d_1+\ldots+d_n=2n-2$.
0
votes
2answers
155 views

Use strong induction to prove number of vertices on complete tree is $2l-1$

Can someone help me construct this proof using strong induction? Use strong induction on $l$ to show that for all $l \geq 1$, a full binary tree with $l$ leaves has $2l-1$ vertices total.
0
votes
1answer
38 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
85 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
542 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
59 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
204 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
232 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
448 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
81 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
177 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
84 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
547 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
516 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
1answer
373 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
86 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
319 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
164 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
22 views

How many trees can be drawn using$n$ vertices without rebuilding isomorphs?

I'm told to draw all possible trees with exactly $6$ vertices. I was able to draw a maximum of $6$ trees. Any more were isomorphs of these $6$ trees. How can I determine if I have drawn all the trees? ...
0
votes
1answer
20 views

expression tree

I'm having some trouble understanding expression trees especially with putting this expression into a tree: S/P^Q^R Any help with how to do these is greatly ...
0
votes
0answers
14 views

Number of partial trees of a complex graph

Demonstrate number of partial trees of a complex graph without a fixed edge is $(n-2)\cdot n^{n-3}$, for $n\geq 3$
0
votes
1answer
32 views

Find the number of trees on the vertex set V = {1, 2, …, 8} in which all vertices have degree 1 or 4.

I am unclear how to figure this out. I understand that if there were 6 vertices of deg = 1 and 2 vertices of deg = 4 then I can simply check if the degrees all add up to 2n-2 and use a specific thm: ...
0
votes
0answers
23 views

Calculate the total cost

According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: Cost per level $i \to \left( \frac{7}{8} ...
0
votes
0answers
14 views

Is this a Red-Black Tree?

I tried to build RBT (Red-Black Tree) via this way: I build a balanced binary search tree (much as I can) and then colored it... Now the Q is: if this is a legal RBT? At my opinion is yes, because ...
0
votes
0answers
47 views

Finding spanning trees using Depth-First Search

I am wondering if root in spanning trees using Depth-First Search can have more than $2$ children? I know this is a silly question, but there is an example in the book which involves only $2$ ...
0
votes
2answers
34 views

Property of the numbering in preorder traversal of the tree

$v$ denotes the vertex which has been asigned the number $v$. The vertices are numbered in the order visited. In preorder all vertices in a subtree with root $r$ have numbers no less than $r$. More ...
0
votes
0answers
27 views

Findind diameter of minimum spanning tree in matlab

hello I am trying to find the diameter of a spanning tree using Matlab's function graphshortestpath().I have a 23 indices spanning tree and I want to find it's diameter. I use these parameters in a ...
0
votes
1answer
21 views

Merging of height balanced trees

$H_1$ and $H_2$ are two height balanced trees. How can they be merged such the time required for merging them is $O(\log n_1 + \log n_2)$ where $n_1$ and $n_2$ are the number of nodes in the trees ...
0
votes
0answers
12 views

Breadth First Search - Building All Possible Trees of a Set

Suppose there is a set of values arranged in a binary search tree (BST). I'm trying to write an algorithm that takes in a sequence, and prints all permutations (BSTs) that have that sequence as their ...
0
votes
0answers
17 views

Oversampling and trees

I want to create a model to predict the propensity to buy a certain product. As my proportion of 1's is very low, I decided to apply oversampling (to get a 10% of 1's and a 90% of 0's). Now, I want to ...
0
votes
0answers
18 views

Suffix string starting at $i$

$S$ is the string of characters:TACGCGGT$ For string S and each of the positions $i=1,2,\dots,9$ write down the suffix string starting at position $i$. What is ...
0
votes
0answers
20 views

Direct Graphs: Prove that for every rooted tree $G=(V,E)$ the algorithm computes a topological sorting of $G$. [duplicate]

Consider the following recursive algorithm for topological sorting of a rooted tree $G=(V,E)$: Apply topological sorting to the vertices in each subtree hanging from the root, and then order the root ...
0
votes
1answer
17 views

Question about consistency in the junction tree algorithm (graphical models

I have a question about consistency in graphical models. It is often stated that when running the junction tree algorithm on a clique (cluster) tree, the marginals of all nodes are locally and ...