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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user avatar
  • 335
2 votes
1 answer
68 views

An Exercise in Graph and Set Theory

Exercise. Let $n>2$ be a natural number. Define the simple graph $G_n=(V,E)$ as follows: $$V=\{A\subset\{1,2,...,n\}:|A|=2\}\ , \{A,B\}\in E\iff A\cap B=\emptyset. $$ For which values of $n$ is $...
user avatar
1 vote
0 answers
23 views

How many ways can we extend a partial order of a rooted tree to a total order?

Consider a rooted tree $\mathcal{T} = (T,\rho)$, where $T=(V,E)$. Given $v_1,v_2 \in V$, $v_1 \preceq v_2$ iff the unique path from $\rho$ to $v_2$ contains $v_1$. We say that $v_2$ is a descendant of ...
user avatar
  • 1,035
0 votes
1 answer
32 views

Adding $k$ edges in a forest creates how many cycles?

Let $G = (V(G),X)$ be a forest. Let $F$ a edge set such ends of each edge of $F$ are connected in $G$. Is true that to add the edges of $F$ create exactly $|F|$ cycles? How can I argument this?
user avatar
  • 71
0 votes
1 answer
44 views

Let $\{w_i\}_{i=1}^n$ be an optimal code such that $\{p_i\}_{i=1}^n$ are words' probability.prove $p_i=p_j \implies |w_i|-|w_j|\leq1$.

Let $\{w_i\}_{i=1}^n$ be an optimal code such that $\{p_i\}_{i=1}^n$ are words' probability. I have to prove the fact that $p_i=p_j \implies |w_i|-|w_j|\leq1$. I read about binary Huffman codes and ...
user avatar
  • 1,561
3 votes
1 answer
55 views

Spanning trees of specific graph

Let H be graph obtained from $G$ by replacing every edge by path of length $k$. Find number of spanning trees of graph $t(H)$ in terms of number of spanning trees of $t(G)$. I noticed if $G$ is tree ...
user avatar
  • 342
1 vote
0 answers
28 views

How can I that if $\operatorname{part}(G'[A])=\operatorname{part}(G'[B])$, then $\operatorname{part}(G[A])=\operatorname{part}(G[B])$

Before of all, I do some necessary definitions. Let $G$ be a graph. For each $X\subseteq E(G)$, we denote the graph $G[X]=(V(G),X)$ (observe that $G[X]$ is a subgraph of $G$). Moreover, define by the $...
user avatar
  • 71
0 votes
0 answers
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 ...
user avatar
  • 23
1 vote
0 answers
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}$ ...
user avatar
2 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 : ...
user avatar
  • 1,561
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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}$ ...
user avatar
  • 71
0 votes
0 answers
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 ...
user avatar
  • 1,561
0 votes
1 answer
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). -&...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1,043
1 vote
1 answer
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 ...
user avatar
  • 77
0 votes
2 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
  • 11
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
5 votes
1 answer
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 ...
user avatar
  • 151
1 vote
0 answers
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 ...
user avatar
  • 23
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
50 views

matlab coding - finding shortest path problem

Lately I've been trying to learn MATLAB and there's this project that have been assigned to me which I'm trying to do. the description of the project is as follows: we have a set of 100 points: $${(0,...
user avatar
  • 154
0 votes
1 answer
28 views

Number of labelled rooted plane trees

I am trying to get the number of labelled rooted plane trees using symbolic method. For unlabelled rooted plane trees i use $\mathcal{T}=\zeta \times \mathcal{S}(\mathcal{T})$. Then $t(z)=z\frac{1}{1-...
user avatar
5 votes
1 answer
79 views

Finding a spanning tree with at least 100 leaves

I have the following graph theory problem: In a country there are pairs of towns connected by roads in such a way that you can get from any town to any by those roads. The president of the country ...
user avatar
  • 121
0 votes
1 answer
39 views

A combinatorial problem of counting path weights with a special symbolic binary tree

Consider two symbols, $X$ and $Y$. Symbol $X$ spawns $X$ and $Y$ -- think of the spawning as a binary tree rooted in $X$ with two leaves. The path weight for leaf $X$ is $a$ and that for leaf $Y$ is $...
user avatar
0 votes
0 answers
33 views

Cayley's formula for the number $T_n$ of labelled trees with $n$ vertices

I was reading about Cayley's formula for the number $T_n$ of labelled trees with $n$ vertices .The book describes a way for finding a formula for $T_n$" The solution basically goes this way: A ...
user avatar
  • 579
0 votes
0 answers
30 views

(proof clarification) - ( E, $\mathscr{F}_G$) is a matroid

I'm having trouble understanding why we make the assumption in the highlighted part of the proof, any help would be appreciate, thanks. Proposition. $\forall G = (V,E)$ undirected graph, the pair $(E,...
user avatar
1 vote
1 answer
50 views

Removing edges of tree in a forest and adding others edges to the same set of vertices of the tree

I am tryng show the following result: Let $F$ a forest and $T_1$ a tree with $T_1 \subseteq F$(subgraph of $F$). If $T_1'$ is a tree with $V(T_1') = V(T_1)$, then $F-E(T_1) \cup E(T_1')$ is a forest. ...
user avatar
  • 71
1 vote
1 answer
44 views

Prove that an undirected connected graph $G$ contains an Euler circuit by some properties of its fundamental cut-set matrix and connectivity.

Let $G$ be an undirected connected graph. $\forall v∈V(G)$, $G-v$ (remove the node and all of its relevant edges from the graph) is still a connected graph. Besides, the fundamental cut-set matrix $S$ ...
user avatar
0 votes
1 answer
32 views

Find minimum weight of tree of graph

Given a connected graph with $|V| = 10$ and $|E| = 20$, with $3$ edges of weight $3$, $4$ edges of weight $4$ and the remaining of weight $9$. What is the lowest weight in the subgraph spanning tree ...
user avatar
  • 593
0 votes
1 answer
34 views

Are two graphs isomorphic if: every spanning tree of one graph is isomorphic to some spanning tree of the other, and vice versa? [closed]

Let $G_1,G_2$ denote two simple graphs, and $T_1,T_2$ denote their respective set of all spanning trees. Are $G_1,G_2$ isomorphic if every $t \in T_i$ is isomorphic to some $t' \in T_j$ for both $i,j \...
user avatar
  • 135
0 votes
1 answer
41 views

Number of different minimum spanning trees in the graph

Let $G$ be a complete graph with $2n\ge6$ vertices. All edges in the graph have weights $2$, except the edges in the following cycles $$v_1,v_2,...,v_n,v_1, \qquad v_{n+1},v_{n+2},...,v_{2n},v_{n+1}$$...
user avatar
  • 157
2 votes
3 answers
199 views

Connection between two trees

Given a tree $T_1 = (V_1, E_1)$ (so a connected acyclic undirected graph is the definition I'm working with) and another tree $T_2 = (V_2, E_2)$, is it true that given any node $v \in V_1$ in $T_1$ ...
user avatar
2 votes
2 answers
72 views

If no cycle in graph $G$ contains edge $e$, then every spanning tree of graph $G$ contains $e$.

Let $G$ be a connected graph. Prove that the following statements are equivalent: $(i)$ $G-e$ is not connected. $(ii)$ No cycle in $G$ contains edge $e$. $(iii)$ Every spanning tree of $G$ contains $...
user avatar
  • 77
0 votes
1 answer
69 views

An interesting game "The Truel"

There is an interesting paper called The Truel. It is about 3 players A , B and C shooting under some rules.The two snippets of the pages relevant to my Question are given below, the full paper is ...
user avatar
  • 3,578
1 vote
1 answer
45 views

Number of trees on $n+k$ vertices that do not contain edges that are only between first $n$ vertices

So say I have $n$ black vertices $\{x_1,\dots,x_n\}$ and $k$ white vertices $\{y_1,\dots,y_k\}$, I want to count the number of trees that do not contain any edge of the type $(x_i,x_j)$. I have ...
user avatar
2 votes
2 answers
38 views

Possible bayes theorem question regarding a shared car

The question: Suppose 2 friends share the use of a car evenly, we will call the two friends Roger and James, respectively. We know that Roger will only use the car to drive to the grocery store, on ...
user avatar
0 votes
0 answers
80 views

Monte Carlo Tree Search

You are to manually run the MCTS algo- rithm for the navigation example covered in class for 10 iterations. For this, you will need simulation results for nodes at tree depth up to 2, which is ...
user avatar
  • 23
1 vote
1 answer
42 views

An identity for rooted plane labelled trees

I wish to prove combinatorialy that $$\frac{1}{1-\sum_{n=1}^{\infty} \frac{(n-1)^{n-1} z^n}{n!}} = \frac{T(z)}{z}$$ where $T(z)= \sum_{n=1}^{\infty} \frac{n^{n-1}z^n}{n!}$. $T(z)$ is the exponential ...
user avatar
4 votes
0 answers
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 ...
user avatar
  • 41
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
15 views

Function of the Degree Centrality in Tree Graphs

Determine the normalised degree centrality of the nodes in some random trees. What do you observe? E.g., is there some function of the degree centrality that is constant across your examples? I've ...
user avatar
  • 1
1 vote
1 answer
38 views

Is this a total ordering of the set of full labelled binary trees? [closed]

Consider a binary tree labelled by some ordered set of letters. Traversing the tree in preorder determines a sequence of letters - a word. A binary tree is called full if all its non-leaf vertices ...
user avatar
  • 316

1
2 3 4 5
37