{PDF} Graphs, Networks and Algorithms Dieter Jungnickel

From the reviews of the previous editions “…. The book is a first class textbook and seems to be indispensable for everybody who has to teach combinatorial optimization. It is very helpful for students, teachers, and researchers in this area. The author finds a striking synthesis of nice and interesting mathematical results and practical applications. … the author pays much attention to the inclusion of well-chosen exercises. The reader does not remain helpless; solutions or at least hints are given in the appendix. Except for some small basic mathematical and algorithmic knowledge the book is self-contained. …” K.Engel, Mathematical Reviews 2002 The substantial development effort of this text, involving multiple editions and trailing in the context of various workshops, university courses and seminar series, clearly shows through in this new edition with its clear writing, good organisation, comprehensive coverage of essential theory, and well-chosen applications. The proofs of important results and the representation of key algorithms in a Pascal-like notation allow this book to be used in a high-level undergraduate or low-level graduate course on graph theory, combinatorial optimization or computer science algorithms. The well-worked solutions to exercises are a real bonus for self study by students. The book is highly recommended. P .B. Gibbons, Zentralblatt für Mathematik 2005 Once again, the new edition has been thoroughly revised. In particular, some further 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 section on the 1-factor theorem has been completely rewritten: it now presents 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.

Table of Contents

Cover

Graphs, Networks and Algorithms, Fourth Edition

ISBN 9783642322778 ISBN 9783642322785

Preface to the Fourth Edition

Preface to the Third Edition

Preface to the Second Edition

Preface to the First Edition

Contents

Chapter 1: Basic Graph Theory

1.1 Graphs, Subgraphs and Factors
1.2 Paths, Cycles, Connectedness, Trees
1.3 Euler Tours
1.4 Hamiltonian Cycles
1.5 Planar Graphs
1.6 Digraphs
1.7 An Application: Tournaments and Leagues

Chapter 2: Algorithms and Complexity

2.1 Algorithms
2.2 Representing Graphs
2.3 The Algorithm of Hierholzer
2.4 How to Write Down Algorithms
2.5 The Complexity of Algorithms
2.6 Directed Acyclic Graphs
2.7 An Introduction to NP-completeness
2.8 Five NP-complete Problems

Chapter 3: Shortest Paths

3.1 Shortest Paths
3.2 Finite Metric Spaces
3.3 Breadth First Search and Bipartite Graphs
3.4 Shortest Path Trees
3.5 Bellman’s Equations and Acyclic Networks
3.6 An Application: Scheduling Projects
3.7 The Algorithm of Dijkstra
3.8 An Application: Train Schedules
3.9 The Algorithm of Floyd and Warshall
3.10 Cycles of Negative Length
3.11 Path Algebras

Chapter 4: Spanning Trees

4.1 Trees and Forests
4.2 Incidence Matrices
4.3 Minimal Spanning Trees
4.4 The Algorithms of Prim, Kruskal and Boruvka
4.5 Maximal Spanning Trees
4.6 Steiner Trees
4.7 Spanning Trees with Restrictions
4.8 Arborescences and Directed Euler Tours

Chapter 5: The Greedy Algorithm

5.1 The Greedy Algorithm and Matroids
5.2 Characterizations of Matroids
5.3 Matroid Duality
5.4 The Greedy Algorithm as an Approximation Method
5.5 Minimization in Independence Systems
5.6 Accessible Set Systems

Chapter 6: Flows

6.1 The Theorems of Ford and Fulkerson
6.2 The Algorithm of Edmonds and Karp
6.3 Auxiliary Networks and Phases
6.4 Constructing Blocking Flows
6.5 Zero-One Flows
6.6 The Algorithm of Goldberg and Tarjan
6.7 Further Reading

Chapter 7: Combinatorial Applications

7.1 Disjoint Paths: Menger’s Theorem
7.2 Matchings: K�nig’s Theorem
7.3 Partial Transversals: The Marriage Theorem
7.4 Combinatorics of Matrices
7.5 Dissections: Dilworth’s Theorem
7.6 Parallelisms: Baranyai’s Theorem
7.7 Supply and Demand: The Gale-Ryser Theorem

Chapter 8: Connectivity and Depth First Search

8.1 k-connected Graphs
8.2 Depth First Search
8.3 2-connected Graphs
8.4 Depth First Search for Digraphs
8.5 Strongly Connected Digraphs
8.6 Edge Connectivity

Chapter 9: Colorings

9.1 Vertex Colorings
9.2 Comparability Graphs and Interval Graphs
9.3 Edge Colorings
9.4 Cayley Graphs
9.5 The Five Color Theorem

Chapter 10: Circulations

10.1 Circulations and Flows
10.2 Feasible Circulations
10.3 Elementary Circulations
10.4 The Algorithm of Klein
10.5 The Algorithm of Busacker and Gowen
10.6 Potentials and epsilon-optimality
10.7 Optimal Circulations by Successive Approximation
10.8 A Polynomial Procedure REFINE
10.9 The Minimum Mean Cycle Cancelling Algorithm
10.10 Some Further Problems
10.11 An Application: Graphical Codes

Chapter 11: The Network Simplex Algorithm

11.1 The Minimum Cost Flow Problem
11.2 Tree Solutions
11.3 Constructing an Admissible Tree Structure
11.4 The Algorithm
Rule of the last blocking arc:
11.5 Efficient Implementations

Chapter 12: Synthesis of Networks

12.1 Symmetric Networks
12.2 Synthesis of Equivalent Flow Trees
12.3 Synthesizing Minimal Networks
12.4 Cut Trees
12.5 Increasing the Capacities

Chapter 13: Matchings

13.1 The Berge-Tutte Formula
13.2 Augmenting Paths
13.3 Alternating Trees and Blossoms
13.4 The Algorithm of Edmonds
13.5 The Gallai-Edmonds Structure Theorem
13.6 Matching Matroids

Chapter 14: Weighted Matchings

14.1 The Bipartite Case
14.2 The Hungarian Algorithm
14.3 Matchings, Linear Programs, and Polytopes
14.4 The General Case
14.5 The Chinese Postman
14.6 Matchings and Shortest Paths
14.7 Some Further Problems
14.8 An Application: Decoding Graphical Codes

Chapter 15: A Hard Problem: The TSP

15.1 Basic Definitions
15.2 Lower Bounds: Relaxations
The Assignment Relaxation
The MST Relaxation
The s-tree Relaxation
The LP Relaxation
15.3 Lower Bounds: Subgradient Optimization
15.4 Approximation Algorithms
15.5 Upper Bounds: Heuristics
15.6 Upper Bounds: Local Search
15.7 Exact Neighborhoods and Suboptimality
15.8 Optimal Solutions: Branch and Bound
15.9 Concluding Remarks

Appendix A: Some NP-Complete Problems

Appendix B: Solutions

B.1 Solutions for Chap. 1
B.2 Solutions for Chap. 2
B.3 Solutions for Chap. 3
B.4 Solutions for Chap. 4
B.5 Solutions for Chap. 5
B.6 Solutions for Chap. 6
B.7 Solutions for Chap. 7
B.8 Solutions for Chap. 8
B.9 Solutions for Chap. 9
B.10 Solutions for Chap. 10
B.11 Solutions for Chap. 11
B.12 Solutions for Chap. 12
B.13 Solutions for Chap. 13
B.14 Solutions for Chap. 14
B.15 Solutions for Chap. 15

Appendix C: List of Symbols

C.1 General Symbols
Sets
Mappings
Numbers
Matrices
Sets of numbers and algebraic structures
Miscellaneous
C.2 Special Symbols
Graphs and networks
Objects in graphs
Parameters for graphs
Mappings on graphs and networks
Matroids and independence systems
Matrices
Codes
Miscellaneous

References

Index