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

2
votes
1answer
52 views

Proof of the Converse of Kraft's Theorem

So I have already proven Kraft's theorem for ternary trees, and I have been tasked with proving the converse. That is, I need to show that there is a ternary tree with $k$ leaves, such that leaf $i$ ...
0
votes
0answers
21 views

Simplification of a dervived binary tree with n nodes [duplicate]

hi I need help with this problem how do simplify this equation and what are the steps and approaches to this problem
0
votes
0answers
293 views

What is the algorithm to sort 5 elements in 7 binary comparisons?

I'm tasked with finding the algo that sorts 5 elements in 7 binary comparisons. (The 7 is derived from ceilingFunction(log 5!), which our text states is the minimum number of comparisons required for ...
2
votes
2answers
910 views

Tree pruning question…

all. I'm facing the question: "A chain letter starts when a person sends a letter to five others. Each person who receives the letter either sends it to five other people who have never received it ...
0
votes
1answer
42 views

Identify Type of Recursive Sequence?

I would love to learn techniques for solving the following, but I can't seem to identify this type of sequence: let $N > 0$ and let $k$ be an arbitrary positive integer between $0$ and $N-1$ ...
3
votes
0answers
88 views

Mathematical notation for formulas involving trees

I am working on document that requires me to write such things as "$T_1$ is a descendant of $T_0$", or "$N_1$ is an parent of $N_2$". For now, I've been highjacking set notation for use in formulas, ...
2
votes
1answer
1k views

Show that Minimum Spanning Tree is unique

Show that MST is unique in case the edge weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$. I thought that the proof can be done for example by contradiction, saying that we ...
9
votes
2answers
322 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$ ...
1
vote
1answer
389 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
1
vote
0answers
50 views

Red Black Binary Search Trees

Give an example of a Red-Black tree and a value, for which inserting the value, and then immediately deleting it yields a tree that is different from the tree before the insertion.
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
0answers
106 views

Nilpotency of the adjacency matrix of a directed tree network

Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and ...
0
votes
1answer
109 views

Recurrence relation for the number of spanning trees in a connected graph proof

The number of spanning trees in a graph $G$ containing an edge $e$ is equal to the number of spanning trees in $G/e$. The number of spanning trees in a graph $G$ not containing an edge $e$ is equal to ...
1
vote
1answer
194 views

What is the length of the Minimum Spanning Tree

What is the length of the Minimum Spanning Tree for the following weighted graph? Solution. The length of any minimum spanning tree for this graph (and there is more than one) is 60. The graph and ...
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 ...
3
votes
1answer
147 views

Cubic (3-regular) graph spanning tree

Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes): Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 ...
1
vote
2answers
165 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 ...
3
votes
1answer
84 views

Prong Corollary, $G$ has a subgraph isomorphic to $T$

There is a corollary in Diestel textbook Graph Theory. Corollary 1.5.4. if $T$ is a tree and $G$ is any graph with $\delta(G) \geq |T|-1$, then $T \subseteq G$, i.e. $G$ has a subgraph isomorphic ...
0
votes
2answers
526 views

Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle

When proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle, is it sufficient to just remove that edge that created a cycle, then it ...
3
votes
0answers
280 views

Algorithm for generating homeomorphically irreducible trees of size n

In this video they talk about generating all the homeomorphically irreducible trees of size 10. I was wondering if there is a generating algorithm for generating all the homeomorphically irreducible ...
3
votes
1answer
59 views

What's the rank of this well founded relation?

Definition A tree is an ordered list of trees. (N.B these are finite objects and there is a very simple computable bijection of them with $\mathbb N$) Examples [] and [[],[],[]] and ...
2
votes
3answers
377 views

Graphs: trees, induction proof

I was wondering if you could help me prove the following. $G$ is a tree $\iff$ deleting any edge will disconnect it. And a similar one: $G$ is a tree $\iff$ adding any edge will create a cycle. I ...
0
votes
2answers
352 views

Confusion related to a graph problem

I have this question related to this graph problem Suppose that an n-node undirected graph G = (V , E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. ...
9
votes
2answers
619 views

“Ballot numbers” sum up to Catalan numbers

Summing certain numbers and comparing the results with OEIS, I found that $ \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} = C_{n+1} - C_{n}, $ where $C_n$ denotes the $n^{\textrm{th}}$ Catalan ...
6
votes
2answers
137 views

Question about trees and generalizing the Principle of Dependent Choices.

One form of the Principle of Dependent Choices is that for any tree $T$ of height $\omega$ such that every node of $T$ has a successor, there is a branch of $T$ of length $\omega$. In this post, I ...
0
votes
0answers
92 views

Straight skeleton is a tree

Can anybody give me a hint on how to prove that the straight skeleton of every polygon is a tree. Here is the definition of the straight skeleton (taken from Wikipedia): The straight skeleton of a ...
2
votes
1answer
50 views

Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
1
vote
1answer
168 views

For BSP generation, How to intersect or locate a triangle with a plane defined by another triangle?

I've hit a stumbling block in my project to draw the Utah teapot. I want to generate a binary space partition tree of a set of 3D triangles. The decision step in the recursive tree-construction ...
1
vote
0answers
46 views

Enumeration of symbols in grammatical expressions or vertices in tree graphs

I have expressions (type of a function) like e.g. $$f:(A\to B)\to C \to (D\to E)\to F.$$ (Where I understand $A\to B\to C$ as $A\to (B\to C)$, in case that is relevant.) There might be information ...
1
vote
2answers
347 views

single elimination tournament, don't understand question?

A single elimination tournament is performed in rounds. In each round the teams each play exactly one game and the winners continue, and the losers are knocked out of the competition. So, in each ...
6
votes
0answers
276 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 ...
0
votes
1answer
130 views

Computational Complexity of Parallel Algorithms

Does parallelism factor in when deriving the computational complexity of a parallel algorithm? Suppose I have a perfect binary tree $T$ with leaves numbered $1$ to $n$, and an algorithm ...
2
votes
0answers
74 views

Presentation of tree decompositions (and related concepts) in terms of continuous maps?

A tree decomposition of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure: Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$; The union ...
2
votes
1answer
74 views

A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing): What I need is a ...
0
votes
1answer
342 views

Is this formula for the number of nodes for a complete tree or a full and complete tree?

In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer: $$ \sum^{h}_{i = 0}k^i $$ where h is the height and k is the max number of ...
3
votes
2answers
1k views

What does lg x mean? is it $\log_2 x$ or $\log_{10} x$ in binary trees

I'm a bit confused, $\log_{10} x = \log x $ right? I believe I've read somewhere that $\log_{2} x = lg x$ but some people say lg = $\log$. So what does lg really stand for? specifically when talking ...
3
votes
2answers
90 views

Real tree and hyperbolicity

I seek a proof of the following result due to Tits: Theorem: A path-connected $0$-hyperbolic metric space is a real tree. Do you know any proof or reference?
2
votes
2answers
1k views

Proof by induction and height of a binary tree

I need some help with a simple proof. I want to know if this proof is correct: Let's define the height of a binary tree node as: 0, if the node is a leaf 1 + the maximum height of the children ...
3
votes
1answer
61 views

Tree formalisms

The intuitive notion of a tree in mathematics is quite straightforward. However, there are several different formalisms of the tree concept. The link http://ncatlab.org/nlab/show/tree lists several ...
4
votes
1answer
214 views

characteristic polynomial of the adjacency matrix of a tree

I have read that if $A$ is the adjacency matrix of a tree $T$, then we have that $$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k} $$ where $N_k(T)$ is the number ...
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 ...
1
vote
2answers
277 views

Breadth first search tree's cycles [duplicate]

Possible Duplicate: Proof related to breadth first search I'm trying to prove the following: Suppose a connected graph $G$ has a cycle $C$ of length $n$. Prove that in any breadth-first ...
5
votes
2answers
247 views

Suppose there are two different spanning trees for a simple graph. Must they have an edge in common?

My instinct is yes, but I don't know how to formalize it into a proof. I still haven't wrapped my head around spanning trees yet. Any thoughts are appreciated!
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 ...
3
votes
2answers
243 views

Bijection between binary trees and plane trees?

I would like to describe a bijection between binary trees and plane trees. A binary tree has a root node and each node of the tree has at most 2 children (left and right). A plane tree has a root node ...
4
votes
1answer
4k 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.
1
vote
1answer
148 views

Depth first search on graph

I have a homework problem I think I know the answer to, but want to double check Consider the graph with three nodes, $a$, $b$, and $c$, and the two arcs $a \rightarrow b$ and $b \rightarrow c$. ...
1
vote
0answers
48 views

What is the runing time of this algorithm involving length and depth?

I'm hoping that someone can shed some light on this running time. I have a "tree", for lack of a better description, that has a length $l$ and depth $d$. I want to maximize the tree size, which ...
2
votes
1answer
267 views

Length of Shortest Path in a Generated Binary Tree

Let's say I have a binary tree of $2$-tuples of positive integers starting with $(1,1)$. The left-child of any element $(A,B)$ is $(A,A+B)$, and the right-child of any element is $(A+B,A)$. Hence, the ...
0
votes
1answer
603 views

M-ary tree problem

A full $m$-ary tree $T$ has 81 leaves and height 4 1) Give the upper and lower bounds for $m$ 2) What is $m$ if T is also balanced? [with $m^h=l$ for maximum leaf in a m-ary tree $m^4=81$ then m=3 ...