Tree

From VT.Prog

A tree is a graph theory concept where a set of points are fully connected with no loops or cycles. These sort of graphs can always be drawn as a tree, by putting one of the points at the top of the drawing and putting the connected elements below it.

Things about trees

• For a tree of N points, there are exactly N-1 edges.
• The shortest path between any two points in a tree can be found by going up some number (towards the root) and down (away from the root) some other number.

Types of Trees

Minimal Spanning Tree

Given a set of points with a set of potential edges with associated costs, the minimal spanning tree is the subset of those edges that makes the graph into a tree and has the lowest cost sum.

For example, suppose there are a group of towns and edges (roads) could be built between them at a cost proportional to their distances. So any two towns could be connected by a road giving a potential set of edges. The minimal spanning tree is the least expensive set of those roads that would connect all those towns together.

A way to find such a tree: Prim's Minimum Spanning Tree

More information: Wikipedia Minimum spanning tree