Basic Graph Theory
Graph theory began in 1736 when Leonhard Euler solved the well-known Königsberg bridge problem. This problem asked for a circular walk through the town of Königsberg (now Kaliningrad) in such a way as to cross over each of the seven bridges spanning the r
- PDF / 683,219 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 404 Views
Basic Graph Theory
It is time to get back to basics. John Major
Graph theory began in 1736 when Leonhard Euler (1707–1783) solved the well-known K¨ onigsberg bridge problem [Eul36].1 This problem asked for a circular walk through the town of K¨onigsberg (now Kaliningrad) in such a way as to cross over each of the seven bridges spanning the river Pregel once, and only once; see Fig. 1.1 for a rough sketch of the situation. When trying to solve this problem one soon gets the feeling that there is no solution. But how can this be proved? Euler realized that the precise shapes of the island and the other three territories involved are not important; the solvability depends only on their connection properties. Let us represent the four territories by points (called vertices), and the bridges by curves joining the respective points; then we get the graph also drawn in Fig. 1.1. Trying to arrange a circular walk, we now begin a tour, say, at the vertex called a. When we return to a for the first time, we have used two of the five bridges connected with a. At our next return to a we have used four bridges. Now we can leave a again using the fifth bridge, but there is no possibility to return to a without using one of the five bridges a second time. This shows that the problem is indeed unsolvable. Using a similar argument, we see that it is also impossible to find any walk—not necessarily circular, so that the tour might end at a vertex different from where it began—which uses each bridge exactly once. Euler proved even more: he gave a necessary and sufficient condition for an arbitrary graph to admit a circular tour of the above kind. We will treat his theorem in Sect. 1.3. But first, we have to introduce some basic notions. The present chapter contains a lot of definitions. We urge the reader to work on the exercises to get a better idea of what the terms really mean. Even though this chapter has an introductory nature, we will also prove a couple of nontrivial results and give two interesting applications. We warn the reader that the terminology in graph theory lacks universality, although this improved a little after the book by Harary [Har69] appeared. 1 See
[Wil86] and [BigLW76].
D. Jungnickel, Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, DOI 10.1007/978-3-642-32278-5 1, © Springer-Verlag Berlin Heidelberg 2013
1
2
1
Basic Graph Theory
Fig. 1.1 The K¨ onigsberg bridge problem
1.1 Graphs, Subgraphs and Factors A graph G is a pair G = (V, E) consisting of a finite2 set V = ∅ and a set E of two-element subsets of V . The elements of V are called vertices. An element e = {a, b} of E is called an edge with end vertices a and b. We say that a and b are incident with e and that a and b are adjacent or neighbors of each e other, and write e = ab or a — b. Let us mention two simple but important series of examples. The complete graph Kn has n vertices (that is, |V | = n) and all two-element subsets of V as edges. The complete bipartite graph Km,n has as vertex set the disjoint union of a set
Data Loading...
