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
2answers
64 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 ...
1
vote
1answer
91 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
23 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
1answer
25 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
131 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 ...
0
votes
0answers
21 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
34 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 ...
1
vote
1answer
23 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
53 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
1answer
30 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
0answers
21 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
26 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
151 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
25 views

AVL, keys where rotations are not required

Suppose the keys {1,2,3.....,n} are inserted into n empty AVL tree in sequence 1,2,3.....,n. Find the key values(1,2...n these are the keys) where rotation(rotations to balance the tree structure) is ...
1
vote
0answers
42 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 ...
5
votes
1answer
116 views

Killer Tree! (one of my old questions)

There is a problem that killed me! but I couldn't solve it: We have a tree graph witch its structure is what is on image. Proof that there is no reduplicative numbers in each line.
0
votes
2answers
159 views

All self-complementary trees [closed]

I am looking for all self-complementary trees. Could someone accompany me in this great adventure?
0
votes
1answer
139 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 ...
1
vote
2answers
496 views

Graph Theory(trees) problem?

I am practicing for my Discrete Math final and came across this question on trees in my textbook(Rosen). Suppose 1000 people enter a chess tournament. Use a rooted tree model of the tournament to ...
6
votes
2answers
126 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
1answer
32 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 ...
0
votes
3answers
76 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
50 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 ...
4
votes
2answers
5k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...
1
vote
1answer
25 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
48 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
213 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 ...
1
vote
1answer
229 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
67 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 ...
1
vote
1answer
63 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
29 views

mathematical formulation Minimum Cost Flow

I have a problem of minimum cost flow that can be defined as the following matrix. I want to solve it how a linear program (without using kruskal algorithms, prim etc). How can I formulate it like a ...
1
vote
1answer
92 views

Complete Binary Tree [closed]

A balanced binary tree is a full binary tree in which every leaf is either at level l or l-­1 for some positive integer l. The set of balanced binary trees is defined recursively by: Basis step: A ...
0
votes
1answer
66 views

Random Binary Search Tree, expected value of nodes with two children

In class, the professor showed that using a uniform random permutation $$ X_1,..., X_n$$ (each being i.i.d.) we can construct a Binary Search Tree by inserting the values in to the tree by their ...
0
votes
1answer
44 views

Calculating the average degree/valency of vertices

If I were to let T be a tree with n vertices, what would be the average degree/valency of the vertices in T? How would I go about calculating this?
2
votes
1answer
173 views

Proving that the height of a 2-3 tree is between $\log_3 N$ and $\lg N$

I am stuck on the problem of trying to prove the upper and lower bounds of a 2-3 tree. I think the most natural recourse is to use induction. However, my instructor told me that this was unnecessary ...
0
votes
0answers
16 views

Is my understanding of realtionship spanning trees and the cycle graphs correct

Any cycle graph C$x$ for example C200 would have only one spanning tree as a spanning tree would be the entire graph minus one edge. And the amount of ways can you remove just one edge from C200 ...
-1
votes
1answer
89 views

Finding a minimum weight spanning tree? [duplicate]

Letting W be the weighted graph created by taking a complete graph K5 on five vertices 1, 2, 3, 4, 5 with the weight of each edge {x,y} given by ({x,y})=x+y, How would I find a minimum weight ...
1
vote
0answers
27 views

Proof for the number of leaves for any Binary Search Tree

A property for binary trees is that the number of leaves is the number of full nodes plus 1, in other words, $L = F + 1$ where $L$ is the number of leaves and $F$ is the number of full nodes. What ...
0
votes
1answer
65 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
-1
votes
1answer
218 views

Question about trees, Let T be a tree with n vertices

Are my answers correct to these 3 questions? Let T be a tree with n vertices. 1) What is the average degree/valency of the vertices in T? Average Degree of of ...
0
votes
1answer
140 views

How many spanning trees does the cycle graph C2014 have?

How many spanning trees does the cycle graph $C_{2014}$ have? How do I create a bipartite graph and use it to solve this problem?
1
vote
1answer
98 views

Postorder and Preorder traversal on a Binary tree

For the tree below, list the labels of the nodes of the tree according to the pre-ordering algorithm, and then re-list them according to the post-ordering algorithm. ...
1
vote
1answer
42 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
0
votes
1answer
48 views

Spanning tree with unique paths.

Let $G$ be a connected graph and let $r∈V(G)$. Prove that $G$ has a spanning tree $T$ such that for every edge of $G$ with ends $u$ and $v$, either $u$ belongs to the unique path in $T$ with ends $v$ ...
6
votes
1answer
762 views

Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: ...
4
votes
1answer
37 views

Expected number of subtree removal in a tree.

I was solving this problem. In a gist the problem is as follows: You are given a rooted tree. On each step you choose a node randomly and remove the subtree rooted by that node and the node ...
0
votes
1answer
47 views

Normalization of data in decision tree

After reading through a few references, I have come to know that for machine learning in general, it is necessary to normalize features so that no features are arbitrarily large ($centering$) and all ...
0
votes
1answer
46 views

The intersection of $k$ subtrees of a tree $T$ is nonempty.

Let $T_1$, $T_2$, . . . , $T_k$ be subtrees of a tree such that any two of them have a vertex in common. Prove that they all have a vertex in common. Any hints/solutions are greatly appreciated. I am ...
0
votes
1answer
31 views

Find the node that we will reach with a given path on a graph (complete binary tree)

This question is regarding a special case of graph i.e. complete binary tree Consider the following tree :- ...
0
votes
1answer
61 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.