# Tagged Questions

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.

20 views

### Number of nodes satisfying a certain property on a binary tree

Fix a large integer $M$ and construct a binary tree as follows. Assign the root node by the integer $0$. If a node is assigned the integer $n$ and $n \leq M - 2$, then $n$ has two children and ...
10 views

### Easy References for understanding Grossmann and Larson rooted trees?

I am an undergraduate student doing a project on rooted trees. I was wondering if anyone would know any easy to understand references that explains Grossman and Larson's Hopf Algebra on rooted trees? ...
64 views

### Finding the maximum length of a minimum spanning tree

Graph G has 4 vertices/nodes and 5 edges. It is also connected. Its edges have the following weights: 5, 8, 10, 16, 18. The minimum length for a minimum spanning tree of graph G would be ...
70 views

### Complete Graph with odd degree

It is known that the Complete Graph $K_n$ has $n^{n-2}$ spanning trees. The $K_{10}$ has $10^8$ spanning Trees. Now my question: How can I compute the number of spanning Trees with odd degree of its ...
27 views

### Evaluating an arithmetic abstract syntax tree [closed]

This might be very simplistic for this forum (apologies, if so). How does one evaluate the tree below. I am not looking for a solution, just assistance in how to evaluate it: I assume I start at ...
32 views

### Find a DFS,BFS spanning tree.

Is my answer right? I think I understood the definition of BFS and DFS spanning tree, but I'm not sure my answer is right. If it is wrong, please correct it.
43 views

### Permutation of keys inserted into a tree?

Give the fraction of permutations of the keys $A$ through $G$ that will, when inserted into an initially empty tree, produce the same Binary search tree as does $A$ $E$ $F$ $G$ $B$ $D$ $C$ ANSWER: (...
34 views

### Tree properties

I am reviewing Diestel's Graph Theory and we are asked to prove that the following are equivalent: (i) $T$ is a tree. (ii) Any two vertices of $T$ are linked by a unique path in $T$. (iii) $T$ is ...
42 views

### maximizing alpha-beta puning.

I was searching a more pertinent place to post artificial intelligence concerned question, but some results pointed me to similar questions posted here, thus I chose math.se, now let's get through ...
47 views

191 views

### Pythagoras tree bounding size

The Pythagoras tree is a fractal generated by squares. For each square, two new smaller squares are constructed and connected by their corners to the original square. The angle of the triangle formed ...
58 views

### Counting the numnber of (labelled and unlabelled) rooted trees on $n$ vertices with height $h$

As far as I know, the number of labelled rooted trees on $n$ vertices is $n^{n-1}$. Is there a known result for counting the number of (labelled and unlabelled) rooted trees on $n$ vertices having ...
34 views

### Number of ordinal trees (aka rose trees) with n nodes, of depth d, with l leaves [closed]

Is computing the number of ordinal trees (also known as "Rose trees") with $n$ nodes, of depth $d$, with $l$ leaves an open problem? I assumed at first that it was a known results but I could not ...
16 views

### Terminology for property of two branches of a tree

Consider a tree $T$. A branch $B$ of a tree $T$ is just a proper subtree of $T$ (that is a subtree $B \subset T$ and $B \neq T$). Lets consider $B_1$ and $B_2$, two branches of a tree such that $B_1$ ...
33 views

### Find total number of ways to disconnect the following graph

Find total number of ways to disconnect the following graph: $4$ $5$ $6$ $8$ My attempt: I've done manually to find possible disconnected sets of given graph. I guess it is should be $8$. ...
34 views

### Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. [duplicate]

Let $G = (V, E)$ be a finite graph. (A) Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. (B) Assume that $|V | = |E| + 1$. Find an example that $G$ is not a tree.
57 views

### Enumerate out-trees that include a set of nodes in a directed graph

Given a digraph A, and an N set of nodes in the digraph. I need to enumerate the set of out-trees that contain those nodes. Where all the the out-trees leaves terminate on a node in set N. EDIT: I am ...
14 views

### Algorithm for finding all maximum out-trees in a digraph

If we have a directed graph, and the graph contains subgraphs which are out-trees. We could find the set of out-trees, such that it does not contain any out-tree that is contained by another out-tree. ...
21 views

### KD-Tree implementation with lat/lon coordinates

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct ...
25 views

### Which of the following is NOT true for $G$?

$G$ is a graph on $n$ vertices and $2n−2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$? For every subset of $k$ ...
85 views

### Existence of $\lambda^+$ Aronszajn trees when $\lambda$ is regular and $2^{<\lambda}=\lambda$

While I was dealing with Aronszajn trees I found the following exercise from Kunen's old book. If $\kappa=\lambda^+$ and $\lambda$ is a regular uncountable cardinal and $2^{<\lambda}=\lambda$ ...
17 views

### Binary Heap Question interpretation

In the question in the link below, how do I tell weather to draw out a binary min heap or a binary max heap? Am I misunderstanding the question? Binary Heap Question
27 views

### Fundamental group of cylinder -triangulation method

Is this correct? Can we conclude that the fundamental group is trivial since there are no remaining generators on 1-simplices?
20 views

### Fundamental group Klein Bottle triangulation

I have been trying to find the FG of the Klein bottle, and I was wondering if someone could verify that this process is correct. After triangulating it, I then found a maximal tree (shown in yellow) ...
39 views

### Fundamental group of the sphere via triangulation

I know that the fundamental group of the sphere is zero, i.e. $\pi(S^2)=0$ I want to show this by triangulation, i.e: Triangulate the sphere Draw maximal tree Draw maximal contractable subspace ...
41 views

### Fundamental group of a tree?

Find the fundamental group of the space $C(T)=\{(x,y) \in T \times T \mid x\neq y\}$. $C(T)=\{(x,y) \in T \times T \mid x\neq y\}$ where $T$ is a graph $T$ is the graph made of $3$ edges with a ...
18 views