# Tagged Questions

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.

23 views

21 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 ...
42 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 ...
32 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 ...
224 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 ...
97 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 ...
59 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 ...
22 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?