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

3
votes
1answer
3k views

How to draw all nonisomorphic trees with n vertices?

I have a textbook solution with little to no explanation (this is with n = 5): Could anyone explain how to "think" when solving this kind of a problem? (for example, drawing all non isomorphic ...
0
votes
0answers
70 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$ ...
4
votes
1answer
425 views

How many vertices of degree 3 or more can a tree have at most?

It is known that a tree $T=(V,E)$ has at least $\Delta$ leaves, where $\Delta$ is the maximum degree of $T$. But how many vertices of specific degree at least $k$ can a tree have at most? I'm ...
0
votes
2answers
46 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 ...
2
votes
2answers
66 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
26 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:
3
votes
2answers
996 views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
1
vote
0answers
12 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
77 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
67 views

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

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 ...
2
votes
0answers
88 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 ...
0
votes
1answer
28 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
16 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
50 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 ...
1
vote
0answers
41 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
80 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
136 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
2answers
80 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
119 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
28 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
142 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
35 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
26 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
57 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
34 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
23 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
28 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 ...
1
vote
0answers
26 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
50 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
117 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
1answer
165 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
543 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
133 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
87 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
52 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 ...
5
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
51 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
230 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
235 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
64 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.
1
vote
1answer
101 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
74 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
45 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
196 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 ...
-1
votes
1answer
90 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 ...