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
1answer
70 views

Graph and one Sequence challenge

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 ...
1
vote
0answers
28 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:
1
vote
0answers
13 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 ...
1
vote
1answer
51 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
44 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
0answers
63 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 ...
1
vote
0answers
55 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 ...
1
vote
1answer
253 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 ...
1
vote
0answers
31 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 ...
1
vote
1answer
149 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
0answers
28 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
43 views

Tree of arity n: How to call a vertex that has only k (k<n) children?

What is the correct adjective for a vertex in an n-ary tree that has only k children (k < n)? I was thinking of something like "unsaturated", but I don't know if that is the correct word for this. ...
1
vote
0answers
87 views

Find tree diameter or center

I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter: Take random vertex A Find such vertex B, that distance to it is maximal Find such vertex C, ...
1
vote
2answers
62 views

Spanning Tree, Network Modelling

I'm developing some software at the moment for voip communications (broadcast style comms, think ventrilo or teamspeak) between multiple users without a central server (send voice to server, server ...
1
vote
1answer
31 views

How many spanning trees of a complete graph with an even number of vertices can be split in half by removing a single edge?

We have a complete Graph G with |V|=n . We know it has n^(n-2) possible spanning trees. How many of them could be split into two equal halves by removing a single edge?
1
vote
1answer
153 views

Determine number of directed trees and rooted trees obtainable

I've been doing some exercices about graph theory and I find myself stuck on this one with no idea of to proceed. Here's the question : how many different directed trees can be obtained if we assign ...
1
vote
1answer
199 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
1
vote
0answers
68 views

Proof of existing path on Depth-First-Search spanning tree

Let $G$ be an undirected connected graph, and $T$ the directed spanning tree of $G$, which I got by performing a DFS on $G$. If $H$ is a complete subgraph of $G$, how can I proof that there a path in ...
1
vote
0answers
429 views

Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time.

So we have a graph $G$ with its edges colored by red and blue. we are asked to find a deterministic linear time algorithm that given a parameter $K$ finds a spanning tree of G using exactly $K$ red ...
1
vote
0answers
23 views

For which graphs do depth first and breadth first produce identical spanning trees?

Is this possible?If yes, what are the conditions it should meet?
1
vote
0answers
51 views

automorphism of a rooted tree

Nowadays i'm working with tree automorphisms. I couldn't find information about rooted tree automorphism concerning the root. Does an automorphism of a rooted tree fix the root or not? Logically it ...
1
vote
0answers
167 views

Generating Function for edge-rooted labelled trees

Let $T_v(z)$ be the (exponential) generating function for vertex-rooted (non-plane) trees. Im trying to construct the generating function $T_e(z)$ for edge-rooted trees from this. I know the ...
1
vote
0answers
142 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
1answer
394 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
56 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
50 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
185 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
193 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
84 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
54 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
209 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
57 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
243 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
93 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
338 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
2answers
1k 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
109 views

How do you find the value of n in this example

$$n^{n-2} = 16$$ I know $n = 4$ through trial and error but how do you find $n$ in a conventional manner? I'm basically trying to solve how many nodes are in a tree that has $16$ spanning trees ...
0
votes
2answers
59 views

solve recurrence relation: comparisons to construct binary search tree with maple

I would like to solve the recurrence relation for the average number of comparisons necessary to the construction of a binary search tree. the recurrence is $$ i(n) = n - 1 + \frac{2}{n} ...
0
votes
2answers
613 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
55 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
53 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
194 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
106 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
101 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
45 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
110 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
35 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
574 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
112 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?