paper
CathyCZK
the_age_of_euler.docxThe Age of Euler
Rarely has the world seen a mathematician as prolific as the great Leonhard Euler 1 (1707-1783). Born in Switzerland, he eventually obtained royal appointments in two European courts, namely Russia and Germany (under Frederick the Great). He published so many mathematics articles that his work fills seventy thick volumes. His publications account for one-third of all the technical articles of eighteenth-century Europe. The preceding century saw the rise of scientific and mathematical journals – the new media of the times and the quickest way of making innovations known to colleagues across the continent. This outgrowth of the printing revolution of the fifteenth century accelerated the pace of mathematical and scientific progress by transmitting new ideas in a timely manner – much like the present computer revolution has just begun to affect the dissemination of knowledge.
1Euler was the person who gave us the notation π for pi, i for , Δy for the change in y, f (x) for a function, and Σ for summation.
After Euler’s death, it took forty years for the backlog of his work to appear in print. Although he lost his sight in 1768, for the last fifteen years of his life he continued his research at his usual energetic pace while his students copied his pearls of wisdom. It is inconceivable to most how he did mathematics without pencil and paper – without being able to see the multitude of diagrams, equations, and graphs needed to do research.
What areas of math did he enrich and expand? The question is what field of math did he not enrich and expand! Not only did he contribute substantially to calculus, geometry, algebra, and number theory, he also invented several fields. Though a father to eleven children, Euler found time to become the father of an important branch of mathematics, known today as graph theory, which would be important in modern fields such as computer science and operations research, as well as traditional areas such as physics and chemistry.
Euler became the father of graph theory as well as topology after solving the notorious “Seven Bridges of Königsberg” problem. The diagram of Figure 10-1 shows the four landmasses of the city of Königsberg and the seven bridges interconnecting them.
Figure 10-1
The problem was to devise a route that traverses each bridge exactly once and to end where one starts. Euler observed that the task could not be done!! He noticed that each landmass has an odd number of bridges connecting it with the rest of the city. Hence a traveler departing, returning, departing, and so forth, an odd number of times would wind up departing on the last bridge, rendering impossible his return to his point of origin.
Let’s consider this gem of thinking one more time. Number the bridges contiguous with landmassA, 1, 2, and 3. Then if one starts the trip by departing A on bridge number one, he must return on bridge number two or number three, leaving only one more bridge. Clearly he must depart on that bridge not yet traveled on – and that makes all the difference! He cannot end his trip on landmassA.
Euler observed that the sizes of the land masses as well as the lengths and shapes of the bridges were irrelevant. Consider, therefore, a diagram representing the landmasses as dots and the bridges as lines, as in Figure 10-2 .
Figure 10-2
Notice the irrelevance of the weird shapes of the bridges meeting at B. The lengths of the lines are, likewise, unimportant. For that matter, so are the precise locations of the dots labeled A, B, C, andD.
In the spirit of Euler, a graph is defined as follows. A graph G is a collection of dots (more commonly called vertices, as we shall call them from now on), and a collection of lines (callededges), each line rendering a pair of vertices adjacent, that is, the edge links the two vertices. The specific layout, or representation, of the graph doesn’t matter, as long as the adjacencies and nonadjacencies are preserved. Imagine an airline graph in which London, Paris, and New York City are vertices and the edges between them represent direct flights on Pack’em-In Airways. The issue is simply a yes-or-no question. Which cities are connected by flights? The graph of Figure 10-3 answers this exciting question. Can you guess what N, L and P represent? Are we concerned with the ∠NLP, that is, the angle made by edges NL and LP? Of course not. The edges could just as well be curved.
Figure 10-3
Incidentally, in this book we shall not consider graphs in which a single pair of vertices may be linked by more than one edge, as in the graph of the seven bridges problem, where vertices A and Bare linked by two edges. Such graphs are today called multigraphs and are important in certain transportation problems, for example, in which several airlines fly between various pairs of cities.
The graph G of Figure 10-4 will be used to illustrate several concepts in graph theory. You may interpret this graph any way you wish. Some will think of the vertices as cities and the edges as flights. Others may view the vertices as atoms in a molecule. The edges will then presumably represent bonds between some of the atoms. The vertices may, in a more animated manner, represent members of the board of directors of a company! An edge between two vertices might indicate that they work well together. In fact entire books have been written on the applications of graph theory to a host of different situations. Ah … before we forget, here is the graph.
Figure 10-4
The degree of a vertex is the number of edges touching it (technically, incident with it). Thus the degree of vertex g in graph G above is 4. This can be written compactly as deg (g) = 4. Graphs are usually identified by capital letters and the vertices are denoted by lowercase letters. Edges may also be labeled using small letters, but the common practice is to label an edge using the letters of the two vertices it is incident with. The rightmost edge in graph G above, for example, may be referred to as edge hj.
The set of vertices and the set of edges of a graph G are denoted V (G) and E (G), respectively. Many authors adhere to the convention that n and e represent the cardinalities (i.e., sizes) of the vertex set and edge set, respectively. In the above example,
V (G) = {a, b, c, d, e, f, g, h, i, j}
in which case n = 10, that is, graph G has ten vertices. You should be able to verify that
E (G) = {ac, be, cd, cg, dh, ef, eg, fg, gh, hi, hj}
implying that e = 11, that is, G has eleven edges. Vertices a, b, i, and j have degree 1 and are therefore called endvertices.
Euler established the following interesting fact, important enough to be called a theorem.
