Graphs, networks and algorithms
This new edition has been thoroughly revised and updated, even though the changes are less extensive than above editions. Of course, the general aims of the book have remained the same. In particular, some material has been added: more on NP-completeness (especially on dominating sets), a section on the Gallai-Edmonds structure theory for matchings, and about a dozen additional exercises—as always, with solutions. Moreover, the 1-factor theorem has been completely rewritten: contains a short direct proof for the more general Berge-Tutte formula. Several recent research developments are discussed and quite a few references have been added.
With update material, additional exercises and new references, this thoroughly revised new edition of this book retains the excellent attributes yet considered: it is clear writing, understandable, well-written, good organization, comprehensive coverage of essential theory, self-contained, highly recommended and well-chosen applications, that it convert in an excellent, challenging, intriguing, and powerful textbook, due to the substantial development effort.
This standard book beginning from the very basic definitions of graph theory, quickly creating and building an account of theorems, lemmas, and finally, a complete collection of algorithms on graphs and networks. There are many exercises and examples, and the list of references is extensive. Here, a call to the reader, for to work on the exercises to get a better idea of what the terms really mean.
This book is a first course or class on graphs, networks and algorithms, and is indispensable for everybody who has to teach combinatorial optimization. The well-worked solutions to the exercises, or hints for some, are indispensable for the students, or readers, does not remain helpless. It is very helpful and suitable for graduate courses in combinatorics, as well as for independent study and research by students, teachers, professionals and researcher in this area. In short, the excellent book of Jungnickel, ought to available for reference.
The book contains preface to above editions, list of figures (p. i-xx), fifteen chapters: 1.-Basic Graph Theory 2.-Algorithms and Complexity 3.- Shortest Paths 4.-Spanning Trees 5.-The Greedy Algorithm 6.-Flows 7.-Combinatorial Applications 8.-Connectivity and Depth First Search 9.-Colorings 10.-Circulations 11.-The Network Simplex Algorithm 12.-Synthesis of Networks 13.-Matchings 13.- Weighted Matchings, 15.-A Hard Problem: The TSP-Appendices on some NP-Complete Problems, on the solutions for chapter 1 to 15, and on the list of Symbols – Bibliography - Index, in 675 pages.
The first chapter, Basic Graph Theory, (pages 1-33), contains a lot of definitions, and began with an introduction to the well-known Königsberg bridge problem, solved by Leonard Euler in 1736, who established that the solvability depends only on their connection properties. This led to the abstract notion of a graph. Actually, Euler proved much more: he gave a necessary and sufficient condition for an arbitrary graph to admit such a circular walk. His theorem is one of the highlights in the introductory Chap. 1, where we deal with some of the most fundamental notions in graph theory: paths, cycles, connectedness, 1-factors, trees, Euler tours and Hamiltonian cycles, the travelling salesman problem, drawing graphs in the plane, and directed graphs. Then also see a first application, namely setting up a schedule for a tournament, say in soccer or basketball, where each of the 2n participating teams should play against each of the other teams exactly twice, once at home and once away.
In the second chapter, Algorithms and Complexity, (pages 35-63), on study in an intuitive manner what an algorithm is and develop a way to measure the quality of algorithms. In particular, on consider some basic aspects of graph theoretic algorithms such as, for example, the problem of how to represent a graph. The different kinds of representation: edges, incidence, adjacency, matrices, and so on, are given. On formulate with more detail the Hierholzer´s algorithm, in Pascal-like language which allows this book to be used in courses to both on graph theory, combinatorial optimization, or computer science algorithms. Moreover, on introduce some rules for how algorithms are to be described, and on need a way to formulate the algorithms deal with. On illustrate and study these concepts quite thoroughly using two specific examples, namely Euler tours and acyclic digraphs. At the end of the chapter on consider a class of apparently very difficult problems (the so-called NP-complete problems) which plays a central role in complexity theory; on will meet this type of problem over and over again in this book. On deal with five NP-complete problems as the vertex cover, independent set, clique problem, dominating set and the Hamiltonian circuit.
In the third chapter, Shortest Paths, (pages 65-102), on know that one of the most common applications of graphs in everyday life is representing networks for traffic or for data communication. The schematic map of the any motorway system in the official guide, the railroad or bus lines in a public transportation system, and the network of routes an airline offers are routinely represented by graphs. Therefore, it is obviously of great practical interest to study paths in such graphs. In particular, on often look for paths which are good or even best in some respect: sometimes the shortest or the fastest route is required, sometimes on want the cheapest path or the one which is safest—for example, on want the route where on are least likely to encounter a speed-control installation. Thus on study shortest paths in graphs and digraphs in this chapter, i.e., this is a topic whose interest extends far beyond traffic networks. On present some useful theoretical concepts (e.g., the Bellman equations, shortest path threes, acyclic networks and path algebras) as well as the most important algorithms for finding shortest paths (in particular, breadth first search, Dijkstra´s algorithm, and Floyd and Warshall´s algorithm). On also discuss two applications, namely to project scheduling and to finding optimal connections in a public transportation system.
In the fourth chapter, Spanning Trees, (pages 103-134), on obtained some basic results on trees, including the number of trees on n vertices. In this chapter, on study this important class of graphs, the spanning trees, in considerably more detail. After some further characterizations of trees, on study another way of determining the number of trees on n vertices which actually applies more generally: it allows one to compute the number of spanning trees in any given connected graph. Following these theoretical results, the major part of the chapter will be devoted to a network optimization problem, namely to finding a spanning tree for which the sum of all edge lengths is minimal. This problem has many 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 that connection. Other possible interpretations are tasks like establishing traffic connections (for cars, trains or planes) or designing a network for TV broadcasts. On present an interesting characterization of minimal spanning trees and use this criterion to establish the most important algorithms for determining such a tree, namely those of Prim, Kruskal, and Boruvka. Following this, on discuss several further applications (e.g., the bottleneck problem) and spanning trees with additional restrictions. Also on consider Steiner trees (these are trees where it is allowed to add some new vertices) and arborescences (directed trees).
The fifth chapter, The Greedy Algorithm, (pages 135-161), study a method for optimizing over certain set systems, the so-called greedy algorithm. More precisely, it is used for maximizing a weight function on so-called independence systems, the classical instance being the system of spanning forests of a graph. The greedy strategy is rather short-sighted: one always selects the element which seems best at the moment. In other words, among all the admissible elements, one chooses that with maximal weight and adds it to the solution being constructed. In general, this simple-minded strategy will not work, but for a certain class of structures playing a very important part in combinatorial optimization, the so-called matroids, it indeed leads to optimal solutions. Actually, matroids may even be characterized by the fact that the greedy algorithm works for them, but there are other possible definitions. On look at various other characterizations of matroids and also consider the notion of matroid duality. Following this, on establish the greedy algorithm as an approximation method for maximization on independence systems which are not matroids. On examine the efficiency of this approach, that is, on derive bounds for the ratio between the solution given by the greedy algorithm and the optimal solution, and also look at the problem of minimization on independence systems. Finally, in the last section, on discuss some further generalizations of matroids and their relationship to the greedy algorithm.
In the sixth chapter, Flows, (pages 163-218), on investigate flows in networks: how much can be transported in a network from a given source s to a specified sink t if the capacities of the connections are prescribed? Such a network might model a system of pipelines, a water supply system, or a system of roads. With its many applications, the theory of flows is one of the most important parts of combinatorial optimization. In Chap. 7 on encountered several applications of the theory of flows within combinatorics, and flows and related notions will appear again and again throughout the book. Because of their fundamental importance, on discuss network flows in considerable depth. In particular, on give detailed presentations of four of the most important algorithms solving this problem, namely the Ford and Fulkerson´s labeling algorithm, a modification of this algorithm by Edmonds and Karp, Dinic´s algorithm, the Malhotra, Kumar and Mahaswari´s (MKM) algorithm, for constructing blocking flows, and the preflow-push of Goldberg and Tarjan´s algorithm, surely the algorithm most widely currently.
In the seventh chapter, Combinatorial Applications, (pages 219-249), on use the theorems of Ford and Fulkerson about maximal flows to prove some central results in combinatorics. More precisely, on use flow theory to study disjoint paths in graphs (Menger´s theorem), matchings in bipartite graphs (König´s theorem), transversals of set families (the marriage theorem), the combinatorics of matrices, partitions of directed graphs (Dilworth´s theorem), partially ordered sets, parallelisms of complete designs (Baranyai´s theorem), and the supply and demand, the Gale-Ryser´s theorem. In particular, transversal theory can be developed from the theory of flows on networks; this approach was first suggested in 1962 in the book by Ford and Fulkerson. Compared with the usual alternative approach, of taking Philip Hall’s marriage theorem—which we will treat in Sect. 7.3—as the starting point of transversal theory, this way of proceeding, has a distinct advantage: it also yields algorithms allowing explicit constructions for the objects in question.
The eighth chapter, Connectivity and Depth First Search, (pages 251-273), treat algorithmic questions concerning k-connectivity and strong connectivity. To this end, on introduce a further important strategy for searching graphs and digraphs (besides BFS), namely depth first search—which may also be thought of as a strategy for traversing a maze. In addition, on present various theoretical results, such as characterizations of 2-connected graphs and of edge connectivity.
In the ninth chapter, Colorings, (pages 275-293), on look at a subject occurring quite often in graph theory: colorings. The two fundamental major results in this area, namely the theorem of Brooks on vertex colorings and the theorem of Vizing on edge colorings, are given. As an aside, on explain the relationship between colorings and partial orderings, and briefly discuss perfect graphs. Moreover, on consider edge colorings of Cayley graphs; these are graphs which are defined using groups. Finally, on turn to map colorings: the Heawood’s five color theorem and report on the famous four color theorem are presented.
The tenth chapter, Circulations, (pages 295-358), considered the simplest kind of flow problems, namely the determination of maximal flows in a network, in considerable detail. The present chapter deals with generalizations of the flows that worked with so far. For example, quite often there are also lower bounds on the capacities of the edges given; or one may seek a maximal flow which is optimal with respect to a given cost function on the edges. To solve these (and even more general) problems, it proves helpful to remove the exceptional role of the source and sink vertices s and t by requiring the flow preservation condition for all vertices, including s and t. This leads to the notion of circulations on directed graphs. There are many interesting applications of this more general concept. To a large part, these cannot be treated using the theory of maximal flows as presented before; nevertheless, the methods of Chap. 6 will serve as fundamental tools for the more general setting. On shall begin with a rather thorough theoretical investigation of circulations and then develop efficient algorithms for finding an optimal circulation (or showing that no such circulation can exist), Klein´s algorithm, Busacker and Gowen´s algorithm, and the OPT´s algorithm, a modification of Ford-Fulkerson´s algorithm; this turns out to be considerably more difficult than determining an ordinary maximal flow. Finally, as an application of circulations, also consider the construction of rather good codes (a mathematical concept used to deal with data corruption by allowing the correction of errors) using the cycle spaces of graphs.
In the eleventh chapter, The Network Simplex Algorithm, (pages 359-378), for practical applications, by far the most useful optimization algorithm for solving linear programs is the celebrated simplex algorithm. This suggests trying to apply this algorithm also to problems from graph theory. Indeed, the most important network optimization problems may be formulated in terms of linear programs; this holds, for instance, for the determination of shortest paths, maximal flows, optimal flows, and optimal circulations. Nevertheless, a direct application of the usual simplex algorithm would make no sense, as the resulting linear programs would be unwieldy and highly degenerate. These two problems are avoided by using a suitable graph theoretic specialization of the simplex algorithm, the so-called network simplex algorithm. This algorithm is usually formulated in terms of a standard problem which we will introduce in the first section; all other problems of practical interest admit easy transformations to this problem. Throughout this book, on emphasize the graph theoretical aspects of combinatorial optimization while avoiding the theory of linear programming as much as possible. In view of this philosophy, it is very fortunate that the network simplex algorithm may be dealt with entirely in graph theoretic terms, with no need to appeal to linear programming; such a presentation will be given here.
The twelfth chapter, Synthesis of Networks, (pages 379-403), on worth that up to now on have considered flows or circulations only on a given network. But it is also quite interesting to study the reverse problem of designing a network—as economically as possible—on which a flow meeting given requirements can be realized. In practical terms, one might think of planning a system of roads. In the present chapter, on mainly study two types of network design problems. On the one hand, the case where all edges may be built with the same cost, and where we are looking for an undirected network with lower bounds on the maximal values of the flows between any two vertices. Both the analysis and design of such symmetric networks use so-called equivalent flow trees; this technique also has an interesting application for the construction of certain communication networks which will be the topic of section 12.4, cut trees, pages 395-399). On the other hand, addressed the question of how one may increase the maximal value of the flow for a given flow network by increasing the capacities of some edges by the smallest possible amount.
The thirteenth chapter, Matchings, (pages 405-439), deals with the problem of finding maximal matchings in arbitrary graphs; for the bipartite case, an efficient algorithms was already given in Sect. 7.2, (König´s theorem). In contrast to this case, it is not at all easy to reduce the general case to a flow problem, though this is possible (but beyond the scope of the present book). Nevertheless, the notion of an augmenting path can be modified appropriately to help enlarge a given matching. On present the best known efficient algorithm, which rests on this concept and is due to Edmonds; this turns out to be much more difficult than in the bipartite case. Also on present the most important theoretical results on matchings in general graphs: the 1-factor theorem of Tutte characterizing the graphs with a prefect matching, the more general Berge-Tutte formula giving the size of a maximal matching, and the Gallai-Edmonds structure theory.
In the fourteenth chapter, Weighted Matchings, (pages 441-479), on consider matchings of maximal cardinality. The present chapter discusses the more general case of weighted matchings, that is, the problem of finding a matching of maximal weight (with respect to a given weight function on the edges). In the bipartite case, this problem is equivalent to the assignment problem considered before, so that the methods discussed in chapter 10 apply. Nevertheless, on give a further algorithm for the bipartite case, the so-called Hungarian algorithm, as this is one of the best known and most important combinatorial algorithms. Then on proceed by explaining the connection between matching problems and the theory of linear programming, even though generally avoid linear programs in this book. On need this to see the deeper reason why the approach used in the Hungarian algorithm works: its success is due to the particularly simple structure of the corresponding polytope, and ultimately to the total unimodularity of the incidence matrix of a bipartite graph. In this context, the reason why the determination of maximal matchings (weighted or not) is considerably more difficult for arbitrary graphs than for bipartite ones will become apparent. As it would make little sense to describe an algorithm for the weighted matching problem in general graphs without using more of the theory of linear programming, no such algorithm is presented in this book. Nevertheless, on include three interesting applications of weighted matchings: the so-called Chinese postman problem (featuring a postman who wants an optimal route for delivering his mail); the determination of shortest paths for the case where edges of negative weight occur; and the decoding of graphical codes. On conclude the chapter with a few remarks about matching problems with certain additional restrictions—a situation which occurs quite often in practice; on see that such problems tend to be inherently more difficult.
The fifteenth chapter, A Hard Problem: The TSP, (pages 481-526), on concentrated on those optimization problems which allow efficient (that is, polynomial time) algorithms. In contrast, the final chapter deals with an archetypical NP-complete problem: the travelling salesman problem already introduced in the first chapter. It is one of the most famous and important problems in all of combinatorial optimization—with many fold applications in such diverse areas as logistics, genetics, telecommunications, and neuroscience—and has been the subject of extensive study for about 60 years. On see yet already that no efficient algorithms are known for NP-complete problems, and that it is actually quite likely that no such algorithms can exist. Now on address the question of how such hard problems—which regularly occur in practical applications—might be approached: one uses, for instance, approximation techniques, heuristics, relaxations, post-optimization, local search, and a complete enumeration. On explain these methods only for the TSP, but they are typical for dealing with hard problems in general. Also brie and explain the idea of a further extremely important approach—via polyhedra—to solving hard problems and present a list of notable large scale TSPs which were solved to optimality.
In the appendix A, Some NP-Complete Problems, (pages 527-536), on present a brief list of NP-problems, on restrict to problems which either mentioned before or are closely related to subject treated in this book. A much more intensive list can be found in the Bible of NP-problems, and the excellent text of Garey and Johnson (1979).
Appendix B: Solutions for Chapter, Chapter 1 to 15, (pages 537-621), contains solutions (or extended hints) to virtually all the proposed exercises. For difficult exercises, on include more details, if an exercise is of a purely computational nature, on usually state the result.
In the appendix C, List of Symbols, (pages 623-627), consist in two parts, the first about general symbols, contains those symbols which are more or less standard, and the second about special symbols, includes the special symbols of graph theory.
References, (pages 629-659), included an intensive and update bibliography, with 766 references.
Index, pages 661-675
Finally, in short, with update material, additional exercises and new references, this thoroughly revised fourth edition of this book retains the excellent attributes yet considered in above editions: it is clear writing, understandable, well-written, good organization, comprehensive coverage of essential theory, self-contained, highly recommended and well-chosen applications, that it convert in an excellent, challenging, intriguing, and powerful textbook, due to the substantial development effort.
This book is a first course or class on graphs, networks and algorithms, and is indispensable for everybody who has to teach combinatorial optimization. The well-worked solutions to the exercises, or hints for some, are indispensable for the students, or readers, does not remain helpless. It is very helpful and suitable for graduate courses in combinatorics, as well as for independent study and research by students, teachers, professionals and researcher in this area. In brief, the excellent book of Jungnickel, ought to available for reference.