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

Multiway tree to Binary Tree

A multiway tree T can be represented as a binary tree T...
0
votes
0answers
9 views

Number of nodes in a B tree

In a B tree with minimum degree t, each non leaf node other than root has at least t children and at most 2*t children. Suppose that the keys {1,2,3...,n} are inserted into an empty B tree with ...
5
votes
1answer
40 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 ...
0
votes
0answers
8 views

Generating a binary minimum spanning tree

I need to derive a spanning tree from a given graph. Is it possible to generate a spanning tree which is a binary tree?
0
votes
0answers
4 views

Preparing data for WEKA decision tree J48

I'm trying to deal with WEKA and J48 algorithm. Looks like I have to present all my numerical values like age, income, height, weight as classes: age_from_18_to_25, age_from_26_to_40, e.t.c. Here is ...
-1
votes
1answer
34 views

Can someone tell me how to solve this problem? [closed]

Let $G$ be a connected graph with $n$ vertices. Let $GT$ be the graph having the spanning trees of $G$ as vertices, with two vertices $s$ and $t$ being adjacent if and only if the corresponding ...
0
votes
1answer
29 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 ...
6
votes
2answers
95 views
+50

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
3answers
32 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
41 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
21 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
38 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
21 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 ...
0
votes
0answers
39 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 ...
4
votes
1answer
166 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
24 views

Exactly one minimum spanning tree

A all edges in a graph of n vertices have differing weights. How can I prove that there is exactly one minimum spanning tree?
1
vote
1answer
50 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.
0
votes
0answers
13 views

Trees and Leaves (Graph Theory)

Let $T$ be a tree with $l$ leaves and $k \in \mathbb{Z}^{+}$ with $2k \geq l$. I need to show that there exists paths $P_{1}, P_{2},...,P_{k}$ such that: (i) $P_{1} \cup P_{2} \cup ... \cup P_{k} = ...
0
votes
0answers
17 views

mathematical formulation Minimum Cost Flow

I have a problem of minimum cost flow that can be defined as the following matrix. I want to solve it how a linear program (without using kruskal algorithms, prim etc). How can I formulate it like a ...
1
vote
1answer
39 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
25 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
2answers
59 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
31 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
38 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 ...
0
votes
0answers
13 views

Is my understanding of realtionship spanning trees and the cycle graphs correct

Any cycle graph C$x$ for example C200 would have only one spanning tree as a spanning tree would be the entire graph minus one edge. And the amount of ways can you remove just one edge from C200 ...
-1
votes
1answer
74 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 ...
1
vote
0answers
16 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 ...
0
votes
1answer
60 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ 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 ...
-1
votes
1answer
201 views

Question about trees, Let T be a tree with n vertices

Are my answers correct to these 3 questions? Let T be a tree with n vertices. 1) What is the average degree/valency of the vertices in T? Average Degree of of ...
0
votes
1answer
135 views

How many spanning trees does the cycle graph C2014 have?

How many spanning trees does the cycle graph $C_{2014}$ have? How do I create a bipartite graph and use it to solve this problem?
1
vote
1answer
29 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
1answer
39 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
3
votes
1answer
45 views

Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: ...
0
votes
1answer
35 views

Spanning tree with unique paths.

Let $G$ be a connected graph and let $r∈V(G)$. Prove that $G$ has a spanning tree $T$ such that for every edge of $G$ with ends $u$ and $v$, either $u$ belongs to the unique path in $T$ with ends $v$ ...
4
votes
1answer
26 views

Expected number of subtree removal in a tree.

I was solving this problem. In a gist the problem is as follows: You are given a rooted tree. On each step you choose a node randomly and remove the subtree rooted by that node and the node ...
0
votes
1answer
30 views

Normalization of data in decision tree

After reading through a few references, I have come to know that for machine learning in general, it is necessary to normalize features so that no features are arbitrarily large ($centering$) and all ...
0
votes
0answers
51 views

prove that for all h in N, a height balanced tree has a height of at least 1.6^h

prove that for all h in N, a height balanced tree has a height of at least 1.6^h. Can this be proven by induction?
0
votes
1answer
25 views

The intersection of $k$ subtrees of a tree $T$ is nonempty.

Let $T_1$, $T_2$, . . . , $T_k$ be subtrees of a tree such that any two of them have a vertex in common. Prove that they all have a vertex in common. Any hints/solutions are greatly appreciated. I am ...
0
votes
1answer
28 views

Find the node that we will reach with a given path on a graph (complete binary tree)

This question is regarding a special case of graph i.e. complete binary tree Consider the following tree :- ...
1
vote
2answers
171 views

Prove that if all edge-costs are different, then there is only one cheapest tree.

Prove that if all edge-costs are different, then there is only one cheapest tree (minimum spanning tree). (Use contradiction and make sure to keep track of the costs of the different trees involved.) ...
2
votes
1answer
40 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
2
votes
1answer
48 views

Visiting Node in BFS and DFS in the same order [closed]

if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false? a) G can be a ...
3
votes
1answer
50 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
1
vote
1answer
25 views

A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$. Any solutions or hints ...
0
votes
0answers
21 views

Pascal's Identity and Trees

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
3
votes
1answer
31 views

Automorphism of Tree

Let $\sigma$ and $\theta$ be two automorphisms of tree $X$. I want to show that min$_{v\in V(X)}d(v,\sigma(v))=$min$_{v\in V(X)}d(\theta^{-1}\sigma\theta(v),v)$. I know every automorphism of tree is ...
1
vote
1answer
59 views

Iterations of Pascal's Identity

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
0
votes
1answer
38 views

How to understand the perfect binary tree formula?

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says: I'm ...
3
votes
0answers
39 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
2
votes
1answer
62 views

Infinite Tree Probability Question

Suppose I have 10 dollars and I'm able to make fair 50/50 bets like flipping a coin. Now suppose each bet is for 1 dollar. What is the probability that if I keep making bets until I hit 0 dollars ...