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

heavy path decomposition/heavy-light decomposition

I'm reading about the heavy path decomposition of trees and its application. I would like to know its time and space complexity. In addition, can the algorithm be implemented in distributed way? What ...
7
votes
1answer
1k views

Height of a full binary tree

A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children. I have been trying to prove that its height is O(logn) unsuccessfully. Here is my work so far: I ...
0
votes
0answers
19 views

Which cut-off for collapsing this tree?

I have a Newick tree that is built by comparing similarity (euclidean distance) of Position Weight Matrices (PWMs or PSSMs) of DNA regulatory motifs that are ~5-9 bp long sequences. An interactive ...
0
votes
1answer
37 views

Expected number of feed-forward/backward triangles in a random graph with internal nodes.

Suppose we have a graph with N* nodes (these are internal nodes. they all have at least one child). Every directed link in the network exists with probability p. What would be the expected number of: ...
1
vote
2answers
67 views

Can we construct from $[0,\omega_1)$ a space which is strictly-Frechet with no winning strategy in $G_{np}(q,E)$?

I have asked in here a question which tured out to make no sense. I think I have found the confusion and would like to try and rephrase my question: Let $E$ be a topological space, $q \in E$. ...
0
votes
1answer
48 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 ...
1
vote
1answer
69 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 ...
0
votes
0answers
29 views

prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
0
votes
0answers
14 views

What is a first-order dependency tree?

From the definition of Chow–Liu trees. Obviously, a tree is a graph with no loops; with first-order do they mean that it is a tree similar to those followed by a depth-first search?
0
votes
0answers
21 views

Representing trees in Set builder notation?

Is there a way to represent graphs and minimum spanning trees using set builder notation? e.g. I have a weighted graph of n nodes, all connected to each other in a mesh network manner. I am to ...
0
votes
1answer
116 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
56 views

Finite trees and embedding in infinite regular trees.

Assume that you have a finite tree $T=(V,E)$, where $V$ and $E$ are the set of vertices and edges of $T$, respectively. Let $d_{max}$ be the maximum degree the some vertice(s) $v\in{V}$. Assume also ...
0
votes
1answer
43 views

Proving that a sub-graph of a tree is a tree

The proof that P ::== any sub-graph, G* of the tree G, is also a tree, involves proof by contradiction. We can suppose that the sub-graph has a cycle --> the whole graph has a cycle --> the whole ...
1
vote
1answer
32 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
0
votes
1answer
50 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?
1
vote
1answer
82 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 ...
0
votes
2answers
293 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
0answers
41 views

How can I find the height of the Recursion Tree?

How do I determine the height of a Recursion tree? For example for the recursion $T(n) = 3T(\frac{2n}{3}) + O(1) $. Could you give me a hint?
0
votes
1answer
54 views

Definition of a leaf in a tree

Across two different texts, I have seen two different definitions of a leaf 1) a leaf is a node in a tree with degree 1 2) a leaf is a node in a tree with no children The problem that I see with ...
1
vote
3answers
68 views

Why do the children of a node $n$ in a complete binary tree have indices $2n $ and $2n+1$?

The complete binary tree is breadth-first ordered 1 to $n$ where $n$ is the number of nodes. The thing I cant seem to understand is that why are the children of node $N$ always $2N$ and $2N+1$? For ...
0
votes
1answer
35 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
1
vote
1answer
73 views

Largest order of automorphism group on a rooted tree?

MacArthur, Sanchez-Garcia, and Anderson have used the ratio of the order of $|Aut(G)|$ and $n!$ (i.e., order of $S_n$) as a normalized measure of the symmetries present in a graph. I am working on ...
0
votes
1answer
458 views

Minimum number of nodes in balanced binary search tree

I'd like to know if anyone could help me verify a recursive formula for the minimum possible number of nodes a binary search tree would require to be balanced. So far, I know that the recursive ...
0
votes
1answer
137 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...
0
votes
1answer
53 views

What's an efficient algorithm for walking to a minimum spanning tree?

Given a connected directed acyclic graph $G(V, E)$, is there an algorithm for changing a spanning tree to a minimum spanning tree through a series of edge swaps? We can use Prim's or Kruskal's ...
3
votes
2answers
375 views

Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.

For $n\ge4$, let G be a simple n-vertex graph with at least $2n - 3$ edges. Prove >that G has two cycles of equal length. (West's Introduction to Graph Theory Q 2.1.42) I am trying to prove the ...
0
votes
0answers
98 views

Structural induction on internal nodes of a binary tree

I know my language is not super mathematic, but I want to make sure I have the logic down. Here is my proof for the number of internal nodes in a binary tree being equal to the floor_function(n/2), ...
0
votes
1answer
201 views

has deleting node in a binary search tree Displacement feature?

I am developing an academic project about graph and tree theory.I searched a lot but I didn't find a clear answer. In a part of project we want to delete some nodes from tree for example we want to ...
5
votes
3answers
73 views

Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?
0
votes
1answer
37 views

How I can prove the one order homology of a tree is zero

When T is a tree and d1 is boundary operator fromC_1(T) to C_0(T) how to prove kernel of d1 is {0} I think acyclic is key point but i don't know next step.
3
votes
2answers
93 views

How many vertices does this tree have?

Suppose that $T$ is a tree. It has $e$ edges and $n$ vertices, and $\overline{T}$ has $10e$ edges. What is n? I think $n = 1$ is a solution, because $T$ can have no edges then, so $0=10*0$. A ...
0
votes
1answer
68 views

Parse Trees - Arithmetic Expressions

In regards to the right side of this expression (c * (a-b)) how is it factored to include (-) instead of * and then (-) again? I cant understand what steps my teacher made to do this.
4
votes
1answer
66 views

Infinite sequence of trees that are not subgraphs to each other

This is from a set of exercises and I am stuck to this. Please, have in mind, that I want to understand how it's solved, I am not just looking for a solution. Define an infinite sequence of trees ...
0
votes
1answer
87 views

Binary Search Tree Traversals

Draw a BST when you insert, $O,V,E,R,F,L,C,W$ from left-to-right and determine the order of the nodes when using post-order traversal and pre-order traversal. My attempt at drawing the BST: ...
0
votes
0answers
39 views

Can an arbitrary network of nodes be effectively visualized as a circular “treemap”?

We all know that a treemap is effective for visualizing hierarchical tree data (i.e. where there are only 1 to many relationships like in a computer file system): But how difficult algorithmically ...
8
votes
2answers
216 views

Ordinal interpretation of Friedman's $n$?

I heard that Kruskal's tree theorem can be turned into a finite form that creates an extremely fast growing function because ordinals could be encoded into trees. On this wiki page it mentions that ...
2
votes
1answer
91 views

questions about binary search tree

Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees. How is it prove ...
0
votes
2answers
95 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
1
vote
1answer
38 views

Graph G with two Spanning Trees

Let's assume that Graph $G = <V,E>$ has two Spanning Trees $G_a = <V, T_1>$ and $G_b = <V,T_2>$ where $T_1 \cap T_2 = \emptyset$ and $T_1 \cup T_2 = E$. Prove that $\chi(G) \le 4$ ...
5
votes
1answer
85 views

Finding graphs with a given number of spanning trees

All of the graphs considered in this question are connected. We can find the number of spanning trees $t(G)$ of $G$ using Kirchhoff's matrix-tree theorem or the deletion-contraction method. I'm ...
1
vote
1answer
108 views

Find Minimal Spanning Tree Using Prim's Algorith

What will be the minimal spanning tree using Prim's Algorithm for this graph Also can i draw a tree and assign the weights as i like,will there be a minimal spanning tree for such a graph
0
votes
1answer
49 views

Some questions about first-order logic (arising from a book by Raymond M Smullyan)

Recently, I got confused when reading a book about first order logic written by Raymond M smullyan. Chapter 1 page 9:When introducing the notion "Formation tree", smullyan define a formation tree for ...
1
vote
0answers
58 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
2answers
45 views

Proof that spanning trees can be converted into one another

Let $T_1$ and $T_2$ be two spanning trees of a graph $G$. Prove that if $e$ is an edge of $T_1$, there exists an edge $f$ in $T_2$ so $T_1-\{e\}+\{f\}$ also is a spanning tree. For $\{e\}\subset ...
2
votes
2answers
59 views

Construction Types or Type Constructions?

In any (simple) type theory there are base types (i.e. the type of individuals and the type of propositions) and type builders (i.e. $\rightarrow$, which takes two types $t,t'$ and yields the type of ...
0
votes
1answer
44 views

Finding the parent of a node in recombining binomial tree

I have posted an earlier question: Finding the child node in the recombining binomial tree. Now I would like to find the parent of a node in recombining tree. The tree looks like this: Now I need ...
1
vote
0answers
282 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
1answer
71 views

The complement of spanning trees is covered by a union of cycles

Is it true that in any (connected) graph $G=(V,E)$, if $T$ is a spanning tree than its complement (edge-wise) may be covered by a union of disjoint cycles? Here's a non-complete attempt to prove this ...
0
votes
1answer
47 views

Proofs with binary trees [duplicate]

Now I have a binary tree which is How would I go about proving binary tree with $n$ leaves has exactly $2 n - 1$ nodes ?
0
votes
1answer
515 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 ...