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
279 views

Category of Trees as sub-category of Category of Graphs

A tree (like a binary search tree) is a direct graph with some limitations (no cycles, connected). How can I express the category of trees as "sub-category" of a graphs? There is a way? I'm not sure ...
0
votes
3answers
1k views

What is the main difference between a free tree and a rooted tree?

In graph theory what is the difference between a rooted tree and a free tree ? What is normally meant when just the plain "tree" is used ?
0
votes
1answer
122 views

Proof for binary tree is a planar graph

Suppose G is a binary tree. Is G necessarily planar? Give a proof, or a counterexample. My guess is that it is indeed planar but I am struggling to find a formal proof for this. EDIT: Is there a ...
0
votes
2answers
535 views

Explanation of why the height of a binary tree $\theta({lg}(n))$.

From Heap Sort chapter of Introduction to algorithms : Since a heap of n elements is based on a complete binary tree , its height is $\theta({lg}(n))$. I know this is correct but how can this ...
0
votes
1answer
49 views

Prove graph cannot have exactly two distinct spanning trees [closed]

Prove that a graph cannot have EXACTLY two distinct spanning trees.
0
votes
1answer
50 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
2answers
111 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 . ...
0
votes
2answers
76 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 ...
0
votes
2answers
75 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!$ ...
0
votes
1answer
29 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
2answers
659 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
3answers
72 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 ...
0
votes
2answers
33 views

Number of spanning trees of a graph (behind the formula)

Given $G$ a subgraph of $K_n$ s.t. $G$ has $n$ vertices with adjacency matrix $A$; why is $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}$$ the number of spanning trees? I can't get ...
0
votes
1answer
338 views

Determining the total degree of a tree

At the start of the solution, I understand that any tree with four vertices has three edges. I don't understand the next statement: "Thus the total degree of a tree with four vertices must be 6." ...
0
votes
2answers
108 views

syntax tree for the word (())()()

I have to create the syntax tree for the word (())()() . That's what I have tried: Could you tell me if it is right?
0
votes
1answer
51 views

Getting a values from nodes

The goal: get horizontal values of vertical level N where level 1 is pinacle node (1). Example: level 4 as input should produce: | 1 | 3 | 3 | 1 | Note: the sum ...
0
votes
2answers
2k views

About balanced and complete binary tree

I found this and I just couldn't verify it. How come it is true? The maximum number of nodes that a balanced binary tree with depth $d$ is a complete binary tree with $2^d-1$ nodes. Let say I have ...
0
votes
1answer
612 views

Maximum height of a quad tree

If we have a quad tree where each node must have 0 or 4 children, is there an expression that can me the maximum height of a quad tree with $n$ nodes?
0
votes
1answer
48 views

Prove by induction that every complete $k$-ary tree of depth $n$ has $(k^{n+1}–1)/(k-1)$ nodes for all integers $n\ge 0$, where $k\ge 2$.

A strictly $k$-ary tree is a $k$-ary tree (a binary tree is a $2$-ary tree) in which every node has either no children (is a leaf) or $k$ children. A complete $k$-ary tree of depth $n$ is a ...
0
votes
1answer
38 views

Huffman coding - conditions for perfect tree output

The question is: Given 4 characters and their frequencies, what's the max possible difference between the frequency of the rarest character and that of the most common character, so the output Huffman ...
0
votes
3answers
44 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 ...
0
votes
1answer
33 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 ...
0
votes
1answer
72 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
59 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 ...
0
votes
2answers
152 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
26 views

Proof about spanning tress in graphs

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$. Let $f_1 \in F_1$. Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.
0
votes
2answers
88 views

Prove that if G is a tree in which all vertices have odd degree then G has odd size.

Prove that if G is a tree in which all vertices have odd degree then G has odd size. Good night, do not know how to approach this "prove". Can you give me tips to solve it?. Please.
0
votes
2answers
53 views

Why is the height of a heap defined as $\lg n$?

I'm a bit confused about why the height of a heap (or a binary tree in general) is given by the floor of $\lg n$. E.g. if you have a tree with 7 nodes, you would get $h = 0$ instead of $h = 2$. Isn't ...
0
votes
1answer
29 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
0
votes
2answers
32 views

Determine the minimum number of weighings to find the counterfeit coin.

Here's the full problem: We have 20 coins, 1 of which is counterfeit (too light). Determine the minimum number of weighings to find the counterfeit coin. Okay so is used the formula $$h=\left ...
0
votes
1answer
53 views

calculate the proportion of n-node trees whose root has only one or two subtrees.

Could we use combinatorics and generating functions to calculate the proportion of n-node trees whose root has only one or two subtrees? Here is what I tried: The combinatorial construction for the ...
0
votes
1answer
59 views

How do I construct a minimum spanning forest?

I realize that a minimum spanning forest in a weighted graph is a spanning forest with minimal weight. Does this mean that I construct it by turning all of the trees into spanning trees?
0
votes
2answers
574 views

How many trees are in the spanning forest of a graph?

Spanning forest is defined by the following definition: A forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in G between these two ...
0
votes
1answer
38 views

find an algorithm to find MST in linear time while each edge has the same weight

I have been disscussing this problem with a lot of my friends . However no solution has been found. let G= w is a weight function for each e in E w(e)=1 find MST of G in O(|V|+|E|) thanks
0
votes
2answers
113 views

A tree $T$ with 50 end-vertices has an equal number of vertices of degree 2, 3, 4, and 5 but contains no vertices of degree greater than 5.

What should be the order of $T$? So I know a graph $G$ is a tree if every two vertices of G are connected by a unique path
0
votes
1answer
846 views

Number of nodes in binary tree given number of leaves

How would I prove that any binary tree that has n leaves has precisely $2n-1$ nodes ? Given that a binary tree is either a single node "o" or a node with the left and right subtrees contains a binary ...
0
votes
2answers
80 views

Determining number of parent node on an n-tree.

I'm sorry if this is the wrong one, was unsure if this was computer science, programming, or mathematics related. I'm going with mathematics because it is semi-graph theory related. I have a tree ...
0
votes
1answer
68 views

Non-Isomorph trees of a graph

Please consider this graph How many non-Isomorph trees with 4 vertex has this graph? Is there any formula that show number of non-Isomorph trees with $n$ vertices? thanks
0
votes
1answer
89 views

Depth of BFS Tree With Different Root Nodes

I need to either prove or disprove that for any node of a graph, the depth of the BFS tree using this node as root is always the same. My intuition is that this is true, but I'm having difficulty ...
0
votes
2answers
3k views

How to find non-isomorphic trees?

"Draw all non-isomorphic trees with 5 vertices." I have searched the web and found many examples of the non-isomorphic trees with 5 vertices, but I can't figure out how they have come to their ...
0
votes
2answers
931 views

creating a Binary tree based on a prefix expression

I want to find the value of a the prefix expression -/+8,10,2*3,2 and build its binary tree I am trying to learn this for a math course, but have absolutely no clue ...
0
votes
1answer
27 views

Question Concerning Family of Trees

I have the following problem where I am asked to construct a family of trees (one for each $n$) that have exactly 2 leaves. I am having difficulty with this problem mainly because I cannot find a ...
0
votes
1answer
127 views

Prove that there are two end points in a tree with a common neighbor

Let $T=(V,E)$ be a tree with at least $3$ vertices. Assume that every vertex has either degree $1$ or a degree of at least $3$ (so there are no vertices with degree $2$). Prove that there are two end ...
0
votes
2answers
103 views

Prove there is a tree with $n$ vertices having degrees $d_1, d_2…d_n$

For $n ≥ 2$ suppose $d_1, d_2,....d_n$ are positive integers with sum $2n - 2$. Prove there is a tree with n vertices having degrees $d_1, d_2....d_n$. I'm at a loss on this one. I'm sure it's pretty ...
0
votes
2answers
124 views

Question: Graph Theory and Trees

In a group of 2n schoolchildren each one has at least n friends. On an outing, the teacher tells them to hold hands in pairs. Show that this can be done with each child holding a friend’s hand, and ...
0
votes
2answers
124 views

how to store a math problem in a binary tree?

If I have the following problem: $\ 12 - (2 +3) - (3 *4)/ (5 -7) $ How would it be stored in a binary tree? following the order of operations, would you start with $\ (3*4) $ at the top or $\ 12 $ ...
0
votes
1answer
165 views

Recurrence relation for the number of spanning trees in a connected graph proof

The number of spanning trees in a graph $G$ containing an edge $e$ is equal to the number of spanning trees in $G/e$. The number of spanning trees in a graph $G$ not containing an edge $e$ is equal to ...
0
votes
2answers
923 views

Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle

When proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle, is it sufficient to just remove that edge that created a cycle, then it ...
0
votes
2answers
475 views

Confusion related to a graph problem

I have this question related to this graph problem Suppose that an n-node undirected graph G = (V , E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. ...
0
votes
1answer
167 views

Computational Complexity of Parallel Algorithms

Does parallelism factor in when deriving the computational complexity of a parallel algorithm? Suppose I have a perfect binary tree $T$ with leaves numbered $1$ to $n$, and an algorithm ...