Algorithms And Computation In Mathematics Volume

Algorithms and Computationin Mathematics Volume 5EditorsArjeh M. Cohen Henri CohenDavid Eisenbud Michael F. Singer Bernd Sturmfels

Dieter JungnickelGraphs, Networksand AlgorithmsThird EditionWith 209 Figures and 9 TablesABC

Dieter JungnickelUniversität AugsburgInstitut für Mathematik86135 AugsburgGermanyE-mail: jungnickel@math.uni-augsburg.deLibrary of Congress Control Number: 2007929271Mathematics Subject Classification (2000): 11-01, 11Y40, 11E12, 11R29ISSN 1431-1550ISBN 978-3-540-72779-8 Springer Berlin Heidelberg New YorkThis work is subject to copyright. All rights are reserved, whether the whole or part of the material isconcerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting,reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publicationor parts thereof is permitted only under the provisions of the German Copyright Law of September 9,1965, in its current version, and permission for use must always be obtained from Springer. Violations areliable for prosecution under the German Copyright Law.Springer is a part of Springer Science Business Mediaspringer.comc Springer-Verlag Berlin Heidelberg 2008 The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply,even in the absence of a specific statement, that such names are exempt from the relevant protective lawsand regulations and therefore free for general use.A EX macro packageTypesetting by the author and SPi using a Springer LTCover design: design & production GmbH, HeidelbergPrinted on acid-free paperSPIN: 1206318546/SPi543210

A mathematician, like a painter or a poet,is a maker of patterns.If his patterns are more permanent than theirs,it is because they are made with ideas.G. H. HardyTo my teacher, Prof. Hanfried Lenz

Preface to the Third EditionThe show must go on.Ira GershwinThis new third edition has again been thoroughly revised, even though thechanges are not as extensive as in the second edition. Of course, the generalaims of the book have remained the same.In particular, I have added some additional material, namely two newsections concerning graphical codes (which provides a less obvious area of application and, as I hope, might also interest the reader in the important fieldof coding theory) and about two dozen further exercises (as usual, with solutions). I have also discussed and referenced recent developments, especiallyfor the travelling salesman problem, where truly impressive new world recordshave been achieved. Moreover, the presentation of the material has been improved in quite a few places, most notably in the chapters on shortest pathsand colorings. In addition to this, many smaller changes and corrections havebeen made, and the proof of several theorems have been rewritten to makethem more transparent, or more precise.Again, I thank my students and assistants for their attention and interestas well as the input they provided. Moreover, I am indebted to several readerswho alerted me to some (fortunately, more or less minor) problems; and I am,of course, also grateful for the encouraging comments I have received.Augsburg, May 2007Dieter Jungnickel

Preface to the Second EditionChange is inevitable.Change is constant.Benjamin DisraeliWhen the first printing of this book sold out in a comparatively short time,it was decided to reprint the original edition with only small modifications:I just took the opportunity to correct a handful of minor mistakes and toprovide a few updates to the bibliography. In contrast, the new second editionhas been thoroughly revised, even though the general aims of the book haveremained the same. In particular, I have added some new material, namelya chapter on the network simplex algorithm and a section on the five colortheorem; this also necessitated some changes in the previous order of thepresentation (so that the numbering differs from that of the first edition,beginning with Chapter 8). In addition to this, numerous smaller changesand corrections have been made and several recent developments have beendiscussed and referenced. There are also several new exercises.Again, I thank my students and assistants for their attention and interestas well as the input they provided. Moreover, I am particularly grateful totwo colleagues: Prof. Chris Fisher who read the entire manuscript and whosesuggestions led to many improvements in the presentation; and Priv.-Doz.Dr. Bernhard Schmidt who let me make use of his lecture notes on the networksimplex algorithm.Augsburg, September 2004Dieter Jungnickel

Preface to the First EditionThe algorithmic way of life is best.Hermann WeylDuring the last few decades, combinatorial optimization and graph theoryhave – as the whole field of combinatorics in general – experienced a particularly fast development. There are various reasons for this fact; one is, forexample, that applying combinatorial arguments has become more and morecommon. However, two developments on the outside of mathematics may havebeen more important: First, a lot of problems in combinatorial optimizationarose directly from everyday practice in engineering and management: determining shortest or most reliable paths in traffic or communication networks, maximal or compatible flows, or shortest tours; planning connectionsin traffic networks; coordinating projects; solving supply and demand problems. Second, practical instances of those tasks which belong to operationsresearch have become accessible by the development of more and more efficient computer systems. Furthermore, combinatorial optimization problemsare also important for complexity theory, an area in the common intersection of mathematics and theoretical computer science which deals with theanalysis of algorithms. Combinatorial optimization is a fascinating part ofmathematics, and a lot of its fascination – at least for me – comes from itsinterdisciplinarity and its practical relevance.The present book focuses mainly on that part of combinatorial optimization which can be formulated and treated by graph theoretical methods;neither the theory of linear programming nor polyhedral combinatorics areconsidered. Simultaneously, the book gives an introduction into graph theory, where we restrict ourselves to finite graphs. We motivate the problems bypractical interpretations wherever possible.1 Also, we use an algorithmic pointof view; that is, we are not content with knowing that an optimal solutionexists (this is trivial to see in most cases anyway), but we are mainly interested in the problem of how to find an optimal (or at least almost optimal)1Most of the subjects we treat here are of great importance for practical applications, for example for VLSI layout or for designing traffic or communicationnetworks. We recommend the books [Ber92], [KoLP90], and [Len90].

XIIPrefacesolution as efficiently as possible. Most of the problems we treat have a goodalgorithmic solution, but we also show how even difficult problems can betreated (for example by approximation algorithms or complete enumeration)using a particular hard problem (namely the famous travelling salesman problem) as an example. Such techniques are interesting even for problems whereit is possible to find an exact solution because they may decrease the amountof calculations needed considerably. In order to be able to judge the qualityof algorithms and the degree of difficulty of problems, we introduce the basicideas of complexity theory (in an informal way) and explain one of the mainopen problems of modern mathematics (namely the question P NP?). In thefirst chapters of the book, we will present algorithms in a rather detailed manner but turn to a more concise presentation in later parts. We decided not toinclude any explicit programs in this book; it should not be too difficult for areader who is used to writing programs to transfer the given algorithms. Giving programs in any fixed programming language would have meant that thebook is likely to be obsolete within a short time; moreover, explicit programswould have obscured the mathematical background of the algorithms. However, we use a structured way of presentation for our algorithms, includingspecial commands based on PASCAL (a rather usual approach). The bookcontains a lot of exercises and, in the appendix, the solutions or hints for finding the solution. As in any other discipline, combinatorial optimization canbe learned best by really working with the material; this is true in particularfor understanding the algorithms. Therefore, we urge the reader to work onthe exercises seriously (and do the mere calculations as well).The present book is a translation of a revised version of the third edition ofmy German text book Graphen, Netzwerke und Algorithmen. The translationand the typesetting was done by Dr. Tilla Schade with my collaboration.The text is based on two courses I gave in the winter term 1984/85 andin the summer term 1985 at the Justus-Liebig-University in Gießen. As thefirst edition of the book which appeared in 1987 was received quite well,a second edition became necessary in 1990. This second edition was onlyslightly changed (there were only a few corrections and some additions made,including a further appendix and a number of new references), because it appeared a relatively short time after the first edition. The third edition, however, was completely revised and newly typeset. Besides several correctionsand rearrangements, some larger supplements were added and the referencesbrought up to date. The lectures and seminars concerning combinatorial optimization and graph theory that I continued to give regularly (first at theUniversity of Gießen, then since the summer term 1993 at the University ofAugsburg) were very helpful here. I used the text presented here repeatedly; Ialso took it as the basis for a workshop for high school students organized bythe Verein Bildung und Begabung. This workshop showed that the subjectstreated in this book are accessible even to high school students; if motivatedsufficiently, they approach the problems with great interest. Moreover, theGerman edition has been used regularly at various other universities.

PrefaceXIIII thank my students and assistants and the students who attended theworkshop mentioned above for their constant attention and steady interest.Thanks are due, in particular, to Priv.-Doz. Dr. Dirk Hachenberger and Prof.Dr. Alexander Pott who read the entire manuscript of the (German) thirdedition with critical accuracy; the remaining errors are my responsibility.Augsburg, May 1998Dieter Jungnickel