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

1
vote
3answers
23 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
10 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
18 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
27 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
41 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
22 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
32 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
42 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
26 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
15 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
58 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 ...
1
vote
1answer
56 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 ...
1
vote
2answers
27 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
39 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
16 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
71 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
25 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
67 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
110 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
39 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
15 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
14 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
88 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
40 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
18 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 ...
0
votes
1answer
12 views

How to prove that at Complete Binary Tree (CBT) at height $h$ we have $2^h$ leaves

I try to prove it by induction, please tell me if I'm right... The induction assumption - For every CBT at height $h$ there is $2^h$ leaves. The base of the induction is right (I'm writing this proof ...
0
votes
1answer
18 views

Proof of the number of the leaves in a full binary tree

I need to proof by induction that at full binary tree there are $\frac{n+1}{2}$ leafs if $|V|=n$. So, I won't write you the whole proof, just my idea, and I'd like to know if this OK... So we ...
0
votes
0answers
9 views

How to prove depth of a vertex is more than depth of its child on a rooted tree

I just read this question on a book, we define depth(X) = max{depth(Y) for all Y which is a child of X}+1 How can we prove it, it seems so obvious but hard to prove
0
votes
1answer
25 views

Definition of a tree and 2 cycles

I've run into a problem with the definition of a tree, and possibly more generally with the definition of a cycle. I've run into the problem a few sections after we talked about trees, and I never ...
0
votes
1answer
49 views

Convert a tree to a forest where every component has an even number of vertices.

I have the following problem, which I am struggling with. It asks to find the maximum number of edges to be removed from a tree to convert it to a forest, where every component will have an even ...
0
votes
0answers
22 views

Adding an edge to a MST generated from a distance matrix

Given an $N\times N $ distance matrix, but not an adjacency matrix for a connected, weighted, undirected graph $G$, I've managed to find a minimum spanning tree (with $N - 1$ edges) using Prim's ...
0
votes
0answers
13 views

If a distance matrix is that of a weighted tree

I am given a distance matrix of size $n \times n$. I need to determine if it can represent a weighted tree or not.
0
votes
0answers
38 views

Find kth largest element of heap.

Consider s binary heap containing n numbers(the root stores the greatest number). You are given a positive integer k < n and a number x. You have to determine whether the kth largest element of the ...
1
vote
0answers
19 views

Multiway tree to Binary Tree

A multiway tree T can be represented as a binary tree T~ by using the firstChild and nextSibling pointers. If we think of the firstChild link as being the left link and the nextSibling link as being ...
0
votes
0answers
25 views

Number of nodes in a B tree

In a B tree with minimum degree t, each non leaf node other than root has at least t children and at most 2*t children. Suppose that the keys {1,2,3...,n} are inserted into an empty B tree with ...
5
votes
1answer
65 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
0
votes
0answers
8 views

Generating a binary minimum spanning tree

I need to derive a spanning tree from a given graph. Is it possible to generate a spanning tree which is a binary tree?
0
votes
0answers
10 views

Preparing data for WEKA decision tree J48

I'm trying to deal with WEKA and J48 algorithm. Looks like I have to present all my numerical values like age, income, height, weight as classes: age_from_18_to_25, age_from_26_to_40, e.t.c. Here is ...
0
votes
1answer
31 views

Graphs that are almost trees

What's the name of rooted trees in which arbitrary connections between vertices of consecutive levels are allowed? (The level of a vertex is its distance to the root.) I.e.: All parents of a vertex ...
7
votes
2answers
109 views

Graph and in-Degree and Drawing

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
3answers
38 views

Acyclic graph must have a leaf

It is a theorem that every acyclic graph must have a leaf, ie. A vertex with degree 1 at most. Intuitively, it makes sense as any vertex with more degree would be connected to at least 2 vertices ...
1
vote
0answers
43 views

Ordinals as Trees

I'm trying to understand countable ordinals and their tree representation. I understand that $\omega$ is the first "non branching tree" of infinite height. I also understand that the exponent of ...
1
vote
1answer
23 views

Height of the tree : $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$

Let the tree described by $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$ Can someone explains why the height is $\log_{8/5}{n}$ I don't know how to proceed