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

1
vote
0answers
204 views

A tree that does not satisfy: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$?

It is a strange question on a book. Give an example of a tree $T$ that does not satisfy the following property: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$. I ...
0
votes
2answers
117 views

Narrowing a Stern-Brocot tree

Say I only wanted to enumerate the rational numbers between 0 and $a$. Is there a way to "narrow" a Stern-Brocot tree to provide this? I tried keeping my left bound at "$\frac{0}{1}$" and setting my ...
1
vote
0answers
56 views

Keeping consistency in subjective ranking

I'm doing some work on a computer program that aids in ranking items which don't have a way to objectively compare to each other. As it is now, it takes each item and pairs it up with each other ...
1
vote
1answer
68 views

Looking to generalize a binomial tree with some constraints.

I've got a set of sample data and I'm looking to see if it's possible to generalize a binomial formula to give a closed form solution to this. If not, would it be possible to write a program to do ...
1
vote
3answers
1k views

Graph with cycles proof questions

Two questions I'm stuck with: If C is a cycle, and e is an edge connecting two nonadjacent nodes of C, then we call e a chord of C. Prove that if every node of a graph G has degree at least 3, then ...
1
vote
1answer
532 views

Prove that in every tree, any two paths with maximum length have a node in common.

Prove that in every tree, any two paths with maximum length have a node in common. This is not true if we consider two maximal (i.e. non-extendable) paths. What does this even mean?
2
votes
0answers
755 views

Minimum Spanning Tree in a Complete Graph

We generate a complete euclidean graph by taking N random points from a limited (1.0 x 1.0 square) 2D space, connecting them all together (complete graph) and giving the edges weights proportional (or ...
1
vote
3answers
1k views

Sufficient conditions on degrees of vertices for existence of a tree

I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me? the question: "there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are ...
0
votes
1answer
431 views

Is smallest binary tree simply root node? Or does it need to have two child nodes?

Apologies for this rather simplistic question, I've just started looking at binary trees and the material I've been provided wasn't explicit about this. Presumably a parent node of a binary tree can ...
6
votes
1answer
609 views

Understanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.

I was reading the Wikipedia article on Friedman's finite form of Kruskal's tree theorem, and am interested in the large numbers TREE(n). I would like to verify TREE(2)=3 myself, but find conflicting ...
1
vote
0answers
230 views

Finding the number of spanning trees of a given height

I hope I can avoid being confusing, but here goes. I have a graph $(V, E)$, connected, undirected and with no loops. I also have an assignment of integer-valued weight to each edge of the graph. ...
2
votes
0answers
107 views

A few questions about a relationship between some integer sequences and infinite recursive trees

In his book Gödel, Escher, Bach Douglas Hofstadter defines the following two integer sequences: Hofstadter G-sequence: $a(n)=n-a(a(n-1))$ Hofstadter H-sequence: $a(n)=n-a(a(a(n-1)))$ He says ...
2
votes
0answers
94 views

How matroids can help me locating trees inside a graph?

Background I am working on a project at present involving graph analysis. I basically need to mathematically model trees inside my graph. How can this be done using Matroids? What I am looking for ...
0
votes
2answers
276 views

Category of Trees as sub-category of Category of Graphs

A tree (like a binary search tree) is a direct graph with some limitations (no cycles, connected). How can I express the category of trees as "sub-category" of a graphs? There is a way? I'm not sure ...
1
vote
1answer
474 views

Number of possible Prüfer codes

I am trying to solve the following problem in my book: (Code stands for Prüfer code) Consider labelled trivalent rooted trees $T$ with $2n$ vertices, counting the root labeled $2n$. The labels are ...
1
vote
1answer
3k views

Maximum number of distinct binary tree possible with 4 nodes

what is the maximum number of distinct binary tree is possible with 4 nodes? ans is 6 but how? acc to me it should be 14
2
votes
0answers
79 views

Embedding tree metric isometrically into $\ell_\infty$

I just started (independent) learning on metric embeddings from the Fall 2003 offering of the course at CMU. I have a limited mathematical background and alas, it made me stumble at the first exercise ...
3
votes
3answers
327 views

Cheapest spanning tree

I am trying to prove the following: Let $x_1$ be any vertex of a weighted connected graph $G$ with $n$ vertices and let $T_1$ be the subgraph with the one vertex $v_1$ and no edges. After a tree ...
2
votes
1answer
95 views

Showing two recurrences to be identical

I am trying to prove Cayley's formula for number of labelled trees on n vertices using multinomial coefficients. The multinomial coefficient satisfies the recurrence: $\tbinom{n}{r_1,\cdots ...
3
votes
0answers
179 views

Number of spanning arborescences

I am trying to prove the following result from my book: Let $G$ be a directed graph with vertices $x_1,x_2,\cdots x_n$ for which a directed Eulerian circuit exists. A spanning arborescence with root ...
0
votes
2answers
932 views

Searching a binary search tree for a specific value

suppose numbers from 1 to 1000 are saved in a binary search tree and we want to find 363. Which of the following sequences cannot be the order of elements while reaching the searched value? 925, ...
0
votes
1answer
175 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 ...
2
votes
1answer
270 views

Proof about trees

Show that in any tree there exists a node such that, if we remove this node and the edges adjacent to it, we will obtain trees which have at most n/2 nodes (the removed node is not counted ...
4
votes
2answers
218 views

On the number of caterpillars

A caterpillar is a tree with the property that if all the leafs are removed then what remains is a path. Could you help me to prove that there are $2^{n-4}+2^{\lfloor n/2\rfloor-2}$ caterpillar on $n$ ...
1
vote
0answers
92 views

Concerning The 'Price-Collecting Steiner Tree'

I'm a Master student at the University of Leuven, Belgium. I have to make a report of a case concerning the 'Price-Collecting Steiner Tree'. We have our model and our restrictions. We are just looking ...
1
vote
3answers
98 views

Comparison trees

You have 60 coins. You know that 1 coin is either lighter or heavier than the other coins. How many comparisons are needed in a worst case scenario to discover which coin is the false one and ...
6
votes
0answers
315 views

Certain permutations of the set of all Pythagorean triples

The fact that the set of all primitive Pythagorean triples naturally has the structure of a ternary rooted tree may have first been published in 1970: http://www.jstor.org/stable/3613860 I learned ...
2
votes
1answer
477 views

Recursive Generating function for enumerating leaf labeled binary trees

Let be B(z) the exponential generating function for the number $b_n$ of different rooted unordered binary trees with exactly n leaves labeled only at their leaves (so the internal nodes are ...
4
votes
3answers
784 views

Spanning trees in a ladder graph

Let $L_n$ be the ladder graph formed from two $n$-vertex paths by joining corresponding vertices. For example $L_4$ is the following I have to find a recurrence $<t>$ where $t_n$ is the ...
0
votes
1answer
355 views

Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves

What is an example of a direct bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves?
1
vote
2answers
108 views

A bijection between ordered trees and ballot lists

Could you help me to prove that there is a bijection between ordered trees with $n+1$ leaves and ballot lists with $n$ A's and $n$ B's? A ballot list is a sequence of A's and B's such that all ...
1
vote
2answers
175 views

Is having no directed cycles in a directed acyclic graph (DAG) a byproduct of the design, or is it intentional?

According to Wikipedia: That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v ...
5
votes
2answers
152 views

An identity on the number of trees

Let $T_n$ be the number of labelled trees on $n$ vertices, then $$ T_n=\sum_kk\binom{n-2}{k-1}T_kT_{n-k} \tag{1}$$ Using this question, I was able to prove that $$ T_n= \frac{n}{2} \ ...
9
votes
2answers
334 views

How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?

How can I prove the identity $$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$ I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...
12
votes
2answers
852 views

Partition a binary tree by removing a single edge

The question is : B-3 Bisecting trees Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced by a ...
1
vote
1answer
209 views

Depth distribution of normalized decision trees?

Lets work with the following inductive definition of a decision tree: 1) $\bot$, $\top$ are decision trees. 2) If $x_i$ is a variable and $T_0$, $T_1$ are decision trees then $(\lnot x_i \land T_0) ...
3
votes
1answer
530 views

Spanning Trees of the Complete Graph Avoiding a Given Tree

EDIT: I think everyone understood, but I never explicitly stated that I am looking at labeled spanning trees. Let $T$ be a tree contained in $K_n$ (the complete graph on $n$ vertices). How can one ...
4
votes
0answers
95 views

Identify this combinatorial construction

I am no combinateur, but I stumbled across the following construction when studying an operad arising from information theory (actually it's a special algebra of an A$_\infty$-operad). It looked ...
3
votes
4answers
2k views

Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

Update: This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution. http://www.youtube.com/watch?v=VbSwwos4R2E Hi, I ...
0
votes
0answers
159 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
4
votes
0answers
120 views

Are almost all rooted trees asymmetric?

It's well known that almost all graphs are asymmetric (have trivial automorphism group) and that almost all free trees are symmetric. By which argument do I see whether almost all rooted trees are ...
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
612 views

Maximum height of a quad tree

If we have a quad tree where each node must have 0 or 4 children, is there an expression that can me the maximum height of a quad tree with $n$ nodes?
1
vote
2answers
533 views

Graph - Minimum spanning tree

I have a graph with a cycle ($v_1,\ldots,v_k, v_1=v_k$). Claim: If there is a cycle with 2 edges of the same weight, and they are the heaviest edges in this cycle, then there is more than one Minimum ...
5
votes
3answers
749 views

How do you calculate the average length of a random binary tree?

Assuming that you start out with a root node, and decide with 50% probability whether or not to add two children nodes. If they do, repeat this process for them. How can you find the average length of ...
2
votes
2answers
585 views

Number of inner nodes in relation to the leaf number N

I am aware that if there is a bifurcating tree with N leaves, then there are (N-1) internal nodes (branching points) with a single root node. How is this relationship proved? Best,
4
votes
1answer
347 views

Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$. I'm now searching for an intuitive, or geometric, or visual proof of ...
7
votes
2answers
2k views

Condition on degrees for existence of a tree

Here is what I need to prove: Let $d_1,d_2,...,d_n$ be a sequence of natural numbers (>0). Show that $d_i$ is a degree sequence of some tree if and only if $\sum d_i = 2(n-1)$. I know that: 1. ...
2
votes
1answer
257 views

Fast question about minimum spanning trees

If any edge from a given spanning tree T0 is contained in some minimum spanning tree T*, does this imply that T0 is also a minimum spanning tree ? Right now, I'm trying to draw on paper some graphs ...
4
votes
1answer
5k views

Determining if two graphs are isomorphic

The answers are already given after the $=$ sign of each question. But I don't know how they arrived at these answers. What does it mean to say $f(A)=1$ and so on? I can't find the connection.