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
5answers
75 views

Prove by induction: A tree on n≥2 vertices has ≥2 leaves

This is what I have. I'm pretty sure this is quite incorrect, but am I at least headed in the right direction? Base Case: $P(2)$: Tree on 2 vertices can only have one edge, the edge connecting the ...
0
votes
2answers
47 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
0
votes
0answers
26 views

Is the path from u to v is diameter of the tree?

The diameter of a tree is the longest (simple) path in the tree. Let u be a vertex in a tree and let v be the farthest from u vertex in T. Show that the path from u to v may not be a diameter I am ...
0
votes
0answers
18 views

Minimal spanning trees in multigraphs with constraints

I have a multigraph G whose edges have three identities. Let's say I have three colors of the edges red, blue and green and each two nodes may be connected by a red, blue and/or green edges. The graph ...
0
votes
1answer
32 views

Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching maxima cardinallity. A tree is an acyclic connected graph. Is there an efficient algorithm ...
0
votes
0answers
12 views

Minimum number of pages in a B-Tree of order n?

How can I calculate the minimum number of pages in a B tree of order n and height 3? 1st level = 1 page 2nd level = 2n+1 pages 3rd level = ? 3rd level is 1? Or how many pages?
0
votes
1answer
19 views

Completion of acyclic sub graph

Statement: Given an acyclic subgraph of a connected graph, show that this subgraph can be completed into a spanning tree of the graph. I know that there is a theorem that states that any connected ...
0
votes
2answers
68 views

Difference between Depth first search and Breadth first search algorithm

Currently I am studying Depth first search algorithm and Breadth first search algorithm. Both these algorithms are looking quite similar to me except for some differences. In BFS, we start with a ...
0
votes
0answers
14 views

Minimum Path Cover in Trees

We have a Tree with $m$ nodes and $m-1$ edges. We are given $Q$ queries. Each query consists of a list of nodes of size $k$, $[n_1, n_2, ..., n_k]$. I need to answer the minimum number of paths that ...
0
votes
0answers
23 views

Nodes lying on Same Path in Trees

Given a Treen with $n$ nodes and $n-1$ edges, I have to answer $Q$ queries. In every query, I get a list of nodes of size $k$, $n_1, n_2, ..., n_k$. I need to answer the minimum number of paths that ...
0
votes
1answer
21 views

Binary Decision Trees

I know the basics to a binary decision tree, but this problem has me a little stumped, and I'm looking for some verification on my ideas. The problem is: "Create a binary decision tree that reflects ...
0
votes
1answer
34 views

Constructing a computably infinite tree with no computable infinite branches using PA

Define an infinite tree as any set of sequences closed under prefix restriction, i.e. any prefix restriction of a sequence in the set is also in the set, where a prefix restriction is a restritcion of ...
0
votes
1answer
30 views

Show that in a binary tree, if B is the number of branch points (including the root) and L is the number of leaves, then one has the relation L = 1+B

We have been discussing trees lately, but have yet to even touch on the topic of a binary tree. I understand what a leaf is, but we didn't have one for the term "branch points" Without being 100% sure ...
1
vote
1answer
51 views

How to prove that each edge of tree is a bridge?

How to prove that each edge of tree is a bridge? My attempt: Tree is a connected graph which has no cycle, and in a connected graph, bridge is a edge whose removal disconnects the graph. Let G ...
2
votes
1answer
28 views

Question about theorem with trees

I know the theorem: for an undirected graph on $n$ nodes, any of the following two imply the third: $G$ is connected $G$ does not contain a cycle $G$ has $n-1$ edges (source) ...
0
votes
0answers
21 views

Minimum biconnected graph from spanning tree algorithm

I'm thinking about if there exist an algorithm, which can build a biconnected graph from spanning tree? The problem is that it should be minimal-weight (each edge between every pair of nodes has it ...
1
vote
1answer
44 views

Finding the probability using a tree.

Let's say a specific exam has 3 levels (I, II, III). The candidates who pass the first exam are then eligible to take the next level of the exam. Let's say the pass rates for levels I, II, and III are ...
0
votes
1answer
16 views

Treewidth Of Graphs And Chordal Completion

https://en.wikipedia.org/wiki/Treewidth The above page explains what a tree decomposition is, and states that treewidth of G is equal to the minimum clique number, minus one, of a chordal ...
3
votes
2answers
32 views

You can always delete a vertex from a tree $G$ such that the remaining connected components have size at most $|V(G)|/2$.

I want to prove the statement in the title: for any tree on $n$ vertices, it is possible to delete a vertex such that the deletion leaves connected components with at most $n/2$ vertices each. I drew ...
0
votes
0answers
16 views

Finding Height, Number of Leaves, and Value at of Each Node on Recursive Trees

I have an exam tomorrow and am struggling to understand how to get the height of a tree, the number of leaves, and the value of each node. The image is a practice exam. Any tips and help on the first ...
0
votes
0answers
19 views

Domain of Injectivity of Analytic Map

Suppose we have an analytic map $f: \mathbb{D} \to \mathbb{C}$. Then the set of points where the function is not locally injective is a discrete set. Suppose first for simplicity that the points ...
0
votes
2answers
43 views

Proving the number of leaves of a tree. (Graph Theory)

Prove that if a tree has $n$ vertices (Where $n\geq 2$)and no vertices has degree of $2$, then $T$ has at least $\frac{n+2}{2}$ leaves. Prove by contradiction Suppose that $T$ has less than $\frac{n+...
1
vote
1answer
43 views

Minimum spanning tree of graph? proof by contradiction?

this is not a homework but I need to understand it before my exam tomorrow. How to prove by contradiction that a minimum spanning tree of a graph G is unique if all the edge weights in G are distinct?...
0
votes
0answers
41 views

Diameter of subtrees

Can some one explain how this guy is calculating the centers of all subtrees in $O(n)$. I couldn't understand it. Here is the Quora link A part of his answer claims the following: 4) Find centre of ...
3
votes
1answer
53 views

Infinite graph theory: What's a tree?

Consider a finite graph $G$: $G$ is a tree if it satisfies any of the following equivalent conditions: (1) $G$ is connected and no cycle can be a subgraph of $G$. (2) $G$ is connected and no cycle ...
0
votes
0answers
14 views

number of nodes in Balance binary tree, Full binary tree Complete binary tree

How can I calculate the number the number of nodes in Balance binary tree, Full binary tree Complete binary tree? For the perfect binary Tree, I found the formula $2^{h+1}-1$.
0
votes
1answer
33 views

Verify directly that are exactly 125 labelled trees on 5 vertices.

I know Cayley's formula. However, I need to count them without using the formula. Such a tree has $5-1=4$ edges. Let the degrees of vertices be $d_1,d_2,d_3,d_4,d_5$. By handshaking lemma $d_1+d_2+d_3+...
-1
votes
1answer
21 views

Maximum number of strict binary trees that can be made, each having exactly n leaf nodes.

I am trying to evaluate(Mathematical expression) the number of strict binary trees that can be made with n leaf nodes. I already know that a strict binary tree with n leaf nodes would have exactly ...
0
votes
0answers
20 views

Uniqueness of spanning trees made using search algorithms?

For undirected graphs, the corresponding spanning trees can be obtained using various search algorithms like Depth-first search algorithm , Bredth-first algorithm, etc. I am not sure whether the ...
0
votes
1answer
33 views

How to define a set of trees recursively?

In particular, consider the set of integer-labelled binary trees (T). How could this set be defined in a recursive way from $\mathbb Z$ and T itself? Examples: $(-2, 1, (3, 1, 0)) \in T$ $(-1, (7, 2, ...
2
votes
1answer
61 views

How do I know when to use a Venn diagram or a probability tree? Also, when can I assume that the events are independent?

I have 2 specific problems, one 'requiring' me to use a probability tree, and the other a Venn diagram. I know that apparently the Venn diagrams can be converted into probability trees and vice versa, ...
1
vote
1answer
34 views

What function describes this problem of every possible breeding of a set of dogs?

If I have n dogs [a, b, c, ...], and I want to breed them in every possible combination (every possible binary tree made of ...
1
vote
1answer
25 views

Bounding the probability of landing at any point for a random walk on a tree

Fix $m\geq 2$ and a vertex $v_0$ in an infinite connected $2m$-regular tree, (in other words, the Cayley graph for the free group on $m$ generators) and consider the random walk on the tree starting ...
0
votes
0answers
24 views

Are these tree-related concepts redundant?

I've been doing a lot of work with trees lately, and have developed vocabulary that I've been using to describe them. Not having that strong of a background in graph theory, it occurred to me that I ...
1
vote
1answer
23 views

Cuts on complete binary trees

Claim : Suppose we have a complete binary tree of height $h$. We introduce a cut to partition this tree into two sets of vertices of size $x$ and $2^h - 1 - x$ for some $x$. For any $x$, we define the ...
2
votes
0answers
41 views

How Many Ways to Construct Trees With No More Than 4 Connections per Vertex.

I am a high school student (so sorry if my thinking is way off) with a problem related to chemistry essentially dealing with the number of ways you can arrange carbon atoms in a alkane. I saw that ...
3
votes
1answer
46 views

Bona “A Walk Through Combinatorics” Problem 10.29

Given a tree $T$, define the "total distance" of a vertex $v$ by $$ td(v) = \sum_{w \in V(T)} d(v,w), $$ where $d(v,w)$ is the number of edges in the unique $vw$-path in $T$. In any tree, the value of ...
0
votes
0answers
20 views

Parsing a definition concerning trees and tuples

Definition: Let $T$ be a tree. Given a set $X$, we define a $T-tuple$ of elements of $X$ to be a function x: $T\rightarrow X$ Alternatively, we sometimes refer to a $T$-tuple as a tree of elements ...
2
votes
1answer
40 views

Constructing every spanning tree from addition and deletion of edges

Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ ...
0
votes
2answers
81 views

Relation between vertices and edges in a tree?

I know the following relation between vertices and edges of a tree - Any connected graph(undirected) with n vertices and $n-1$ edges is a tree. My question is suppose I have an undirected connected ...
0
votes
1answer
39 views

Finding log base 2 of a number .

I generally visualize $\log_{2}$ of a number as an inverted binary tree, for example to know how many times 8 needs to be divided to become one I image a inverted tree of 8 leaves then, the level ...
0
votes
2answers
36 views

How many vertices are of degree 1?

Given $T(n,m)$ which contains only vertices of degree 1 and 3. How many vertices are of degree 1? Is it similar to compute in thi link? How many vertices of degree 1 in a tree? Thank you.
1
vote
1answer
64 views

Closed Form for Sum of Nodes in Binary Tree

Consider a binary tree $T$ with nodes in $\mathbb{Z}^+$, where level $k$ of $T$ contains nodes $2^k$ through $2^{k + 1} - 1$. I have some problems that involve visiting the nodes of $T$ in their ...
1
vote
1answer
16 views

Number of Plane Oriented Recursive Trees

The number of plane oriented recursive trees is $(2n-3)!!$ I understand that given a vertex $v$ with $k$ successors, there are $k+1$ ways to attach a new vertex to create a new tree of size one ...
1
vote
0answers
27 views

Entropy of a dictionary

I have an english dictionary (a file that contains a list of words) and I want to calculate: given a path tree (a word), measure $H(C_{l+1}|C_l=c_l, C_{l-1}=c_{l-1}, ...)$ for a few levels of the ...
3
votes
1answer
73 views

Set Theory: Tree Property

Why does the tree property hold for regular cardinals but not singular cardinals? (I.e. There exists a tree of height $\kappa$ with countable levels and no cofinal branch for $\kappa$ a singular ...
1
vote
0answers
16 views

Example of a Shortest Path Tree for a Directed Graph that contains a directed cycle of negative length

My colleague says this is possible, but I don't understand how. I know it is necessary for the directed Graph to contain no negative cycles in order to prove that the Shortest Path Tree exists. So I ...
0
votes
2answers
42 views

Black Depth in Red-black Tree?

Wikipedia's Red-black tree states the last property of a Red-black tree: Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: ...
1
vote
1answer
60 views

Depth-first search binary tree problem

Professor Hastings has constructed a 23-node binary tree in which each node is labeled with a unique letter of the alphabet. Preorder and postorder traversals of the tree visit the nodes in the ...
1
vote
1answer
36 views

Relationship between ordered trees and integer partitions

I've found that there is a bijection between integer partitions and ordered rooted trees with roots of degree 2 or greater. The rigorous proof is complicated, but the gist of it is that you take the ...