Graph Theory

"Please graph the following..." and groans already echo around the classroom. Graphing data is one of the most widely used areas of mathematics in the real world. It is unfortunate that graphs are often met with frustrated grumbling and then quickly done without truly understanding the fantastic capabilities of graphs and just how useful they can be. Reconsider, however, your definition of graphs. When you think of graphs, you imagine bar graphs and line graphs, which are used as models of relationships between things. Graph theory is the not the study of graphs, in the traditional sense. True, graph theory is a study of relationships between things, but not in the sense we are used to. The graphs that we will be discussing show an important aspect of math that mathematician Keith Devlin puts forth: "Math is about patterns. And patterns are what life is all about" (30). The identification of patterns or lack of patterns amongst the relationship between objects is key in graph theory.
Graph Theory


A graph is a collection of points called nodes that are connected by lines called edges. Here is an example of two graphs that are exactly the same, even though they look different.

Both graphs 1 and 2 have 4 nodes and 6 edges. Points A, B, C, and D are what we would call nodes and they each have a qualitative value based on how many other nodes it is connected to. This is described in terms of degrees. For example, the node A has a degree of 3 because it is connected to three other nodes. You can also have directed graphs where there is an arrow on each edge in order to represent different types of relationships. You can also have weighted graphs where each edge has a qualitative value, and this will represent different types of relationships as well.

Graphs are used effectively in many different applications.

• Computer Networking: Graphs can keep track of which computers are networked together, which were the servers, and weights and arrows could show what kind and to what a computer has access to.
• Family Tree: Graphs can organize who is related to whom in the family. Arrows can be used to show who gave birth to whom, and weights could show many things, such as the number of years in age difference between two members, or how positive the relationship is between two members on a scale of 1 to 100.
• Product Distribution: Graphs can use nodes that represent either factories or stores. Arrows flow from factories to stores, and weights show how many products are shipped from the factory to the store.

For more information on graph theory, go to http://www.cs.elte.hu/~hubenko/graph_theory.html 

For a cool program that helps you do graph theory, go to http://www.graph-magics.com/  (be aware that this program only works on PCs.)