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

1
vote
0answers
120 views

Binary Tree and Geometric Distribution

I have the following algorithm for "constructing" a binary tree: A probability $p_g$ for elongation, i.e. adding an edge A probability $p_b$ for branching, i.e. adding to a node two "child" edges ...
1
vote
0answers
288 views

Binary Tree and Overhead fraction Caluculation

Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes: 2) Only leaf nodes store data; internal nodes store two child ...
1
vote
0answers
54 views

Red Black Binary Search Trees

Give an example of a Red-Black tree and a value, for which inserting the value, and then immediately deleting it yields a tree that is different from the tree before the insertion.
1
vote
0answers
48 views

Enumeration of symbols in grammatical expressions or vertices in tree graphs

I have expressions (type of a function) like e.g. $$f:(A\to B)\to C \to (D\to E)\to F.$$ (Where I understand $A\to B\to C$ as $A\to (B\to C)$, in case that is relevant.) There might be information ...
1
vote
1answer
163 views

Depth first search on graph

I have a homework problem I think I know the answer to, but want to double check Consider the graph with three nodes, $a$, $b$, and $c$, and the two arcs $a \rightarrow b$ and $b \rightarrow c$. ...
1
vote
0answers
49 views

What is the runing time of this algorithm involving length and depth?

I'm hoping that someone can shed some light on this running time. I have a "tree", for lack of a better description, that has a length $l$ and depth $d$. I want to maximize the tree size, which ...
1
vote
1answer
184 views

What is the fairest solution/formula for rewarding points in a hierarchical network?

Introduction The nature of this hierarchical network is based on the concept of Multi-Level Marketing strategy. Example 1 - Unfair Situation Ancestor receives 1 point for every descendant ...
1
vote
0answers
78 views

How can I prove this property of a $d$-ary tree?

I have the following homework (algorithms lecture): Every $d$-ary tree $G=(V,E)$ contains a vertex $v$ such that the size of the subtree with root $v$ is at least $\frac{1}{d+1} \vert V \vert$ and at ...
1
vote
0answers
48 views

How to formulate a best-search algorithm limited by a count of nodes visited?

The problem I'm doing a search by computer program. Each node takes about 5 minutes of wall time to get a result so I'm looking to carefully choose the nodes to inspect so as to find the best result ...
1
vote
0answers
203 views

A tree that does not satisfy: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$?

It is a strange question on a book. Give an example of a tree $T$ that does not satisfy the following property: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$. I ...
1
vote
0answers
55 views

Keeping consistency in subjective ranking

I'm doing some work on a computer program that aids in ranking items which don't have a way to objectively compare to each other. As it is now, it takes each item and pairs it up with each other ...
1
vote
0answers
219 views

Finding the number of spanning trees of a given height

I hope I can avoid being confusing, but here goes. I have a graph $(V, E)$, connected, undirected and with no loops. I also have an assignment of integer-valued weight to each edge of the graph. ...
1
vote
0answers
92 views

Concerning The 'Price-Collecting Steiner Tree'

I'm a Master student at the University of Leuven, Belgium. I have to make a report of a case concerning the 'Price-Collecting Steiner Tree'. We have our model and our restrictions. We are just looking ...
0
votes
2answers
896 views

Searching a binary search tree for a specific value

suppose numbers from 1 to 1000 are saved in a binary search tree and we want to find 363. Which of the following sequences cannot be the order of elements while reaching the searched value? 925, ...
0
votes
2answers
255 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
87 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
474 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
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
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 . ...
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 ...
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!$ ...
0
votes
1answer
28 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
3answers
47 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
32 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
218 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
107 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
560 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
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 ...
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 ...
0
votes
1answer
62 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
42 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
258 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
2answers
119 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
63 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
52 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
28 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
0
votes
2answers
30 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
50 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
53 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
405 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
36 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
96 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
629 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
75 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
64 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
70 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 ...