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
116 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
287 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
39 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
43 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
42 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
95 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
148 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
36 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
77 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
68 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
652 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
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 ...
1
vote
0answers
41 views

Ordinals as Trees

I'm trying to understand countable ordinals and their tree representation. I understand that $\omega$ is the first "non branching tree" of infinite height. I also understand that the exponent of ...
1
vote
0answers
16 views

Proof for the number of leaves for any Binary Search Tree

A property for binary trees is that the number of leaves is the number of full nodes plus 1, in other words, $L = F + 1$ where $L$ is the number of leaves and $F$ is the number of full nodes. What ...
1
vote
0answers
37 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
54 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
273 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
126 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
37 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
118 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
107 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
249 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
51 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
218 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
8 views

Generating a binary minimum spanning tree

I need to derive a spanning tree from a given graph. Is it possible to generate a spanning tree which is a binary tree?
0
votes
0answers
4 views

Preparing data for WEKA decision tree J48

I'm trying to deal with WEKA and J48 algorithm. Looks like I have to present all my numerical values like age, income, height, weight as classes: age_from_18_to_25, age_from_26_to_40, e.t.c. Here is ...
0
votes
0answers
39 views

Proof by Induction for Splay Tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay tree ...
0
votes
0answers
24 views

Exactly one minimum spanning tree

A all edges in a graph of n vertices have differing weights. How can I prove that there is exactly one minimum spanning tree?
0
votes
0answers
13 views

Trees and Leaves (Graph Theory)

Let $T$ be a tree with $l$ leaves and $k \in \mathbb{Z}^{+}$ with $2k \geq l$. I need to show that there exists paths $P_{1}, P_{2},...,P_{k}$ such that: (i) $P_{1} \cup P_{2} \cup ... \cup P_{k} = ...
0
votes
0answers
17 views

mathematical formulation Minimum Cost Flow

I have a problem of minimum cost flow that can be defined as the following matrix. I want to solve it how a linear program (without using kruskal algorithms, prim etc). How can I formulate it like a ...
0
votes
0answers
13 views

Is my understanding of realtionship spanning trees and the cycle graphs correct

Any cycle graph C$x$ for example C200 would have only one spanning tree as a spanning tree would be the entire graph minus one edge. And the amount of ways can you remove just one edge from C200 ...
0
votes
0answers
49 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
21 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
17 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
41 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 ...