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
0answers
16 views

Binary representation of a Binary Tree leaf node congruent with path to reach it

So I know that if we count leaf nodes from left to right and 0-index them, and then transform those indices to their binary form (5 being 101, etc.), it translates to the path from the root to reach ...
0
votes
0answers
9 views

Changements that have to be done in order to delete node of red-black tree

According to my lecture notes: Let $x$ be the child of the node that we delete. Let $w$ be its sibling node and $p$ the father of $x$. There are four cases: At the first case, $w$ is red. We ...
3
votes
1answer
26 views

Identifying Binary Search Trees from their Prufer Sequence

If you ignore its root, a Binary Search Tree generated by some permutation of $\{1, \ldots, n\}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found ...
2
votes
0answers
23 views

Red-Black tree - “Insert-Delete” [on hold]

I am looking at red-black trees. Unfortunately in my lecture notes, the operations "Insert" and "Delete" are not well explained. Could you explain to me steps that we have to do for these two ...
1
vote
1answer
24 views

Determine if there is a node in a binary postorder anti-sorted tree with key $k$

A binary postorder anti-sorted tree is a binary tree for which the post-order traversal gives the keys that are saved at the nodes of the tree in descending order. Present a pseudocode for the most ...
0
votes
1answer
18 views

Is these Trees isomorphic or not?

Is these Trees isomorphic or not? They have same structure but they have different code. Because one of them is minimum code. Thank you for your answers in advance.
0
votes
1answer
25 views

Draw a 2-3 tree, insert and delete a key

Assume that at the nodes of a 2-3 tree, the following keys are saved (in an increasing order): $3,6,9,12,15,18,21,24, 27, 30, 33, 36$. It is also given that the root is a 2-node that contains the ...
1
vote
1answer
43 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
1
vote
1answer
21 views

Rotations after inserting element in AVL-tree

We want to insert $58$ at the following AVL-tree and then we have to make rotations so that the tree is balanced. According to my notes, we are at the case RL (The first edge leads to the right and ...
0
votes
3answers
13 views

Proving if $G$ has no cycles but by adding one edge between any two vertices will create a cycle then $G$ is a tree

Prove: if $G$ has no cycles but by adding one edge between any two vertices it will create a cycle then $G$ is a tree. Below is the definition we use for a tree. I don't see any way to connect ...
2
votes
1answer
23 views

Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children. I read that ...
0
votes
1answer
31 views

Let $G$ be a connected graph, then $G$ is a tree iff $G$ has no cycles

Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles. $\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles. ...
2
votes
0answers
38 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
1
vote
1answer
11 views

Prove in any tree with n vertices, the number of nodes with 3 or more neighbors is at most 2(n-1)/3

I know that the number of edges in the tree is n-1, and by the sum identity, the degree is 2(n-1)... I'm not sure how to go about completing the proof, or even starting it for that matter.
2
votes
1answer
22 views

Graph with fixed amount of spanning trees

"Find a graph with 8 vertices, which have exactly 27 spanning trees." How do I find such a graph, or prove one does not exist?
0
votes
0answers
20 views

Isomorphism testing for minimal SP-trees

I'm doing a bit of research on the SP-trees. I'm still new to this whole problematic, so I'd be thankful if someone cleared this thing up. :) This is the scenario that I'm trying to come up with a ...
0
votes
0answers
34 views

$T(n) = T(n/3) + T(2n/3) + cn$ - recursion tree with constance $c$

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac ...
0
votes
0answers
7 views

$k$-ary labeled trees with distinct labels

Classical definition of $k$-ary labeled trees doesn't restrict somehow the uniqueness of tree labels inside its branches. My question: Is any special definition (name) for such trees? To clarify ...
4
votes
0answers
18 views

Simple criteria to know if the p-nary notation of an integer can generate a tree by preorder traversing?

I am treating with a preorder tree traversal structure(which means sequences where the children of each tree node are listed behind it) now for some other problems and the structure is like: ...
0
votes
0answers
30 views

Polynomial time algorithm for finding the chromatic sum of a tree.

As the title goes, a polynomial time algorithm for finding the chromatic sum of a tree is required. NOTE: Finding the chromatic sum of a graph is also called the sum coloring problem - The sum ...
1
vote
1answer
28 views

If the inorder traversal of a binary tree produces ordered output, is the tree a binary search tree?

Given a binary search tree, it's easy to see that the inorder traversal returns values from the underlying set in order (according to the comparator that set up the binary search tree). My question ...
1
vote
1answer
12 views

Proof of a tree with a vertex of degree k and less than k vertices of degree 1

The question is : Does there exist a tree with a vertex of degree k and less than k vertices of degree 1? I tried a lot but it is impossible to find. There is no tree with a vertex degree k and less ...
0
votes
0answers
30 views

Prove graph is a tree

Prove: Graph is a tree if and only if every pair of two distinct vertices are joined by only one path, and the vertices of this path are all distinct. I can easily see on a diagram that this is ...
0
votes
1answer
45 views

What does $ \chi(Tree)\leq 2 $ mean in graph theory?

I am reading an article about graphs in English. Does $\chi(Tree)\leq 2$ mean that each node has no more then $2$ children?
0
votes
0answers
31 views

Efficient and Elegant Subword-Tree Construction - trouble understanding compact representation

I'm reading the paper "Efficient and Elegant Subword-Tree Construction" by M.T. Chen and J.I. Seiferas and I'm having trouble understanding their compact representation to a Subword-tree, especially ...
0
votes
2answers
78 views

Prim , Kruskal or Dijkstra

I've a lot of doubts on these three algorithm , I can't understand when I've to use one or the other in the exercise , because the problem of minimum spanning tree and shortest path are very similar . ...
2
votes
2answers
39 views

could a spanning tree graph be expressed by a lower triangular matrix?

Suppose a directed spanning tree graph $G$, there are $n$ nodes, and the root is node $1$. We express this graph by a matrix $M_{n\times n}$. If there is an directed edge from node $i$ to node $j$, ...
1
vote
0answers
26 views

About the topology of a $d$-regular tree

What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph? Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see ...
3
votes
3answers
131 views

How to calculate the expected maximum tree size in a pseudoforest

I would like to calculate the expected maximum tree size in a randomly generated pseudoforest of $N$ labelled nodes where self-loops are not permitted. Empty and single-node trees are also not ...
0
votes
2answers
62 views

Vertices of degree one and cut-edges

Please help solve following: Suppose that $v$ is a vertex of degree $1$ in a connected graph $G$ and that $e$ is the edge incident on $v$. Let $G′$ be the sub- graph of G obtained by removing $v$ and ...
2
votes
1answer
56 views

Is this random binary tree finite?

Consider the following procedure for generating a random binary tree: Starting with a full binary tree (i.e., each node has either two or no children) we iterate over the leaves and (independently) ...
1
vote
0answers
41 views

Expected Max Pseudotree Size

I'm working on a problem where I need to calculate the expected maximum pseudotree size in a randomly-generated pseudoforest with $n$ nodes. Expected maximum value is of course: $$ E(x) = ...
4
votes
1answer
74 views

Maps of primitive vectors and Conway's river, has anyone built this in SAGE?

I am attempting to teach number theory from John Stillwell's Elements of Number Theory in the upcoming semester. There are two sections (5.7 and 5.8) which describe the diagrammatic method for the ...
0
votes
1answer
69 views

Graph theory and tree company

I appreciate anyone who answer this question and I anyone who design appropriate graph.
3
votes
0answers
93 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
20 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
35 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
25 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
37 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
21 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 ...
2
votes
0answers
52 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
25 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
48 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
64 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
36 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
33 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
28 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
25 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 ...
1
vote
0answers
26 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} ...