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

8
votes
0answers
113 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} ...
6
votes
0answers
282 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
94 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 ...
4
votes
0answers
113 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 ...
3
votes
0answers
37 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
3
votes
0answers
41 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...
3
votes
0answers
41 views

maximizing the inverse degree in a graph

The inverse degree in the graph $G$ is defined as \begin{align*} r(G) = \sum_{i=1}^N \frac{1}{d_i}, \end{align*} where $d_i$ is the degree of node (vertex) $i$. Is the connected graph with maximum ...
3
votes
0answers
90 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, ...
3
votes
0answers
282 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
0answers
143 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 ...
2
votes
0answers
35 views

What are the automorphisms of an $n$-regular tree?

Let $T$ be the connected tree in which each vertex has $n$ neighbors. (So $T$ is infinite.) What is the full automorphism group of $T$?
2
votes
0answers
43 views

Number of nodes with even offspring

I've been working on a combinatorics assignment, and while the last few questions had clever solutions which didn't involve functional equations and the use LIFT, I fear I'm at my end. Given a ...
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
0answers
67 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
640 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
101 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
91 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
74 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
33 views

Find tree diameter or center

I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter: Take random vertex A Find such vertex B, that distance to it is maximal Find such vertex C, ...
1
vote
0answers
53 views

Proof of existing path on Depth-First-Search spanning tree

Let $G$ be an undirected connected graph, and $T$ the directed spanning tree of $G$, which I got by performing a DFS on $G$. If $H$ is a complete subgraph of $G$, how can I proof that there a path in ...
1
vote
0answers
257 views

Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time.

So we have a graph $G$ with its edges colored by red and blue. we are asked to find a deterministic linear time algorithm that given a parameter $K$ finds a spanning tree of G using exactly $K$ red ...
1
vote
0answers
13 views

For which graphs do depth first and breadth first produce identical spanning trees?

Is this possible?If yes, what are the conditions it should meet?
1
vote
0answers
119 views

Software/Applet to Draw Tree Diagrams (for Enumeration Problems)

I need a software/applet/flash file which easily draws tree diagrams for simple enumeration problems: I want to give number of the vertices in each layer, and it draws the diagram which shows all the ...
1
vote
0answers
36 views

automorphism of a rooted tree

Nowadays i'm working with tree automorphisms. I couldn't find information about rooted tree automorphism concerning the root. Does an automorphism of a rooted tree fix the root or not? Logically it ...
1
vote
0answers
117 views

Generating Function for edge-rooted labelled trees

Let $T_v(z)$ be the (exponential) generating function for vertex-rooted (non-plane) trees. Im trying to construct the generating function $T_e(z)$ for edge-rooted trees from this. I know the ...
1
vote
0answers
100 views

Binary Tree and Geometric Distribution

I have the following algorithm for "constructing" a binary tree: A probability $p_g$ for elongation, i.e. adding an edge A probability $p_b$ for branching, i.e. adding to a node two "child" edges ...
1
vote
0answers
189 views

Binary Tree and Overhead fraction Caluculation

Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes: 2) Only leaf nodes store data; internal nodes store two child ...
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.
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
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 ...
1
vote
0answers
58 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
47 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
200 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
54 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
213 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
90 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
45 views

prove that for all h in N, a height balanced tree has a height of at least 1.6^h

prove that for all h in N, a height balanced tree has a height of at least 1.6^h. Can this be proven by induction?
0
votes
0answers
19 views

Pascal's Identity and Trees

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
0
votes
0answers
14 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
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
0answers
28 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
0answers
21 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
0answers
42 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
29 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
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?