nach oben

1999 | Buch

Kapitel lesen Erstes Kapitel lesen

Graphs, Networks and Algorithms

verfasst von: Dieter Jungnickel

Verlag: Springer Berlin Heidelberg

Buchreihe : Algorithms and Computation in Mathematics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

From the reviews of the German edition:

"Combinatorial optimization, along with graph algorithms and complexity theory is booming. This book treats the most prominent problems which are polynomially solvable. The Traveling Salesman Problem is discussed as a paradigm of an NP-complete problem. The text is well written, most exercises are quite enlightening and the hints are clear. Algorithms are described very thoroughly. The list of references is impressive and gives good guidance for further reading.

The book can be recommended to beginners as an introductory text as well as for research and industry as a reference."

(OPTIMA)

In this corrected 2nd printing of the first edition the author has made some small modifications: some minor mistakes were corrected and updates to the bibliography provided.

Inhaltsverzeichnis

Frontmatter

1. Basic Graph Theory

Abstract

The history of Graph Theory begins with a paper by Euler (1736)¹ where he solved the well-known ‘Königsberger Brückenproblem’. This problem consists in finding a circular tour through Königsberg using each of the seven bridges over the river Pregel exactly once.

Dieter Jungnickel

2. Algorithms and Complexity

Abstract

In Theorem 1.3.1 we gave a characterization for Eulerian graphs: A graph G is Eulerian if and only if each vertex of G has even degree. This condition is easy to verify for any given graph. But how can we find an Euler tour in an Eulerian graph? The proof of Theorem 1.3.1 only shows that such a tour exists, but does not tell us how to find it (though it contains a hint of how to achieve this). We are looking for a method for constructing an Euler tour, an ‘algorithm’. In this book we generally look at problems from the algorithmic point of view: we want more than just theorems about existence or structure. As Lüneburg (1982) said: It is important that we can finally compute the objects we are working with. However, we will not go as far as giving concrete programs (in PASCAL, say); our algorithms will be described in a less formal way. Our main goal is to give an overview over the basic methods used in a very large area of mathematics; we can only achieve this (without exceeding the limits of this book) by omitting the details of programming techniques. Readers interested in concrete programs are referred to Syslo, Deo and Kowalik (1983) and Nijenhuis and Wilf (1978), where programs in PASCAL and FORTRAN, respectively, can be found.

Dieter Jungnickel

3. Shortest Paths

Abstract

One of the most common applications of graphs in everyday life is the representation of networks for traffic or data communication. The survey map of german motorways in the official guide ‘Autobahn Service’, the railroad or bus lines in some system of public transportation, or the network of routes an airline offers are represented as graphs without anybody being aware of it. Thus, it is obviously of great practical interest to study paths in such graphs. In particular, we often look for paths which are ‘good’ or even ‘best’ in some respect: Sometimes the shortest or the fastest route is required, sometimes we want the cheapest path or the one which is ‘safest’ (for example, we want the route where it is most unlikely that we encounter a speed control installation). We will mainly consider shortest paths in (directed) graphs in this chapter, and we will see that this question is not only of interest in traffic networks.

Dieter Jungnickel

4. Spanning Trees

Abstract

In this chapter, we have a closer look at trees which were introduced in Section 1.2. We begin by giving some further characterizations of trees and determining the number of trees on n vertices and, more generally, the number of spanning trees in a connected graph. The main part of this chapter is devoted to problems of the following kind: In some given network, we look for a spanning tree for which the sum of all lengths of edges is minimal. This problem has a lot of applications: For example, the vertices might represent cities we want to connect to a system supplying electricity; then the edges represent the possible connections and the length of an edge states how much it would cost to build the respective connection. Other possible interpretations are tasks like establishing traffic connections (for cars, trains or planes: ‘Connector Problem’), or building a network for TV broadcasts. Finally, we consider Steiner trees (these are trees where it is allowed to add some new vertices) and arborescences (the directed analogue of trees).

Dieter Jungnickel

5. The Greedy Algorithm

Abstract

In this chapter, we look at a generalization of the Algorithm of Kruskal, the so-called Greedy Algorithm. This algorithm can be used for maximization on ‘independence systems’ (as, for example, in the case of the Algorithm of Kruskal, the system of spanning forests of a graph). However, the strategy used is rather short-sighted: we always choose the element which seems best at the moment (that is, of all the admissible elements, we choose the element whose weight is maximal) and add it to the solution we are constructing (this explains the name!). In general, this strategy does not work, but for a certain class of structures, the so-called matroids (which play an important part in Combinatorial Optimization), it indeed leads to an optimal solution. In fact, this class of structures is characterized by the fact that the Greedy Algorithm works for them, but there are other possible definitions for matroids. We will see some other characterizations of matroids and look at the notion of duality of matroids.

Dieter Jungnickel

6. Flows

Abstract

In this chapter, we look at ‘flows’ in networks: How much can be transported in a network from some ‘source’ s to some ‘sink’ t if the ‘capacities’ of the connections are given? Such a network might be a model for a system of pipelines or a water supply system or for a system of roads. The theory of flows is one of the most important parts of Combinatorial Optimization; it has various applications as well in Mathematics as in other fields. The book by Ford and Fulkerson (1962) ‘Flows in Networks’, formerly the standard reference, is still worth reading; an extensive treatment is in the recent monograph by Ahuja, Magnanti and Orlin (1993). In Chapter 7, we will see several applications of the theory of flows within Combinatorics, and flows and related notions will appear again and again during the remainder of this book.

Dieter Jungnickel

7. Applications in Combinatorics

Abstract

In this chapter, we use the theorems of Ford and Fulkerson about maximal flows to prove some central theorems of Combinatorics. In particular, Transversal Theory can be developed from the theory of flows on networks; this approach was first suggested in the book by Ford and Fulkerson (1962) and is also used in the survey by Jungnickel (1986). Compared with the usual approach of taking the Marriage Theorem of Hall (1935) — which we treat in Section 7.3 — as the starting point of Transversal Theory (as in the book by Mirsky (1971b)), our way of proceeding has the advantage that we get algorithms for constructing the respective objects simultaneously, for example by specializing the Algorithm of Dinic (1970) in an appropriate way. We will study disjoint paths in graphs, matchings in bipartite graphs, transversals, combinatorics of matrices, partitions of directed graphs, partially ordered sets, parallelisms and the Supply-Demand-Theorem.

Dieter Jungnickel

8. Colourings

Abstract

This chapter treats a subject occurring quite often in Graph Theory, namely colourings. First, we show the relationship between colourings and partial orderings (as studied in Section 7.5) and mention ‘perfect’ graphs. Then we prove the two main theorems about colourings of vertices and edges (namely the Theorems of Brooks and Vizing). Finally, we consider edge colourings of Cayley graphs; these are graphs which are defined using groups. We will barely scractch the surface of a vast area in this chapter; for a detailed study of colouring problems we refer the reader to the monograph by Jensen and Toft (1995).

Dieter Jungnickel

9. Circulations

Abstract

In Chapter 6, we introduced the simplest kind of flow problems (namely the determination of maximal flows in a network); in Chapter 7, we studied the various applications of this theory. The present chapter treats generalizations of the flows we worked with so far. For example, it occurs quite often that, for some network, there are lower bounds on the capacities of the edges or a cost function on the edges given as well. To solve this kind of problem, it makes sense to remove the exceptional role of the vertices s and t and to require that the condition of flow preservation (F2) of Chapter 6 holds for each vertex in the network including s and t. Doing this, we obtain the notion of ‘circulation’ on a directed graph. As we will see, there are various new possibilites for applying this new notion. Not all of these can be treated using the theory of maximal flows we presented above; however, the methods of Chapter 6 are a central tool for the more general case.

Dieter Jungnickel

10. Synthesis of Networks

Abstract

Up to now, we have only considered flows or circulations, respectively, for a given network. However, the converse question is very interesting, too: For given conditions on the flow, construct a network (with as little effort as possible) on which such a flow would be possible. On the one hand, we consider the case where all edges can be built with the same cost and we are looking for an undirected network with lower bounds on the maximal values of a flow between any two vertices. We analyze such ‘symmetric networks’ via ‘equivalent flow trees’ and ‘equivalent cut trees’. This technique has an interesting application for the construction of certain communication networks; this is discussed in Section 10.4. On the other hand, we look at the question of how to increase the maximal value of the flow for a given flow network by increasing the capacities of some edges as economically as possible.

Dieter Jungnickel

11. Connectivity

Abstract

In the first chapter, we defined what ‘connected’ and ‘strongly connected’ means; we also introduced the notion of k-connectivity in Chapter 7. The Algorithm of Moore (BFS) we presented in Chapter 3 is an efficient method for determining the connected components of a graph. Now, in the present chapter, we mainly treat algorithmic questions concerning k-connectivity and strong connectivity for directed graphs. We develop a further strategy for searching (besides BFS), namely ‘Depth First Search’. This chapter also contains various theoretical results, for example characterizations of 2-connected graphs and of edge connectivity.

Dieter Jungnickel

12. Matchings

Abstract

This chapter is devoted to the problem of finding maximal matchings in arbitrary graphs; the bipartite case was treated in Section 7.2. Contrary to the bipartite case, the general case cannot be reduced immediately to a flow problem. However, we will see that the notion of an augmenting path can be modified appropriately. Kocay and Stone (1993) and Kocay and Stone (1995) showed that matchings can be treated in the context of Flow Theory by introducing special networks and flows satisfying certain symmetry conditions. Subsequently, Fremuth-Paeger and Jungnickel (1998a, 1998b, 1998c, 1998d, 1998e) provided a general theory based on this approach, including efficient algorithms. We will not present this rather involved theory because it would take up too much space, and refer the reader to the original sources instead.

Dieter Jungnickel

13. Weighted Matchings

Abstract

In the previous chapter, we studied matchings of maximal cardinality (‘cardinality matching’). The present chapter is devoted to weighted matchings, in particular to the problem of how to determine a matching of maximal weight in some network (G, w) (‘weighted matching’). In the bipartite case, this problem is equivalent to the ‘assignment problem’ (see Example 9.1.4), so that the methods introduced in Chapter 9 can be applied. However, we give a further algorithm for the bipartite case, the ‘Hungarian Algorithm’, which is one of the most popular and most important combinatorial algorithms. We proceed by showing the connection to the Theory of Linear Programming, which we need to understand why the approach used in the Hungarian Algorithm is successful (this is due to the particularly simple structure of the corresponding polytope and to the total unimodularity of the incidence matrix of a bipartite graph). In this context, it will also become clear why the determination of maximal (weighted) matchings is much more difficult for arbitrary graphs than for bipartite graphs and which significance the blossoms have. It makes no sense to describe an algorithm for this problem without introducing more of the Theory of Linear Programming, and for this reason, no such algorithm is included in this book.

Dieter Jungnickel

14. A Hard Problem: The TSP

Abstract

Up to now, we designed algorithms only for those optimization problems which allow an efficient (that is, polynomial) solution. This chapter is devoted to NP-complete problems; we use the Travelling Salesman Problem introduced in Chapter 1 and shown to be NP-complete in Chapter 2 as the standard example. We saw in Chapter 2 that NP-complete problems are a class of problems for which no good algorithms are known and it is quite likely even that no such algorithms exist. Now we consider the question how such ‘hard’ problems might be handled. Possible approaches include approximation techniques, heuristics, relaxations, post-optimization, local optimums, complete enumeration and several more. We explain all the techniques by using the TSP which can serve as a paradigm for a difficult problem.

Dieter Jungnickel

A. Solutions

Abstract

This appendix contains solutions or directions for solving almost all the exercises of this book. For difficult exercises, we give a more detailed solution, whereas for easy ones, we sometimes restrict ourselves to hints. If an exercise is a purely arithmetical problem, we state the result only. For some exercises, where the result is known already (from earlier considerations) or where the reader was required to do some experiments, we do not give any solution.

Dieter Jungnickel

B. List of Symbols

Abstract

This first part of the list contains some general symbols which are more or less standard. The special symbols of Graph and Matroid Theory will be treated in the next section.

Dieter Jungnickel

Backmatter

Titel: Graphs, Networks and Algorithms
verfasst von: Dieter Jungnickel
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-03822-2
Print ISBN: 978-3-662-03824-6
DOI: https://doi.org/10.1007/978-3-662-03822-2

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

1. Basic Graph Theory

2. Algorithms and Complexity

3. Shortest Paths

4. Spanning Trees

5. The Greedy Algorithm

6. Flows

7. Applications in Combinatorics

8. Colourings

9. Circulations

10. Synthesis of Networks

11. Connectivity

12. Matchings

13. Weighted Matchings

14. A Hard Problem: The TSP

A. Solutions

B. List of Symbols

Backmatter