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

0
votes
1answer
45 views

Graph theory and tree company

I appreciate anyone who answer this question and I anyone who design appropriate graph.
3
votes
0answers
63 views

a problem about finding an algorithm for a spanning tree in a 3-regular graph

"Consider the connected 3-regular graph G. Find an algorithm that produces a subgraph S of G which is a spanning tree and if you remove S from G then G is divided into some components that each of ...
0
votes
1answer
12 views

Tree Traversal-Is the order ascending?

I have a question about the traversal of a tree. When we print the values of a binary search tree using in order traversal are the values printed in an ascending order??
1
vote
1answer
28 views

Spectrum of infinite d-regular tree

Consider the adjacency matrix of the infinite d-regular tree, call it A. To find the spectrum we consider it as an operator in $L^2(V)$. It is stated that $A-\lambda I$ is always one-to-one. I do ...
0
votes
1answer
22 views

How many trees can be drawn using$n$ vertices without rebuilding isomorphs?

I'm told to draw all possible trees with exactly $6$ vertices. I was able to draw a maximum of $6$ trees. Any more were isomorphs of these $6$ trees. How can I determine if I have drawn all the trees? ...
2
votes
1answer
32 views

Why doesn't Tutte polynomial T(1,1) equal 0?

If the formula for a Tutte polynomial is: then how does T(1,1) solve for spanning trees instead of just returning a 0?
1
vote
1answer
19 views

Graph theory, trees, show T is subgraph of G

Let T be a tree with n vertices. G be a non-empty graph with $\delta$(G) $\ge$ n-1. Prove that T is a subgraph of G. If it's a tree then I know it has to be connected and if the minimum degree is ...
1
vote
0answers
26 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
0
votes
1answer
20 views

expression tree

I'm having some trouble understanding expression trees especially with putting this expression into a tree: S/P^Q^R Any help with how to do these is greatly ...
1
vote
1answer
44 views

A decision tree has an expected depth of at least $\log n!$

I am looking at the proof of the following theorem and I have some questions. The theorem is the following: On the assumption that all permutations of a sequence of $n$ elements are equally ...
0
votes
0answers
14 views

Number of partial trees of a complex graph

Demonstrate number of partial trees of a complex graph without a fixed edge is $(n-2)\cdot n^{n-3}$, for $n\geq 3$
0
votes
2answers
56 views

The decision tree has height at least $\log n!$

The proof of the theorem Any decision tree that sorts $n$ distinct elements has height at least $\log n!$ is the following: Since the result of sorting $n$ elements can be any one of the $n!$ ...
1
vote
3answers
33 views

The number of (non-equal) forests on the vertex set V = {1, 2, …,n} that contains exactly 2 connected components is given by

The number of (non-equal) forests on the vertex set V = {1, 2, ...,n} that contains exactly 2 connected components is given by $\sum_{k=1}^{n-1} {n-1 \choose k-1} k^{k-2} (n-k)^{n-k-2}$. I am unsure ...
0
votes
1answer
32 views

Find the number of trees on the vertex set V = {1, 2, …, 8} in which all vertices have degree 1 or 4.

I am unclear how to figure this out. I understand that if there were 6 vertices of deg = 1 and 2 vertices of deg = 4 then I can simply check if the degrees all add up to 2n-2 and use a specific thm: ...
0
votes
1answer
24 views

Existence of infinite subsequence of trees assuming two tree operations

Assume two operations on rooted trees: contract an edge: choose an edge $E$, join two vertices adjacent to $E$ grow a leaf: choose any vertex and connect it to a new leaf Starting with any rooted ...
1
vote
1answer
24 views

Existence of infinite subsequence of trees with a subtree contained in the sequence

Assume a statement: For every infinite sequence of rooted trees $\{T\}_{i=0}^\infty$ there is an index $j\geq0$ such that there are infinitely many trees in $\{T\}_{i=0}^\infty$ which contains ...
0
votes
0answers
23 views

Calculate the total cost

According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: Cost per level $i \to \left( \frac{7}{8} ...
2
votes
0answers
26 views

How can I infer order from partially ordered discrete sequences?

A really interesting problem that I can't stop thinking about! Have run in to this a couple of times but yet to find a smart approach to either solve or frame this problem. This is my try at ...
3
votes
5answers
194 views

Halting probability of random tree-generating algorithm

Suppose I have a tree-generating algorithm as follows. Begin with one root vertex. With equal probability, create either three subvertices or none. Recurse and repeat for each of the subvertices (if ...
1
vote
1answer
22 views

Partitioning a planar graph into spanning trees?

Suppose I have a simple, planar graph, which I want to partition into three edge sets such that each set forms a spanning tree. I've made an attempt at a solution, but it requires a few assumptions ...
1
vote
0answers
21 views

Help with proof about merge two heaps to one heap…

We have two heaps: $H_1,H_2$ that have $n_1,n_2$ elements ($H_1$ have $n_1$ elements and $H_2$ have $n_2$ elements). We know that the smallest element at $H_1$ is bigger the root (the biggest element) ...
1
vote
0answers
29 views

Probability and search Tree

I need some help with the following question. Given the random permutations of $ n > 2 $ numbers. Now, creating a binary search tree and puting it the organs one by one. Denote the input organs ...
1
vote
1answer
61 views

Graph and one Sequence challenge

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
0
votes
0answers
14 views

Is this a Red-Black Tree?

I tried to build RBT (Red-Black Tree) via this way: I build a balanced binary search tree (much as I can) and then colored it... Now the Q is: if this is a legal RBT? At my opinion is yes, because ...
0
votes
1answer
56 views

Proving number of edges in F = n - k

So if we let F = (V,E) be a forest with n vertices and k connected components (trees), how can I prove that the number of edges in F = n - k ? I was thinking of using induction, but I'm super lost. ...
2
votes
1answer
61 views

Preorder traversal, inorder traversal, postorder traversal

a) preorder traversal b) inorder traversal c) postorder traversal Ok, a) r,j,h,g,e,d,b,a,c,f,i,k,m,p,s,n,q,t,v,w,u b) a,b,d,c,e,g,f,h,j,i,r,s,p,m,k,n,v,t,w,q,u c) ...
0
votes
0answers
47 views

Finding spanning trees using Depth-First Search

I am wondering if root in spanning trees using Depth-First Search can have more than $2$ children? I know this is a silly question, but there is an example in the book which involves only $2$ ...
0
votes
2answers
34 views

Property of the numbering in preorder traversal of the tree

$v$ denotes the vertex which has been asigned the number $v$. The vertices are numbered in the order visited. In preorder all vertices in a subtree with root $r$ have numbers no less than $r$. More ...
0
votes
0answers
27 views

Findind diameter of minimum spanning tree in matlab

hello I am trying to find the diameter of a spanning tree using Matlab's function graphshortestpath().I have a 23 indices spanning tree and I want to find it's diameter. I use these parameters in a ...
2
votes
2answers
60 views

A tree on n vertices where every vertex has degree 1 or 4. Prove that n ≡ 2 (mod 3)

Let T be a tree tree on n vertices where every vertex has degree 1 or 4. Prove that n ≡ 2 (mod 3)
1
vote
0answers
21 views

How many pure trees with a fixed number of nodes exist?

How many pure trees of size (number of nodes) $n$ exist? Apart from having this fixed size, the trees can be arbitrary. The sequence starts like this: Here's the beginning of the sequence:
1
vote
0answers
11 views

Graph invariants for rooted trees

I'm looking for a few graph invariants (that have been studied before) that help distinguish rooted trees. I have a large, real-world collection of these graphs and I'd like to see what has been ...
0
votes
1answer
59 views

Increase by one all edges, Min-Cut, changes or not?

My Friends, as i ask a new question recently, Increase by one, Shortest path, changes the edges or not? i want to ask a related question as a new post Suppose we have a Graph G in which weight ...
0
votes
2answers
37 views

Increase by one, Shortest path, changes the edges or not?

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
0
votes
1answer
21 views

Merging of height balanced trees

$H_1$ and $H_2$ are two height balanced trees. How can they be merged such the time required for merging them is $O(\log n_1 + \log n_2)$ where $n_1$ and $n_2$ are the number of nodes in the trees ...
0
votes
0answers
12 views

Breadth First Search - Building All Possible Trees of a Set

Suppose there is a set of values arranged in a binary search tree (BST). I'm trying to write an algorithm that takes in a sequence, and prints all permutations (BSTs) that have that sequence as their ...
1
vote
1answer
41 views

Tree recursive question: number of nodes and relationship with children

Suppose a given tree T has n1 nodes that have 1 child, n2 nodes that have 2 children, . . . , nm nodes that have m children and no node has more than m children, how many nodes have NO child are there ...
0
votes
0answers
17 views

Oversampling and trees

I want to create a model to predict the propensity to buy a certain product. As my proportion of 1's is very low, I decided to apply oversampling (to get a 10% of 1's and a 90% of 0's). Now, I want to ...
2
votes
0answers
73 views

Can “tit for tat” strategy be defined in monadic second-order logic?

Prisoner's dilema game can be represented as a game tree, which could be infinite game with corresponding infinite game (binary) tree in common case. There is well-known tit for tat strategy, which ...
1
vote
0answers
27 views

Euclidean Minimum Spanning Tree Property

Is the following statement about Euclidean MSTs true, and if so could someone help me with a proof? Between any two nodes, the EMST minimizes the maximum edge cost of any edge required to traverse ...
1
vote
1answer
72 views

Number of spanning trees for these 2 figures

The solution to the number of spanning trees of the graph below is given by $6$ and $4 \times 4 - 1$ for Graph A and B respectively. I'm not sure how to get this. Please assist. I did ask a similar ...
1
vote
1answer
115 views

Number of spanning trees of this graph

The solution to the number of spanning trees of the graph below is given by $3 \times 2 \times 3 = 18$. I'm not sure how to get this. Please assist. Thanks! Notes: Just in case anyone was ...
0
votes
0answers
18 views

Suffix string starting at $i$

$S$ is the string of characters:TACGCGGT$ For string S and each of the positions $i=1,2,\dots,9$ write down the suffix string starting at position $i$. What is ...
0
votes
2answers
46 views

How many different heaps can we build from $n$ elements?

We the group $[n]=\{1,2,....,n\}$. How many heaps can we build for $n=4,5,6,7$?? Important: The question is not about the building heap algorithm, is about how many heaps can we built for each number ...
0
votes
0answers
20 views

Direct Graphs: Prove that for every rooted tree $G=(V,E)$ the algorithm computes a topological sorting of $G$. [duplicate]

Consider the following recursive algorithm for topological sorting of a rooted tree $G=(V,E)$: Apply topological sorting to the vertices in each subtree hanging from the root, and then order the root ...
0
votes
1answer
17 views

Question about consistency in the junction tree algorithm (graphical models

I have a question about consistency in graphical models. It is often stated that when running the junction tree algorithm on a clique (cluster) tree, the marginals of all nodes are locally and ...
4
votes
1answer
93 views

Exercise 1.1 in Serre's trees

I have in fact become stuck by the very first problem in Serre's book on Trees. It is a little bit embarrassing but ho-hum. I start with Serre's definition of direct limits. Let $(G_i)_{i \in I}$ be ...
1
vote
1answer
52 views

Proof: How many edges need be removed from this graph to produce the spanning tree?

Assume the graph,$G$ has the degree sequence $6,4,4,3,3,3,3,2,2$. How many edges must be removed from $G$ to produce the spanning tree $T$? We can construct this graph using Havel-Hakimi's ...
0
votes
0answers
19 views

Proof verification that two spanning tress of the same graph are the same size

Let $H$ be any graph and $T_1$ and $T_2$ be spanning trees for $H$. Prove that the size of $T_1$ equals the size of $T_2$. Proof: $T_1$ has an edge set ...
0
votes
1answer
32 views

Show this tree exists for n >= 3

I wonder if you guys can help me find an easier solution for this. Show that for every n >= 3 a tree exists with exactly n nodes and n - 1 leaves. My instructor had a solution that basically ...