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

Get sister node of all nodes given edge list

I've run into this problem writing some code to do some analyses on phylogenetic trees in Python. Let's say I have a tree: ...
1
vote
1answer
28 views

Algorithm for equality of trees of restricted depth

Are there any efficient algorithms to decide whether two trees of limited depth, where all nodes have a finite number of childs, are equal interpreted as finite sets with the leaves the "atomic" ...
0
votes
1answer
20 views

What is the amount of non-isomorphic trees of order n with a maximum incidence of 4?

It's a graph-theory model of the theoretical amount of possible non-cyclic alkanes isomers. I can't find a way to compute it? Any hints appreciated.
0
votes
1answer
116 views

Tree question proving [closed]

Let $T_1$ be a tree of height $h$ such that the root has one child, and the branching factor at each level is one more than the branching factor at the previous level. Thus, the root has one child, ...
0
votes
0answers
57 views

Can Collatz's problem be used as a pseudo random prime sieve?

If you take the concept of $3x+1$, $\dfrac{x}{2}$ and starting at 2, create a tree. On the left nodes you apply the $3x+1$. On the right nodes, if the parent node is even apply the $\dfrac{x}{2}$. ...
2
votes
1answer
537 views

Proof involving maximum weight of edge in minimum spanning tree

Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight ...
1
vote
1answer
47 views

Encoding the answers to questions somewhere in a binary tree

I have a sequence of binary questions $(U_1,\dots, U_N)$ with some distribution. I know the answer to $n\leq N$ (mod-)adjacent questions, and want to convey this knowledge with as few bits as possible....
2
votes
2answers
75 views

In a full binary tree of depth $d$, what is the number of pairs of vertices at distance $t$ from each other?

I can come up with a dynamic-programming-type program to compute this number, but I am wondering if a nice closed form formula is known. By "full" I mean a binary tree where every vertex is within ...
0
votes
0answers
10 views

Proof by induction that $\sum \limits _{i=1} ^n d^{-l_i} = 1$ sentence in a full tree [duplicate]

How do I prove by induction that $\sum \limits _{i=1} ^n d^{-l_i} = 1$ where: $d$ = the number of children of each node; $n$ = the number of leaves; $l$ = the depth of each leaf $l_1, \ldots, l_n$? ...
0
votes
1answer
25 views

Every simple graph has at least $n-k$ edges.

From here on, $n$ will denote the number of vertices and $k$ will denote the number of connected components of the graph in question. Theorem. Let $F$ be a forest, then $F$ has $n-k$ edges. ...
0
votes
2answers
47 views

There are $n^{n-3}$ numbers of trees with named edges - how to proof?

How to proof that there are $$ n^{n-3} $$ trees with $n$ (unnamed) vertexes and $n-1$ named edges: $\left\{1, 2, 3, 4, ..., n-1\right\}$?
1
vote
1answer
140 views

Location of two “centers” in a tree

This problem came up during a recent (and already finished) coding competition on Hackerrank, I was wondering if someone stumbled upon a proof. [This question is my paraphrasing of the original] ...
0
votes
1answer
15 views

Finding a unique tree for given in order and postorder traversals

I just encountered a problem to find a tree for given inorder and postorder traversals.Can anybody elaborate the same using an example ?
1
vote
1answer
451 views

Prove that a graph cannot have two distinct spanning trees

Prove that a graph cannot have two distinct spanning trees. I'm confused with this proof. More so that I think I'm confused as what distinct in this context means? Initially I thought it was that ...
0
votes
0answers
43 views

Help with functions of vertex sets

Let vertex sets $V_1$ and $V_2$ be defined by $V_1= \{1, 2, 3\}$ and $V_2 = \{a, b, c \}$. Let $E_1 = \{ \{ 1, 2\}, \{2, 3\} \}$, and let $E_2 = \{ \{a, b\}, \{b, c\} \}$ be the edge sets ...
0
votes
1answer
50 views

how can i Prove that by adding one edge to G you create a cycle in G?

Any one help me to show the prove for this? Let the undirected graph G = (V, E) be a tree. Prove that by adding one edge to G you create a cycle in G.
0
votes
2answers
23 views

an intuition for $\sum {\frac{(n-2)!}{k_1!k_2!…k_n!}}=n^{n-2}$

in studying about Graphs I've faced to the problem which says that the number of trees on n points is $n^{n-2}$. In the solution manual of the book the problem is reduced to the summation $\sum {\...
0
votes
2answers
33 views

The Hand Shaking Lemma

In any graph G=(V,E) [the hand shaking lemma] $$ \sum_{v \in V} \deg(v) = 2 |E| $$ (original at http://i.stack.imgur.com/af4en.png) where |E| donetes the number of edges I alredy tried to count ...
0
votes
0answers
37 views

In code sequence of tree replace every 0 with two 0 and every 1 with two 1 will it be tree again?

So i have this question If yes, explain how the structure of this graph depends on the structure of the original subgraph. In not, give an example of such sequence. I just want to be sure if i'm right ...
0
votes
0answers
17 views

Proving the treewidth of a graph is the maximum treewidth of the connected components

We have a graph $G = (V,E)$ and $C$ is the set of connected components of G. I want to prove that $tw(G) \geq $ Max $tw(C)$ where tw is the treewidth. I know the out sketch of the proof is to take ...
0
votes
1answer
219 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
30 views

Why does no minimal spanning tree contain the longest edge of a circuit?

Let $G=(V,E)$ be a graph with lengthfunction $l:E\rightarrow\mathbb{R}$. How do I prove that if $e$ is a line in a circuit $C$ such that $l(e)>l(f)$ for all $f\in C$ with $f\neq e$, then we get ...
1
vote
1answer
38 views

prooving graph with no cycles and |V | = |E| + 1 is a tree.

My assignment is to prove that G = (V, E) is a tree if and only if |V | = |E| + 1 and G has no cycles. However, I am having some trouble doing just that. We defined a tree as a graph which is ...
1
vote
1answer
84 views

Finding connected components of the graph [duplicate]

suppose that I have the following undirected graph with the following adjacency matrix showing if there is an edge between the nodes: \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 &...
0
votes
0answers
181 views

DFS tree of a $K_{1,3}$-free connected graph

Let there be $G=(V,E)$ a connected, $K_{1,3}$-free graph. (A $K_{1,3}$-free graph is a graph which has no 'claw' structures in it, where a claw structure refers to a vertex that has $3$ edges ...
0
votes
1answer
18 views

Structual induction on mirror(mirror t) = t

I have to prove that for all binary trees $t$ the following property holds: $$mirror(mirror(t))=t$$ $mirror(t)$ is defined as: $$mirror(t) =\begin{cases} Empty, & \text{if $t$ is Empty} \\ Node(...
0
votes
2answers
43 views

Find a minimum spanning tree using Prim's algorithm

I have the adjacency matrix: Where we have nodes a to g, and with their respective weights x means symmetry, and the spaces left out are positive infinity $$\begin{array}{c|c|c|c|c|c|c|c|} & \...
0
votes
0answers
29 views

Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
-1
votes
1answer
138 views

Prove that at least one edge of minimum weight is in the minimum spanning tree of a graph.

Let G be a connected graph with edge weights w. Suppose T is a minimum spanning tree of G. Let X be any nonempty proper subset V(G). Prove that at least one edge of minimum weight in the cut induced ...
1
vote
1answer
88 views

Build Tree by Prüfer Code $(6,2,2,6,2,5,10,9,9)$

I have the Prufer Code $(6,2,2,6,2,5,10,9,9)$. I want to build the corresponding tree. My algorithm: 1) Tree = $\{\}$, code = $(6,2,2,6,2,5,10,9,9)$, count = $(1,2,3,4,5,6,7,8,9,10,11)$ 2) Tree =...
0
votes
0answers
37 views

Name for a Type of Tree Diagram (Simplified Family Tree)

I just want to know what the name for this type of tree diagram is. In order to be clear, I want terminology like "binary tree" or something like that (but a name which actually applies). If I ...
0
votes
1answer
22 views

finding heap child and partents

I did anwer the question but I'm not sure if this is right. can you guys double check my answer and let me know if its wrong. Question 1: For the heap element at position i in the underlying array of ...
1
vote
0answers
56 views

Graph Theory: Are Infinite Trees Planar?

Graph theory: Are infinite trees planar? I think countable trees are, but not uncountably infinite trees, apparently. How does one construct such a tree?
1
vote
3answers
52 views

Finding element in binary min-heap

I am trying to answer two questions. Can some one check my answer and let me know if its correct or not? Question 1: Which locations in a binary min-heap of n elements could possibly contain the ...
1
vote
2answers
60 views

How to prove that a connected graph with $|V| -1= |E|$ is a tree?

I could neither show myself nor find a proof of the following result: if $G=(V,E)$ is a connected graph with $|E|=|V|-1$ then $G$ is a tree. Could somebody please provide an argument to establish ...
1
vote
1answer
22 views

Upperbound in the number of spanning trees of a r-regular Graph

i was trying to proof this upper bound in the number of spanning trees $t(G)$ of an r-regular graph G (and discuss what happens with equality) $t(G)$ $\leq$ $\frac{1}{n}$$(\frac{rn}{n-1})^{n-1}$ ...
1
vote
1answer
24 views

Interpreting a nonstandard definition of a tree

Definition: A tree is a triple $(T,\sigma,\pi)$ where $T$ is a set and $\sigma$ is a so-called successor function from $T$ to the set $T^*$ of all nonempty subsets of $T$, together with a surjective ...
0
votes
2answers
119 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?
0
votes
1answer
29 views

Why is the spanning tree algorithm used for bridge-routing?

In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed ...
0
votes
0answers
13 views

time complexity of a tree dynamic programming problem

The original problem: http://codeforces.com/blog/entry/20508 581F — Zublicanes and Mumocrates, I want to prove that the time complexity is $O(n^2)$. Suppose we have a tree, how to prove that $\sum_{v=...
2
votes
0answers
118 views

Bounding the global intersection of a family of sets

Suppose that we have a decision tree of height $r + 1$ that describes how to increment an $n$-bit integer in the range $[0, 2^n -1]$. That is, the internal nodes are labelled with a bit position that ...
1
vote
0answers
46 views

Completeness in M-ary trees where the value of M is variable.

Definitions of complete trees are typically limited to some specific kind of tree, often an $m$-ary tree, where the number of children each internal node must have is a positive integer $m$. Consider ...
0
votes
1answer
57 views

Why is tree not uniquely possible with given preorder and postorder traversal?

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely? preorder and postorder inorder and postorder ...
1
vote
1answer
34 views

Prove that minimum spanning tree is a tree

From the the Wikipedia page Minimum spanning tree: A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total ...
0
votes
0answers
13 views

Minimum(maximum) cost of a weighted uni-height tree

If we have a rooted tree with all trunks the same height, and every vertex assigned a weight, is there a simple method to find the route from root to a leaf with minimum(maximum) cost?
0
votes
1answer
90 views

Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8

Question: Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8 (in that order) into an (initially) empty binary search tree. Show also ...
1
vote
1answer
24 views

Set of edges not contained in any spanning tree

The question is as follows: Prove that in a graph $G$ a set of edges $X$ which is not contained in any spanning tree is a cycle (or possibly an edge disjoint union of cycles). My thoughts: Proceed by ...
0
votes
1answer
31 views

Minimum spanning tree edge count

Given is a weighted complete graph where every weigth is a positive ineger. Let n be the amount of vertices. I have to prove that the number of edges of a minimum spanning tree of that graph is equal ...
-1
votes
1answer
156 views

Number of paths from root to a node in a tree

How to prove inductively the total number of paths from the root to all leaves in a given tree? From what I understand, one should show how to find the number of paths to a specific leaf, then use ...
11
votes
0answers
163 views

Free medial magmas

A medial magma is a set $M$ with a binary operation $*$ satisfying $(a*b)*(c*d) = (a*c)*(b*d)$. Medial magmas constitute an algebraic category $\mathsf{Med}$, therefore there is a functor $\mathsf{Set}...