Tagged Questions

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

2
votes
1answer
17 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
40 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
22 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
14 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
57 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
53 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
26 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
18 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
38 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
24 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
66 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
105 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
38 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
87 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
37 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
11 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
17 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
46 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
30 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
16 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
20 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
60 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
30 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
108 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
37 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
0
votes
1answer
40 views

Infinite Search Tree Probibility

I have a question on Search Trees. I have a balanced, infinite, search tree. If you check a node at level $l$, the probability of finding a solution at that node is $p^l$. Questions The first ...
0
votes
1answer
63 views

Prove through structural induction that a binary tree has an odd number of nodes

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes. I dont know how to get started with this ...
0
votes
0answers
39 views

Proof by Induction for Splay Tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay tree ...
5
votes
1answer
188 views

Graph Min Cut Problem

The idea is to give an Flow Network in which the minimum cut goes through a lot of edges. So adding one unit to each edge will change the min cut. The following figure, as a counter example, shows a ...
0
votes
0answers
24 views

Exactly one minimum spanning tree

A all edges in a graph of n vertices have differing weights. How can I prove that there is exactly one minimum spanning tree?
1
vote
1answer
55 views

$k$-connected graphs containing trees

I've encountered the following problem in the book "Graphs and Digraphs" and I'm not sure how to do it. Show that every $k$-connected graph contains any tree of order $k+1$ as a subgraph.
0
votes
0answers
14 views

Trees and Leaves (Graph Theory)

Let $T$ be a tree with $l$ leaves and $k \in \mathbb{Z}^{+}$ with $2k \geq l$. I need to show that there exists paths $P_{1}, P_{2},...,P_{k}$ such that: (i) $P_{1} \cup P_{2} \cup ... \cup P_{k} = ...