I Graph Theory

## Graph Theory

### Flowers, trees, and forests

Graph theory is an area of math than can be both beautiful and useful. This math uses dots and lines to create shapes. Graphs can represent "flowers," "trees," and "forests." 'Dots are called nodes or vertices, while lines are called edges. "Edges" connect two "vertices." "Flowers" are vertices and edges that create a closed path. "Trees" are usually several vertices and edges connected together without ever creating a closed path, although a tree can also be just one node--otherwise known as a seed. Forests are groups of trees. The definition of a forest is that it is a graph without closed paths.

This is one small part of math that is beautiful and has a visual form that approximates integral components of our natural forests. Graphs can represent plumbing, the Army's command structure, geneology, molecular structures, and data files to name a few.

The degree of a vertex, d(v) is equal to the number of neighbors of that vertex. The curvature of a vertex, k(v), can be expressed as:

$k\left(v\right)=\frac{1-d\left(v\right)}{2}$

As we use this expression and find the values of the curvature of different vertices, we see that end nodes on trees equal $-\frac{1}{2}$ , limbs where two branches meet equal 0, and crotches where only three branches come together equal $\frac{1}{2}$ . Professor Oliver Knill formulated the theory that the total curvature of a forest is the number of trees.

More generally, for objects called plants, trees where flowers are attached, the total curvature is equal to the number of plants minus the number of flowers.

### Uses

Graph Theory can be applied in everyday life. As an example, think of street cleaners, the vehicle type. To begin to think about how graph theory is applied, compare street cleaning with house cleaning. As you'd rather only vacuum one hallway in your house one time, the street cleaner (not to mention the city) would rather only clean one street one time. You can imagine that this could be challenging figuring out which streets to drive down and in which direction--maybe a little harder than figuring out in which direction you should vacuum your house! Graph theory helps large cities plan the best route for their street sweepers to save time and money. Math can be useful!

This page is based on a lecture by Oliver Knill, Harvard University, on 23 January, 2012.

References:     Lecture Handout     Lecture Worksheet