Special Graph Problems


 

  The subject we now call graph theory, and perhaps the wider topic of topology,  was founded on the work of Leonhard Euler, and a single famous problem called the Seven Bridges problem. Probably the first paper on graph theory was by Euler. In 1736 he wrote Solutio problematis ad geometriam situs pertinentis, Commetarii Academiae Scientiarum Imperialis Petropolitanae which translates into English as "The solution of a problem relating to the geometry of position." Euler was one of the first to expand geometry into problems that were independent of measurement. In the paper Euler discusses what was then a trendy local topic, whether or not it is possible to stroll around Konigsberg (now called Kaliningrad) crossing each of its bridges across the Pregel River exactly once. Euler generalized the problem and gave conditions which would solve any such stroll. You can see a map of the actual seven bridges of  Konigsberg at this site at St. Andrews Univ.

    A graph is a mathematical object with two types of elements, vertices (sometimes called nodes, see below) and edges.  Think of vertices as points and edges as lines connecting some of the points to one another. You can think of the WWW as a graph.  Each computer is a vertex, and the edges are all the phone lines connecting them.    Here is a simple example, a quadrilateral drawn with edges connecting every possible pair of points.  Such a graph is called a complete 4-graph and is one of a group of similar graphs of n vertices called compete n-graphs. A complete graph is a graph in which every vertex is connected to every other vertex. The complete graph with four vertices is called k4. The complete graph with three vertices, k3, is a triangle. Mathworld has illustrations of k2 through k7. A complete graph with n vertices, kn, has exactly n(n-1)/2 edges. In the recent past the term universal graph was used for what we now call a complete graph.

Sometimes we want a graph to indicate that we can only move between two nodes in one direction. To do this the edge segment is replaced with an arrow from one vertex to the other indicating the acceptable direction of travel. These graphs are called directed graphs or di-graphs. An example of a digraph is shown here.

A special type of complete directed graph that has a single directed graph between each pair of vertices is called a tournament graph or a complete oriented graph. Illustrations of such graphs are here.

Two points are called adjacent if there is an edge connecting them.

  Euler path and circuit.  If it is possible to start at a vertex and move along each path so as to pass along each edge without going over any of them more than once the graph has an Euler path.  If the path ends at the same vertex at which you started it is called an Euler circuit. Some nice problems, explanations, and illustrations are shown at Isaac Reed's wonderful web site.   Even some very simple graphs like the one above do not have an Euler path (try it).  The reason can be found at the web site just mentioned.

It is interesting that Euler never published an algorithm for finding an Euler circuit, but only provided a method of determining if one existed or not. In a note from Ed Sandifer he states, "In his paper on the Konigsberg Bridge Problem, all he says about finding such paths is that if you remove all double edges, then it will be easy to find a solution." For a translation of Euler's original paper and a history of the problem see [N. L. Biggs, E. K. Lloyd, and R. J. Wilson. Graph Theory 1736-1936. Clarendon Press, Oxford, 1976 ]. The most common algorithm I have found is credited to a mostly unknown French mathematician named Fleury which appeared in Fleury, Deux problemes de geometrie de situation, Journal de mathematiques elementaires 1883, 257-261. Here is an explanation of Fleury's algorithm.

  Hamiltonian Circuit a Hamiltonian circuit, named for Irish mathematician Sir William Rowan Hamilton, is a circuit (a path that ends where it starts) that visits each vertex once without touching any vertex more than once. There may be more than one Hamilton path for a graph, and then we often wish to solve for the shortest such path. This is often referred to as a traveling salesman or postman problem.   Every complete graph (n>2) has a Hamilton circuit.

Notice that for an Euler path you may visit each vertex more than once and in a Hamilton path it is not necessary to travel every edge.   

In 1962, Chinese mathematician M K Kwan (meigu Guan) posted work on a type of problem that came to be called the Chinese postman problem. If a circuit does not have an Euler circuit, it asks for the shortest circuit that covers each path, even if some edges have to be traversed more than once. At this page from the NIST site I found that Kwan's "article referred to optimizing a postman's route, was written by a Chinese author and appeared in a Chinese math journal. Based on this Alan Goldman suggested the name "Chinese Postman problem" to Jack Edmonds when Edmonds was in Goldman's Operations Research group at the U.S. National Bureau of Standards (now NIST). Edmonds appreciated its "catchiness" and adopted it. Goldman was also indirectly influenced by recalling an Ellery Queen mystery called "The Chinese Orange Mystery". (Alan Goldman, personal communication, 14 December 2003) "

   

The term node is from the Latin nodus and is closely related to our words for knot and knob.  The word circuit is from  circumire, "to go around", which shares the common Latin root for circle, and led to the common English word circuitous.
 
   The word edge is also used to describe the lines joining the vertices of a polygon or polyhedron.  It is drawn from a true English word for the sharpened surface of a sword or spear.  It was originally pronouced with a "k" sound in place of the d, something perhaps like "ekge" and is probaly related to the word acute through the German.