**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 k_{4}. The complete graph with three vertices, k_{3}, is a triangle. Mathworld has illustrations of k_{2} through k_{7}. A complete graph with n vertices, k_{n}, 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.