A tree is a graph that is connected but contains no cycles.
4
votes
2answers
50 views
How many vertices of degree 1 in a tree?
How many vertices of degree 1 are there in a tree with no vertices of degree more than 4?
The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of ...
5
votes
1answer
132 views
Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:
I ...
4
votes
1answer
85 views
Is the graceful labeling conjecture still unsolved?
From the Wikipedia article on graceful labeling:
... A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that ...
2
votes
1answer
42 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
140 views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
Moderator Note: This is a current contest question on codechef.com.
What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i ...
1
vote
1answer
70 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
1answer
127 views
What is the fairest solution/formula for rewarding points in a hierarchical network?
Introduction
The nature of this hierarchical network is based on the concept of Multi-Level Marketing strategy.
Example 1 - Unfair Situation
Ancestor receives 1 point for every descendant ...
1
vote
1answer
80 views
Finite Rooted Binary Trees
I am new to learning about finite rooted binary trees. This lemma below is from John Meiers book: Groups, Graphs and Trees. There is no aval proof in the book. I was just wondering is I could catch a ...
0
votes
1answer
30 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
131 views
has deleting node in a binary search tree Displacement feature?
I am developing an academic project about graph and tree theory.I searched a lot but I didn't find a clear answer. In a part of project we want to delete some nodes from tree for example we want to ...
0
votes
1answer
59 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 ...
0
votes
1answer
122 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 ...
6
votes
0answers
215 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 ...
4
votes
0answers
53 views
Free medial magmas
A medial magma is a set $M$ with a binary relation $*$ satisfying $(a*b)*(c*d) = (a*c)*(b*d)$. Medial magmas constitute an algebraic category $\mathsf{Med}$, therefore there is a functor $\mathsf{Set} ...
4
votes
0answers
87 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
0answers
82 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 ...
3
votes
0answers
94 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 ...
2
votes
0answers
29 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
0answers
189 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 ...
2
votes
0answers
40 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
0answers
37 views
Groups acting on (regular) trees with finite quotient
Let $T$ be a regular tree, and suppose that $G \leq \mathrm{Aut}(T)$ has finite quotient graph, $T / G$. Is it true (in general) that $G$ will have trivial centralizer in the full automorphism group? ...
2
votes
0answers
326 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 ...
2
votes
0answers
78 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
75 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
...
2
votes
0answers
57 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 ...
1
vote
0answers
25 views
Finding number of homeomorphically irreducible trees of degree N
There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree 10. This is discussed in many places, such as here and is ...
1
vote
0answers
36 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.
1
vote
0answers
26 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
0answers
41 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 ...
1
vote
0answers
47 views
How can I prove this property of a $d$-ary tree?
I have the following homework (algorithms lecture):
Every $d$-ary tree $G=(V,E)$ contains a vertex $v$ such that the size of the subtree with root $v$ is at least $\frac{1}{d+1} \vert V \vert$ and at ...
1
vote
0answers
15 views
Is there a fast tree balancing algorithm when addition > deletion
Is there a tree balancing algorithm / tree structure that is faster on addition of nodes than on deletion?
1
vote
0answers
30 views
How to formulate a best-search algorithm limited by a count of nodes visited?
The problem
I'm doing a search by computer program. Each node takes about 5 minutes of wall time to get a result so I'm looking to carefully choose the nodes to inspect so as to find the best result ...
1
vote
0answers
107 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 ...
1
vote
0answers
42 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
0answers
144 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. ...
1
vote
0answers
77 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 ...
0
votes
0answers
40 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 ...
0
votes
0answers
17 views
2-3-4 Tree: how to insert numbers to optimise the layers?
Let's imagine I have number in a list from 1 to 15, then the way to have 2 full rows is to insert them with this order into an empty 2-3-4 tree
2,4,6,8,10,12,14,1,3,5,7,9,11,13,14,15
(you can test ...
0
votes
0answers
41 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
0answers
54 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 ...
0
votes
0answers
66 views
Spanning Tree question regarding fundamental cycle / cutset
Hello i have a question regarding this graph and i am not sure about the answer.
Given the following graph (image in link), where the dotted lines are edges of a spanning tree, find the fundamental ...
0
votes
0answers
43 views
Constructing steiner tree
Given 4 nodes with edge values as stated below, is it possible to build a minimum spanning tree using Steiner tree?
...
0
votes
0answers
71 views
Bootstrap sampling
The usual way to create bootstraps is by sampling with replacement from the original data set.
The resulting resampled bootstraps have the same length (N records/data points) as the original data ...
0
votes
0answers
82 views
Bounding the number of nodes in a sub-tree of a Red Black Tree
Let T be a Red Black tree with n nodes.
Let v be a child of a child of the root.
Find a tight asymptotic lower bound as a function of n to the number of nodes in the sub-tree of v (meaning the root of ...
0
votes
0answers
49 views
Upper bound for number of unlabelled trees?
Is there even a remotely good formula for the upper bound for the number of unlabelled trees. I know of Knuth's formula for asymptotic behaviour, but that is not always above the actual value. The ...
0
votes
0answers
179 views
Depth-first spanning tree?
I am going to identify tree edges and back edges in an undirected graph.
The graph consists of $5$ nodes, the edges between these nodes are as shown below:
Suppose starting with $v_1$, after a ...
0
votes
0answers
44 views
An MST-like problem with vertex selection
Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...
0
votes
0answers
233 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?
0
votes
0answers
110 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 ...
0
votes
0answers
123 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 ...
