Minimal Graphs and Trees, Part I

Suppose you're building a network, anything from computers to roads, where the cost of building an edge is a factor. Is there a way to find the smallest possible graph?

What You Should Learn

  • The definition of two special kinds of graphs called trees and forests.
  • The visual representation of trees and forests.
  • the relationship between the size of a tree and its order.
tree branches

The names of the objects in this section come from their similarity to the branches of a tree.

Let's say you're trying to build a computer network like the ones in the previous section where the vertices are computer networks in separate buildings. High speed computer cable isn't cheap so you want to use as little as possible but, once the network is set up, the connections are so fast that it doesn't matter how many edges a connection has to pass through to get to where it's going. In other words, we would like to construct a system where there is exactly one path between any two points since, if there were multiple paths, we would have used cable we didn't need to.

Specifically, we need a network that has a path connecting every vertex to every other vertex, i.e. it has to be connected, and it also has to have no cycles. Not having cycles will ensure that there's only one path between any two points. Before we can go in search of a solution to what's called the Minimal Connector Problem we need some new language.

Any connected graph with no cycles is called a tree. A graph without any cycles is called a forest.

A tree is what we were discussing in the previous paragraphs. It's a graph that connects every point to every other point in exactly one way. A forest is a collection of trees.

graph 48Trees get their name from their appearance. Like the graphs to the right, their branching nature often resembles real world trees. An alternative way to identify a tree is to look for bridges. Individually the two graphs are called trees. Taken together as one big, disconnected graph they're a forest.

Another way to identify a tree is to look for bridges. In a tree every edge is a bridge. If an edge weren't then it could be removed and every vertex could still connect to every other vertex.

Since you know that both of the graphs on the right are trees use them to confirm the following equation.

If G is a tree of order p and size s then s = p - 1.

Minimal Graphs and Trees, Part II >><< Computer Networks and the Internet