# Questions tagged [trees]

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.

1,805 questions
Filter by
Sorted by
Tagged with
27 views

### Add an edge to a planar graph and preserving planarity

I’m not sure this is the correct StackExchange section. Let me know if I have to change I’m wondering if, given a planar graph $G$ And two vertices $v,u$, is there an efficient algorithm to know if ...
68 views

26 views

### Branches evaluation in infinite binary tree

I have been thinking about a proposition on infinite trees, which seems to be false but I can't find any counterexample. The problem : Let $T$ be an infinite binary tree, where all nodes are of ...
1 vote
20 views

### Combinatorics, 2-Tree, Sequence

I've just thought about a combinatoric problem. Say you have a tree with $n$ nodes at the $n$-th level ($2$-tree). Number elements based on their position left to right, top to bottom. Let $a_{n,i}$ ...
117 views

### I think I have discovered a new sorting algorithm using binary search tree. [closed]

If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
8 views

### Let $X,Y,Z,W$ be words with vector frequency $(x,y,z,w)$ , Find an optimal code.

Let $X,Y,Z,W$ be words with vector frequency $(x,y,z,w)$ such that $x\leq y\leq z\leq w$. Find certain requirements about $x,y,z,w$ such that $W=00,Z=01,Y=10,X=11$ is an optimal code. My solution : ...
1 vote
10 views

### Is there a efficient way to find only the combinations of interest from V exciting in P [closed]

Is there a efficient way to find only the combinations of interest from V exciting in P I have a list of something like this. V = [2,3,5,7,9,12] Size of V can be ...
1 vote
63 views

### How can I show that for each $e = uv \in F_0$ we have $H[F^* \cup e]$ contains a cycle

First, I present some definitions. Let $G$ a graph. For each $Z \subseteq E(G)$, we denote the graph $G[Z]$ by the $(V(G), Z)$. Let ${\cal P}$ a partition of $V(G)$. Define the graph $G_{\cal P}$ ...
9 views

### Root sub-trees of 2-3 tree

Suppose there is a $2-3$ tree with $n$ nodes. Each node in the left sub-tree of the root has $3$ children. (except the leaves). Each node in the right sub-tree of the root has $2$ children. (except ...
47 views

### What is a convex combination of graphs?

For example in this paper, they refer to a "convex combination of trees" (pg. 2, first paragraph), and also, more generally, to "convex combination of graphs" (pg. 2, footnote). -&...
11 views

### algorithm for finding two disjoint generating trees in a graph

I am studying shannon's switching game, in particular Lehman's results for necessary and sufficient conditions of join and cut win. The proof uses two disjoint generating trees and known results for ...
23 views

### nullspace of matrix "related" to incidence matrix of a tree

A signed incidence matrix $A$ of size $n-1 \times n$ obtained for a tree with $n$ vertices has full rank. Now, if I replace each entry $a_{ij} = +1$ in $A$ with some $\alpha_{ij} > 0$, will this ...
1 vote
41 views

### connected Graph with $n$ vertices and $n-1$ edges contains unique $u-v$ path

Let $G$ be a graph with $n\geq 1$ vertices and $m$ edges. Prove: $G$ is connected and $m=n-1 \implies$ $G$ contains a unique $u-v$ path for every $u,v\in G$. How can i prove this? It is clear that ...
55 views

### Algebraic tree-based problem

Mathematics! I have encountered a one problem that is being solved by using an algebraic (I guess?) tree with a following structure: _ _ _ _ 16 _ _ _ _ _ _ _ 8 _ 8 _ _ _ _ _ 4 _ 4 _ 4 _ _ _ 2 _ 2 _ 2 ...
18 views

### Prove that the number stored in the root of AVL tree is $2^{\left \lfloor{\log_2(n / 3)}\right \rfloor + 1}$

The question I am having trouble with: For $n \geq 3$, let $T_n$ denote the AVL tree obtained by inserting the numbers 1, 2, 3, ..., n, in this order, into an empty AVL tree. Prove that the number ...
74 views

### Find a simple path in given tree with minimum number of edges

Suppose given a Tree $T=(V,E)$. Each nodes in $T$ has a degree at most two. Also, edges in $T$ has weight distinct and positive natural. Suppose $|V|=n$, our goal is find a simple path with length ...
25 views

### Calculate nodes of the parse tree [closed]

Suppose that G is a context free grammar with productions that may have epsilon as the right side. If w is in L(G), the length of w is n, and w has a derivation of m steps, Show that a parse tree for ...
1 vote
51 views

### Overlap between the maximum spanning tree and largest edges of a bipartite graph

Given $K_{m,n}$ a bipartite graph, what is the expected fraction of overlap that the set of the top/largest m+n-1 edges would have with the maximum spanning tree (MST) of the graph? Naively it has to ...
8 views

### alpha beta pruning for multiple players

I have just finished implementing the min-max algorithm for a three-player game. I currently want to implement alpha-beta pruning but I, unfortunately, am unable to find any clear methods on how to ...
125 views

### Define a perfect $N$-ary tree in math notation as a set of series

Let's say I have a perfect $N$-ary tree of depth $=2 (M)$ and each parent node has children $=3 (N)$, and each parent-child relation is weighted, so it looks as a weighted unidirectional graph, with ...
1 vote
26 views

### Prove there are at least m minimum spanning trees

I just encountered a question of the MST: Assume $G$ is a weighted connected graph, and there is a cycle $C$ of length $m$, and the weights of these $m$ edges are all equal to the minimum value of ...
1 vote
20 views

### Is there anything known about the tree width of the direct sum of two graphs?

So, if you have two graphs (both with a designated edge), you could take the direct sum of those two graphs, where you glue those two graphs to each other along the designated edge. I think different ...
15 views

### Tree with maximum degree k

Prove that any tree T = (V, E) with maximum degree k must have at least k vertices with degree 1. (Hint: You may use the fact that every tree T = (V, E) with |V| ≥ 2, has at least two vertices of ...
50 views

38 views

### Real tree and simplicial tree

A real tree is a metric space $(X,d)$ such that for any points $x,y\in X$ there is a unique path from $x$ to $y$, and which is a geodesic. Equivalently, it is a $0$-hyperbolic space. A simplicial tree ...
28 views

### How do you proove that TREE(3) is finite in layman terms?

Apologies in advance. I am just a layman who knows about ordinals and know about TREE(n) but I don't know how to prove it is finite. Is there a simple transfinite ordinal proof? I don't know anything ...