Graphs began to appear around 1770, however, they were commonly used
only around 1820 (Thomas, 1999). They appeared in three different works,
The Statistical Book of Maps by William Playfair, the Indicator Diagrams by James Watt,
and the writings of Johann Heinrich Lambert (Thomas, 1999). The descriptive
geometry of Gaspard Monge, which had an important indirect influence on the way
graphs developed (Thomas).
In 1847, Gustav Kirchhoff examined a special type of graph called tree
(Ralf, 1993). A tree is a minimally connected graph but contains no cycle.
Kirchhoff used this concept in applications
dealing with electrical networks in his extension of Ohm's laws for electrical flow (Ralf).
This period also saw two other major ideas coming to limelight. Francis
Guthrie first investigated the four-color
conjecture around 1850 (Ralf, 1993). The second major idea was the Hamiltonian
cycle. This cycle was named after Sir William Rowan Hamilton, who used the idea
in 1859 for an interesting puzzle that used the edges on a regular
dodecahedron (Ralf, 1993). A solution to this puzzle is
not very difficult to find, but mathematicians are still searching for necessary
and sufficient conditions to characterize those undirected graphs that pass a
Hamiltonian path or cycle (Ralf). In around 1857,
Arthur Cayley developed some graphs in order to count the distinct isomers of
saturated hydrocarbons (Ralf).
The term `graph' has several different meanings. The term was introduced
in English in 1878 by the mathematician J J Sylvester, who used it to describe
diagrams that he believed showed striking
analogies between the chemical bonds in molecules and graphical representations
of mathematical invariants and covariants of binary expressions (James, 1878;
and Thomas, 1999). |