an unconventional introduction to the internet.pdf

Chapter 1An unconventional introduction to the InternetHow Euler answered a perplexing question about a journey in the historic city of K¨ onigsberg, and how that journey can be re-shaped for more interesting purposes using Internet mathematics.The sketch map in Figure 1.1 is one of the most sacred images in the history of mathematics. Drawn by Swiss scientist Leonhard Paul Euler for an article published in 1736, it was intended to depict the connections among thedifferent districts of the city of K¨ onigsberg via seven bridges crossing the river Pregel. Why K¨ onigsberg; why Euler; and, above all, why are we discussing this here? For many centuries K¨ onigsberg, in the heart of Eastern Prussia, was one of the most important cities in the world. It deserved a better fate. Conqueredby manifold rulers, invaded by various armies, the city finally became part of the Soviet Union under the name of Kaliningrad at the end of World War II, during which brutal aerial bombardment had destroyed almost all of its historic monuments. Even the celebrated university Albertina, founded in the sixteenth century by Albert of Brandenburg, fell victim to the bombs. It was here that Immanuel Kant spent his entire life; and, according to a slightly du-bious tradition, it was also the origin of a tantalizing problem, finally brought to the attention of Euler in 1735. At that time, Euler held a position in the Imperial Russian Academy of Sciences founded by czar Peter the Great in St. Petersburg. The problem posedto him was very simple, and scarcely interesting at first glance. K¨ onigsberg had seven bridges connecting four districts of the city separated by the bends of the river. In Euler’s drawing the districts are indicated by A,B,C,D and the bridges by a,b,c,d,e,f,g. The historic center of the city was in A, the Kneiphof island, site of the University Albertina and (one century later) of Kant’s grave. The question raised by the curious citizens was whether it was possible to take a walk starting from an arbitrary point of the city, crossing each bridge exactly once, and returning to the starting point. If you have not seen this problem before, consider spending a few moments on it. It should1© 2012 by Taylor (b)with weighted arcs; or (c) with directed arcs.bridges without crossing any one of them more than once, if it exists, is called a Euler tour of the graph.Today pedestrians in K¨ onigsberg are rare, and rather than reflecting on appealing mathematical problems while strolling around their thoughts are more likely to be angrily directed at reckless drivers that jeopardize theirsafety or splash their clothes with filthy water from the puddles. But we like to believe that in Euler’s time the people of K¨ onigsberg were pleased to see their seven bridges problem solved so elegantly, although Euler’s approach referred to a general arrangement of districts and bridges, using the particular problem of K¨ onigsberg only as a starting point for the creation of a new theory. In the realm of graphs, Euler’s solution can be stated as follows:A graph admits a Euler tour if and only if all its vertices have even degree.If you have tried to solve the K¨ onigsberg problem yourself, you might have conceived a condition equivalent to the only if part of Euler’s theorem. In fact even if a single node has odd degree a tour cannot reach and then leave it, one or more times, without either traversing an incident arc twice or leaving one incident arc untraversed. In the case of K¨ onigsberg, for example, node B has odd degree three (in fact, all the districts of the city have an odd number of bridges) so the walk is impossible. To convince yourself of Euler’s assertion note that after entering district B from bridge a one can leave B from bridge b, enter again from bridge f, but at this point it would be impossible to leave B without crossing one of the three bridges again.More difficult is to prove the if part of the theorem, i.e., if all the vertices have even degree a Euler tour exists. We leave the proof of this part to any graph theory textbook. Even so, a reader with mathematical skills can at least try to prove it without any help. In particular a reader familiar with computer algorithms may produce a constructive proof, i.e., the scheme of a program© 2012 by Taylor hence it is a good starting point for reaching all authoritative districts directly. On the other hand A has two incoming links from the best hub B, meaning that it is a favorite place to visit in the area, and so some major art galleries have probably been established there. Just as for random walks, these results depend solely on the structure of the graph. We conclude this informal introduction by emphasizing that anyone who really wants to understand how the Internet and the Web are organized and function must be ready to study a fair bit of mathematics and computation© 2012 by Taylor & Francis Group, LLCAn unconventional introduction to the Internet7theory.3In fact, f。