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
21 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
40 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 ...
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
1answer
16 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 ...
1
vote
1answer
78 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
12 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 ...
0
votes
1answer
25 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
26 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 ...
2
votes
0answers
114 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
1answer
21 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
23 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 ...
0
votes
1answer
39 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 ...
1
vote
1answer
34 views

Finding Minimum Weight Subgraph Spanning Tree

Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1. Suppose we also have a subset ...
0
votes
1answer
31 views

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree.

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree. I think i've done this right but i'm not sure.
0
votes
0answers
11 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
57 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 ...
0
votes
2answers
31 views

Tree. Number of nodes and children

Suppose a given tree $T$ has $n_1$ nodes that have $1$ child, $n_2$ nodes that have $2$ children, . . . , $n_m$ nodes that have $m$ children and no node has more than $m$ children, how many nodes have ...
1
vote
1answer
25 views

Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
1
vote
1answer
123 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 ...
1
vote
0answers
25 views
0
votes
1answer
17 views

Remove the root from a binomial tree

I have a binomial tree with height k. How do I proof that when I remove the root, the result will be k new binomial trees, each with with a height from 0 to k-1. Thanks in advance.
1
vote
1answer
98 views

Spanning trees of ladder graphs…

a. Draw the 1-ladder, 2-ladder, and 3-ladder graphs, and calculate the number of spanning trees for each. - I have completed this part and wanted to confirm that these numbers look accurate, I feel ...
2
votes
0answers
23 views

Maximum number of subtree in a spanning tree

Is it possible to determine the theoretical maximum of number of subtree that can be extracted from a spanning tree? Some context (I don't know whether this is useful): I build the spanning tree by ...
0
votes
1answer
23 views

Balance factor changes after local rotations in AVL tree

I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation: ...
0
votes
0answers
24 views

Bottleneck distances for the Steiner problem in graphs

I have been reading the paper "Preprocessing the Steiner Problem in Graphs" by Duin (http://link.springer.com/chapter/10.1007%2F978-1-4757-3171-2_10) and I am having a bit of trouble wrapping my head ...
0
votes
0answers
6 views

Tree decomposition (Citation needed)

Recently, I read the statement "Fix $k\geq 1$, Any tree with at least $k$ edges may be decomposed as a union of edge-disjoint subtrees, each having between $k$ and $3k$ edges" Now I was wondering ...
1
vote
2answers
60 views

Number of reachable vertices in a tree

Given a tree $T$ with infinite nodes. Each node of the tree has exactly $C$ children. I need to figure out that, starting from a node at distance $h$ from root, how many distinct vertices can be ...
1
vote
2answers
30 views

Find all possible topological-sortings of graph G

A topological ordering of G is an ordering of the nodes as $v_1,v_2,...,v_n$ so that all edges point "forward": for every edge $(v_i,v_j)$, we have $i<j$. Moreover, the first node in a ...
0
votes
2answers
59 views

Trees with no vertex of degree 2 have more leaves than internal nodes

There is a question asked by portal about Tree having no vertex of degree 2 has more leaves than internal nodes so we want to prove this claim by induction and an answer from Micheal Biro suggested ...
1
vote
1answer
47 views

What is a “linear chain” in Graph Theory?

What is a linear chain in the context of graphs and trees? For example: a topological sort forms a linear chain What does a linear chain mean in the example above? Another example from ...
1
vote
1answer
27 views

How can I draw a tree to represent combinations?

I understand how to systematically draw a tree for permutations. How do you do this for combinations? In my book, I don't see a system to avoid repetitions. I'd like to draw a tree of 5C3 if possible. ...
1
vote
1answer
22 views

Circuits and Trees

Given a graph G, can it be split into 2 sets of graphs($ G_1, \; G_2 $) such that, $G_1$ consists only trees and $G_2$ consists only circuits ? In other words: Is it possible to construct any graph ...
3
votes
1answer
151 views

Tree having no vertex of degree 2 has more leaves than internal nodes

If $T$ is a tree having no vertex of degree 2, then $T$ has more leaves than internal nodes. Prove this claim by a) induction, b) by considering the average degree and using the handshaking lemma. ...
0
votes
1answer
19 views

There are at least 22 vertex-disjoint paths between every pair of vertices?

$G$ is a graph on $n$ vertices and $2n−2$ edges$.$ The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G?$ For every subset of $k$ ...
0
votes
1answer
22 views

Intersection of all possible spanning trees of a connected, simple graph.

Is the intersection of all possible spanning trees of a simple, connected graph $G$ equal to the graph $(V_{G}, \varnothing)$? I'm not sure if this is a trivial question or not. Although I'm going to ...
0
votes
0answers
49 views

Number of Ways to Traverse a Binary Tree

Consider a binary tree of $n$ nodes. For the sake of example consider the following tree: ...
4
votes
0answers
68 views

Why is the intersection of countably many homogeneously Suslin subsets of $\,^{\omega} \omega$ homogeneously Suslin?

I found this assertion in these notes: The derived model theorem (Steel) right in the beginning on page 3, together with the remark that this is 'not too hard to show'. Unfortunately, I'm ...
0
votes
1answer
112 views

Tree with no nodes of degree 2: prove that # leaves ># internal nodes using average degree and handshake lemma

Im really struggling to formalise my thoughts on this one. Basically I understand that if we would allow nodes with degree 2, then we could chain together infinitely many nodes to always produce ...
2
votes
1answer
23 views

Different trees of weighted graph , please check whether my explanation is correct $?$

Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then ...
0
votes
0answers
25 views

Complexity analysis of alpha beta pruning of a full tree

I am trying to understand the derivation of a time complexity for an alpha-beta pruning algorithm but up till now have not found any reasonable recourse. Many recourses claim that if you take a full ...
1
vote
0answers
20 views

Yet another curious convolution

Some time ago, I found the following algorithmic problema: Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors. Given that the ...
0
votes
0answers
56 views

For a k-ary tree with height h, the upper bound for the maximum number of leaves is $k^h$

i want to prove For a k-ary tree with height h, the upper bound for the maximum number of leaves is $k^h$. (assume the complete k-ary tree is a tree that is complete in all levels including the ...
0
votes
0answers
16 views

directed trees versus singly-connected directed graphs

According to wikipedia, a singly connected directed graph (a.k.a. Polytree) is a Directed Acyclic Graph whose underling undirected graph is a tree. How is this different from directed trees (trees ...
1
vote
0answers
34 views

Is there a name for this particular kind of tree graph?

I've recently encountered a problem which heavily involves analysis of structures analogous to weighted trees with no nodes of degree two (such a node along with its adjacent edges would be ...
1
vote
0answers
25 views

Binary Minimum Spanning Tree (from complete graph)

Given a weighted complete graph (or more exactly, a matrix of pairwise metric distances between vertices), I need to find a good approximation of the binary spanning tree of lowest total cost. There ...
2
votes
2answers
87 views

Graph Theory: Trees, leaves and cycles

So, a vertex is called a leaf if it connected to only one edge. a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that G = (V, E) is a graph, V ≠ Ø, where every vertex ...
0
votes
1answer
55 views

Counting spanning trees and hamiltonian paths

Assumption : For any connected graph, every hamiltonian path is a spanning tree but not the other way around. If the assumption is wrong there is no need of reading any furhter. So is the assumption ...
1
vote
0answers
52 views

What exactly is TREE(3)? [closed]

I've heard that it is an enormous number, but I honestly don't understand how someone gets to it. Could anyone explain it in layman's terms?
0
votes
0answers
44 views

Extract the overall “structure” (“backbone”) of a set of vertices…

My main problem is that I am struggling to find a good graph-theoretical formulation of my problem, let alone a formal name for it (if it already exists, as I suspect it should)… Informally, given a ...
0
votes
0answers
15 views

Name of operation: changing the root of a rooted tree

What is (if any) the name of the operation of changing the root of a rooted tree? Picking a vertex which is not the root, then reorienting the edges in such a way that the vertex becomes the root?