Combinatorics

Graphs are sets of objects which are studied based on their interconnectivity with each other. Graph theory began when people were seeking answers to questions about whether it was possible to travel from one point to another, or what the shortest distance between two points was.

A graph is composed of two sets, one of points or vertices, and the other of edges. The set of edges represents the vertices that are connected to each other. Combinatorally, graphs are just a set of objects (the vertex set) and a set of equivalence relations (the edge set) regarding the arrangement of the objects. For example, a triangle is a graph with three vertices and three edges. So the vertex set may be (x,y,z) and the edge set (xy,yz,zx). The actual labeling of the points is not as important as fundamental concepts which differentiate graphs.

Sometimes graphs are not easy to tell apart because there are a number of ways we can draw a graph. The graph (x,y,z) with edges (xy,yz,zx) can be drawn as a circle with three points on the circumference. The lines do not have to be straight. The vertex and edge sets are the only information defining the graph. So a circle with three distinct points on the circumference, and a triangle, are the same graph. Graphs with hundreds of vertices and edges are hard to tell apart. Are they the same?

One of a number of ways to tell graphs apart is to look at their connectivity and cycles, inherent properties of graphs.

A graph is connected if every vertex can be reached to every other vertex by traveling along an edge. The triangle is connected. A square, thought of as a graph with four vertices, (x,y,z,w) but with only two edges (xy,zw) is not connected. There is no way to travel from vertex x to vertex z. A graph has a cycle if there is a path from a vertex back to itself where no edge is passed over twice. The triangle has one cycle. The square, as defined above, has no cycles. Graphs can have many cycles and still not be connected. Ten disconnected triangles can be thought of as a graph with 10 cycles. The two properties, connectivity and cycles, do not always allow for the differentiation of two graphs. Two graphs can be both connected and have the same number of cycles but still be different.

Another four properties for determining if two graphs are different is explained in a very nice introduction to the subject, Introduction to Graph Theory by Richard Trudeau.

Computer networks are excellent examples of a type of graph that demonstrates how important graphs are to the computer field. Networks are a type of graph that has directions and weights assigned to each edge. An example of a network problem is how to find the best way to send information over a national computer network. Should the information go from Washington, D.C. through Pittsburgh, a high traffic point, and then to Detroit, or should the information be sent through Philadelphia and then through Toledo to Detroit? Is it faster to go through just one city even if there is more traffic through that city?

A similar issue involving networks is whether to have a plane make a stop at a city on the way to Los Angeles from Detroit, or should the trip be non-stop. Adding factors like cost, travel time, number of passengers, etc. along with the number of ways to travel to Los Angeles leads to an interesting network theory problem.

A traditional problem for the gasoline companies has been how to best determine their truck routes for refilling their gas stations. The gasoline trucks typically drive around an area, from gas station to gas station, refilling the tanks based on some route list, a graph. Driving to the nearest neighboring gas stations is often not the best route to drive. Choosing the cheapest path from vertex to vertex is known as the greedy algorithm. Choosing the shortest route based on distance between locations is often not the most cost effective route. Some tanks need refilling sooner than others because some street corners are much busier than others. Plus, like the Königsberg Bridge problem, traveling to the next closest station may lead to a dead end and a trucker may have to back track. The list of examples seems endless. Graph theory has applications to all professions.