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,903
questions
0
votes
0
answers
17
views
Why is it that two labeled trees being identical is not the same as two isomorphic trees? [closed]
Why is it that two labeled trees being identical is not the same as two isomorphic trees? Couldn't you just say those two graphs are isomorphic? Maybe I am misunderstanding the definitions.
0
votes
0
answers
17
views
About using Young tableaux to find non isomorphic trees on N vertices
In these days I dive in combinatorics to estimate the class of non isomorphic trees on N vertices.
After a while I realized this sounds me really similar when using Young Tableaux on permutation ...
0
votes
1
answer
20
views
Special Aronszajn tree actually has continuum cardinality?
Wikipedia gives the following construction of a special Aronszajn tree. Supposedly, this tree has $\aleph_1$ nodes, as each level and each branch is countable. However, it seems to me that this ...
- 4,760
-1
votes
0
answers
11
views
Prove or disprove: (a) If G is a graph of order n and size m with three cycles, then m ≥ n + 2. (b) There exist exactly two regular trees. [closed]
How to prove or disaprove:
(a) If G is a graph of order n and size m with three cycles, then m ≥ n + 2.
(b) There exist exactly two regular trees.
Any help is appreciated.
- 1
0
votes
0
answers
22
views
Graphs with average degree $t$ embed all trees with $t$ vertices
I want to prove the following:
A simple graph with average degree at least $t$ contains all trees on $t$ vertices as a subgraph.
I tried proving this by induction. I first showed that if a graph $G$ ...
5
votes
3
answers
100
views
Proving the sum of length of a unique path in a tree is less than equal to $n$ choose $2$.
I am having trouble on trying to prove this statement using induction. Given a tree with $n$ vertices with $n \geq 2$. $x$ is a fixed vertex, for each $v$ in the vertex set, $d(v,x)$ is the length of ...
- 81
0
votes
1
answer
54
views
Average Distance Between Two Nodes In An Unweighted Tree
Given a random unweighted tree with $n$ vertices, what would be an average minimal distance between two of its vertices?
To put it in a more formal way, let's denote the set of all trees with $n$ ...
-1
votes
0
answers
28
views
Does a minimum spanning tree has the lowest maximum weights among all spanning trees? [closed]
Say that we have G, an undirected connected graph that has a positive weight for each edge. Let a spanning tree T be the minimum spanning tree (MST) for G, and we define the maximum weight (MW) of a ...
- 17
1
vote
0
answers
26
views
FUSF /neq WUSF, 3-regular Tree, effective Resistance
My professor gave an example of a 3-regular tree where the Wired Uniform Spanning Forest (WUSF) is not equal to the Free Uniform Spanning Forest (FUSF), but I'm having trouble understanding the ...
- 11
1
vote
0
answers
33
views
Fault Tolerant MST
Consider a graph $G=(V,E)$ and an MST of $G$. I am wondering how many edges I need to store, to make the MST tolerant to edge failures.
If there is only one edge failure, I require at most $n-1$ edges ...
- 41
2
votes
1
answer
38
views
Proving that an acyclic graph with $n$ vertices has $\leq n-1$ edges
By the handshake rule, $∑\deg(v) = 2|E|$. Each tree in a forest has at least one leaf node (a vertex with degree $1$). Therefore, the sum of the degrees of all vertices in the graph is at most:
$$∑\...
- 21
4
votes
3
answers
223
views
Random walks on regular trees
An infinite $d$-regular tree is a graph where every vertex has degree $d$ and
there are no cycles. Suppose we define a standard random walk $X_n$ on such a tree. Is the claim that $X_n$ is transient ...
- 629
-2
votes
0
answers
9
views
The amortized complexity of visiting $m$ keys in order in B-tree with $N$ items
I read a paper that said the amortized complexity of visiting $m$ keys in ascending order in a $b$ tree with $N$ keys is $O(1 + \log(N/m))$. I am wondering why it is not $O(1 + (\log N)/m)$ because ...
1
vote
1
answer
34
views
Sums over all paths in rooted trees over random draws
We are given two rooted trees $T_1, T_2$ which have the same depth $d$, and for each leaf there is a path to it of length $d$ from the root. Also, assume the number of children for each node is ...
- 843
1
vote
1
answer
55
views
Is it decidable if two structures are isomorphic?
Suppose that $S$ is a nested set and let $S_E$ be the set of "pure" elements (that is, elements of $S$ that are not sets). For example, if $S=\{a,\{a,b,c\}\}$ the "pure" elements ...
- 405
0
votes
0
answers
47
views
Exponential generating function for counting ordered and unordereed trees
I do not really know how to come up with the exponential generating function for counting trees.
Generally I want to discuss labelled rooted trees, such that every node has either 0, 1 or 2 children.
...
- 69
1
vote
0
answers
23
views
The definition of a maximal tree as a 1 dimensional cw-complex
In Hatcher's - a maximal sub-tree in a graph is defined as a contractible subgraph that reaches all the vertices.
Later he shows that this definition is equivalent to a cycle-free connected graph - ...
- 33
2
votes
2
answers
49
views
Intuition behind $2i+1\ 2i+2$ formula for converting array to a complete binary tree
I have tried really hard to come up with the formula for converting an array of elements to a binary tree, but I have failed.
I need some help understanding the intuition behind how the formula $2i+1\ ...
- 957
0
votes
0
answers
36
views
What is a 1-tree bound?
What does it mean exactly to find 1-tree bound? Is it an optimal TSP tour? and how would one find find an even better lower bound tour than the optimal one? is it possible?
Thanks to all who can ...
- 101
-1
votes
1
answer
32
views
Maximum weight forest?
If I have a graph and I need to find a maximum weight forest, but because a graph is already a forest, is it enough to find the maximum spanning tree?
thanks to anyone who can help
- 101
1
vote
0
answers
48
views
Edmonds branching algorithm
Can anyone in very simple terms explain what is and how to perform the Edmunds Branching algorithm.
So far I know you need to have a spanning tree rooted at r (a set of n-1 edges containing paths from ...
- 101
0
votes
0
answers
42
views
Proving that the tree T contains at most k − 2 nodes of degree three or more.
Let G = (V, E) be an undirected graph and T a tree in G with k ≥ 2 leaves. Prove that
the tree T contains at most k − 2 nodes of degree three or more.
This is what I have:
k-2 = the number of internal ...
- 101
0
votes
1
answer
44
views
Maximum number of vertices in a connected graph
I've recently stumbled across a problem that states the following:
Given G a connected graph, $D$ the maximum shortest distance between
two vertices in in the graph and $\Delta > 2$ the maximum ...
- 485
0
votes
0
answers
32
views
Finding MDST in subgraph is enough for MDST problem in the original graph
Let $G = (V, E, w)$ be strongly connected graph. Show that there exists a subgraph $G′ = (V, E′, w)$ of $G$ with $|E′| \le 2(n − 2)$ such for every $r\in V$ , an MDST of $G′$ rooted at $r$ is also an ...
- 1
0
votes
0
answers
29
views
Algorithm to construct a graph with minimal spanning trees
I need an algorithm that constructs an undirected graph given all of its minimal spanning trees (bases of a matroid) to find circles in the underlying graph. Has anyone an idea how I can do that?
...
- 1
3
votes
0
answers
63
views
Binary Huffman encoding for uniform probability
I've been having trouble with a question regarding the Huffman algorithm under a uniform probability distribution.
Suppose we have $k$ symbols $\{x_1, x_2,\dots, x_k\}$, and $c_i$ are the respective ...
- 467
0
votes
0
answers
18
views
Structure to model multiple hierarchies on the same entities
Say I have a set of entities and multiple hierarchies based on them, each hierarchy modeling a different type of relationship. What would be a useful structure to model this scenario?
For instance, ...
- 81
1
vote
1
answer
38
views
Shortest path joining two paths on tree
Let $[a, b]$ and $[c, d]$ be two paths on a tree network with empty intersection. It is easy to observe that: The intersection of paths [x, y], where $x\in [a, b]$ and $y\in [c, d]$, is again a non-...
- 1,274
1
vote
1
answer
70
views
Number of balanced-parentheses sequences on $2n$ bits as $n$ grows large
The motivation to consider the sequences below comes from an efficient way to represent trees on $n$ nodes using $2n$ bits.
Let $n\in\mathbb{N}$ be a positive integer. Let us call $s\in\{0,1\}^{2n}$ a ...
- 2,676
0
votes
1
answer
47
views
What type of Tree/Graph/Multigraph is a syntax parse tree?
Consider a string $((A\lor B)\lor A)$
We can make an (informally defined) parse tree for this expression whose nodes are subformulas. The root node would be the full formula $(A \lor B) \lor A$ which ...
- 1,152
1
vote
0
answers
38
views
Calculating number of spanning trees of complete graph with each edge divided
When calculating the number of spanning trees of complete graph $K_n$ with adding an extra vertex to every edge, I've noticed that the number of spanning trees is always equal to:
$$n^{n - 2}*2^{n - 1\...
- 291
4
votes
2
answers
137
views
How to calculate number of spanning trees of $K_5$ with extra vertex on one edge?
Here we have $K_5$ complete subgraph that gives $5^3 = 125$ spanning trees (using Cayley's formula).
Adding one vertex to arbitrary edge, gives me this graph for example.
Using Mathematica, it gives ...
- 291
1
vote
1
answer
78
views
Graphs with a given number of edges and vertices of degree $3$
Original problem:
Let a $\Gamma$ be a set of all graph's G following rules: $V_G \subset \mathbb{N}$, $|E_G| = 303$ and $G$ has $151$ vertices of degree $3$. (Last condition means that G can have ...
- 65
0
votes
0
answers
56
views
Proving that if G is a tree that relative to the source vertex s then BFS (G) = DFS (G) = G
I'm trying to prove that if G is a tree that relative to the source vertex s then BFS (G) = DFS (G) = G.
I thought to assume the negative that BFS (G) = DFS (G) = T.
G and T are not same, then there ...
- 1
1
vote
1
answer
52
views
De-contracting minimum spanning trees
I'm thinking about how to prove the following statement on Wikipedia.
Assume an undirected graph with weights for each edge.
If $T$ is a tree of MST edges, then we can contract $T$ into a single ...
- 172
0
votes
0
answers
23
views
Proper definition of a full tree
When I've searched up online mostly I found the definition for full trees to be limited to a tree which has 0 or 2 children for each of it's nodes. Which is okay to understand but here is my dilemma.
...
- 162
0
votes
0
answers
17
views
Deletion in AVL trees
assuming that one has to delete the root of an AVL tree.
Does it matter which node replaces the root, say if it is the next smaller or next greater number than the root itself, as long as the AVL-...
- 431
0
votes
1
answer
81
views
Is $n^{n-2}$ the number of trees on $[n]$ where the sum of degrees of vertices is $2n-2$?
I'm trying to count the number of trees on $[n]$ given that $d_1,d_2,\dots,d_n$ are positive integers with $\sum_{i=1}^{n}d_i=2n-2$ and for $i\in[n]$ $\deg(i)=d_i$.
My thought process here is that ...
- 238
1
vote
1
answer
35
views
Trees and $K_{10}$
$(ii)$ Ignoring vertex labels, how many distinct trees are there with $5$ vertices? Draw each such tree, and justify your conclusion that there are no more.
$(iii)$ Choose one of the trees that you ...
- 1,007
1
vote
1
answer
41
views
Can a graph have multiple distinct minimum spanning trees?
I have the following undirected graph which has multiple edges that have the same edge weights, the question is it possible to find more than one distinct minimum spanning tree for the following graph?...
- 21
5
votes
1
answer
81
views
Finding the coefficients of the OGF of unary-binary trees
A unary-binary tree is a plane (unlabeled) tree where each vertex has $0$, $1$, or $2$ descendants. Find the OGF $M(z)$ for a unary-binary tree and show that its coefficients are $[z^n]M(z) = \frac{1}{...
- 3,564
0
votes
0
answers
37
views
Number of spanning trees obtained from $K_n$
Let $K_n$ denotes the complete graph with $n$ verticies labelled 1,2,...,n. I want to show that a number of spanning trees of the graph obtained by deleting m edges that are incident to the last ...
- 1
2
votes
1
answer
32
views
How to generate trees with 11 and 12 vertices (with diagrams)?
I looked at this thread, but I couldn't seem to understand how to use geng and nauty to generate trees and get the diagrams. I need to generate trees with 11 and 12 vertices and possibly with more ...
- 131
0
votes
1
answer
44
views
Discrete Mathematics - Trees and Relations Question
I am completely stuck on this multiple choice trees question. In this multiple-choice question, more than one option can be correct. I believe this is a trees question; if it is not, then I have gone ...
- 51
0
votes
0
answers
39
views
Reverse Induction on Graphs
I am currently trying to prove that for any tree, e=v-1, where e is the number of edges and v is the number of vertices. My first thought was to perform induction on the structure of the tree. Clearly,...
- 93
1
vote
0
answers
13
views
Hashing binary trees from permutations
Any permutation $P_n$ (we are talking about small $n$, since I have to generate all $n!$ ones for my work - tree costs - anyway) can be uniquely turned into a binary tree $T_n$ by starting with an ...
- 565
0
votes
1
answer
21
views
Choosing edge in Kruskal's algorithm to form MST
In the given picture, I was trying to form an Minimum Spanning Tree and I wonder if we can select the edge (FB) because it crosses an another edge (AG).
Thanks in advance.
- 111
0
votes
0
answers
31
views
Maximum height of a complete binary tree with $t$ terminal vertices (leaves).
Let $T$ be a complete binary tree with $t$ terminal vertices (or leaves). I want to know the maximum height $h_\max$ it is possible for $T$ to have. The only result I know is that if $T$ is a binary ...
- 1,776
1
vote
1
answer
32
views
Finding MST from Empty Set of Edges? [closed]
I was reading https://en.wikipedia.org/wiki/Reverse-delete_algorithm regarding finding MST in an undirected and connected graph G.
Where the algorithm works like this:
Start with graph G, which ...
- 21
0
votes
1
answer
42
views
How many subgraphs with exactly 6 edges can I make from a complete graph with 7 vertices?
Let the complete graph be unweighted and undirected. The subgraphs can be unconnected.
Edit (More detail): I'm trying to go about this by splitting it up into spanning trees and non-spanning trees ...
