دانلود کتاب Graph and Network Theory: An Applied Approach using Mathematica®

فهرست مطالب :

Contents Preface About this book Organisation of material in the book Part 1: Topics in network optimisation Part 2: Topics in classical graph theory Part 3: Topics in modern graph theory The intended audience Notation Acknowledgements Invitation List of Algorithms List of Biographical Notes PART 1 Topics in network optimisation Chapter 1 An introduction to graphs 1.1 Introduction 1.2 What is a graph? 1.3 Special graphs 1.4 Operations on graphs 1.5 Degree sequences 1.6 Isomorphisms 1.7 Directed graphs 1.8 Representing a (di)graph on a computer 1.9 Multigraphs and pseudographs Exercises Computer exercises Projects Further reading Chapter 2 Graph connectedness 2.1 Introduction 2.2 Connected graphs 2.3 Distance in graphs 2.4 Cut-vertices and bridges 2.5 Directed graphs 2.6 Further study of connectivity in graphs Exercises Computer exercises Projects Further reading Chapter 3 Algorithmic complexity 3.1 Introduction 3.2 "Big O" notation 3.3 A classification scheme for decision problems 3.4 Polynomial-time reducibility and ness 3.5 Decision problems vs. computation problems Exercises Computer exercises Projects Further reading Chapter 4 Optimal paths 4.1 Introduction 4.2 Distance in weighted graphs 4.3 Shortest paths in weighted graphs 4.3.1 Dijkstra's algorithm 4.3.2 Floyd’s algorithm 4.4 Longest paths in weighted digraphs Exercises Computer exercises Projects Further reading Chapter 5 Trees 5.1 Introduction 5.2 Properties of trees 5.3 Constructing minimum spanning trees 5.3.1 Kruskal's algorithm 5.3.2 Prim's algorithm 5.4 Rooted trees 5.5 Depth-first tree searches Exercises Computer exercises Projects Further reading Chapter 6 Location problems 6.1 Introduction 6.2 The centre of a graph 6.3 The median of a graph 6.4 General centres and medians 6.5 Absolute centres and medians 6.6 General absolute centres and medians Exercises Computer exercises Projects Further reading Chapter 7 Maximum flow networks 7.1 Introduction 7.2 Preliminary concepts 7.3 The max-flow min-cut theorem 7.4 The max-flow min-cut algorithm Exercises Computer exercises Projects Further reading Chapter 8 Minimum-cost network flows 8.1 Introduction 8.2 Network flow and linear programming theory 8.3 Basic feasible solutions 8.4 The network simplex algorithm Exercises Computer exercises Projects Further reading PART 2 Topics in classical graph theory Chapter 9 Matchings 9.1 Introduction 9.2 Maximum matchings 9.3 Vertex covers 9.4 Tutte's theorem 9.5 The Tutte-Berge formula 9.6 The binding number of a graph 9.7 Matching algorithms for bipartite graphs 9.7.1 Method I: Network flows 9.7.2 Method II: Augmenting paths 9.8 A matching algorithm for general graphs 9.9 A weighted matching algorithm 9.9.1 Linear programming background 9.9.2 The maximum weight matching problem 9.9.3 Outline of the maximum weight matching algorithm 9.9.4 A worked example Exercises Computer exercises Projects Suggestions for further background reading Further reading Chapter 10 Eulerian graphs 10.1 Introduction 10.2 Finding eulerian circuits and trails 10.3 The Chinese postman problem 10.4 Other postman problems 10.5 Eulerian digraphs 10.6 Fleury's algorithm for digraphs Exercises Computer exercises Projects Further reading Chapter 11 Hamiltonian graphs 11.1 Introduction 11.2 Which graphs are hamiltonian? 11.3 The closure function 11.4 The travelling salesman problem 11.4.1 The nearest-neighbour heuristic 11.4.2 A lower bound on TSP solutions 11.4.3 Instances of the TSP satisfying the triangle inequality 11.4.4 Christofides' algorithm 11.5 Almost traceability and almost hamiltonicity 11.5.1 Hypotraceability of graphs 11.5.2 Hypohamiltonicity of graphs 11.5.3 Hypotraceability and hypohamiltonicity of digraphs Exercises Computer exercises Projects Further reading Chapter 12 Graph connectivity 12.1 Introduction 12.2 Cuts and separating sets 12.3 Blocks 12.4 Connectivity and edge connectivity 12.5 Menger's Theorem 12.5.1 The vertex form of Menger's Theorem 12.5.2 The edge form of Menger’s Theorem 12.6 Computing the connectivity of a graph Exercises Computer exercises Projects Further reading Chapter 13 Planarity 13.1 Introduction 13.2 Properties of planar graphs 13.3 Which graphs are planar? 13.3.1 Contractions, subdivisions and graph minors 13.3.2 Kuratowski's characterisation of planar graphs 13.3.3 Wagner's characterisation of planar graphs 13.3.4 A planarity testing algorithm 13.4 The crossing number of a graph 13.5 Other parameters related to planarity 13.5.1 The rectilinear crossing number 13.5.2 The thickness of a graph 13.5.3 The coarseness of a graph 13.6 Embedding on surfaces other than the plane 13.6.1 The genus of a surface 13.6.2 The generalised crossing number of a graph 13.6.3 The genus of a graph 13.7 The Robertson-Seymour theorems Exercises Computer exercises Projects Further reading Chapter 14 Graph colouring 14.1 Introduction 14.2 Vertex colouring 14.2.1 k-Colourability 14.2.2 Criticality and the chromatic number of a graph 14.2.3 Other bounds on the chromatic number of a graph 14.2.4 Computing good vertex colourings heuristically 14.2.5 An exact algorithm for vertex colouring 14.3 Edge colouring 14.3.1 The chromatic index of a graph 14.3.2 Criticality with respect to X'(G) 14.3.3 Computing the chromatic index of a graph Exercises Computer exercises Projects Further reading Chapter 15 Oriented graphs 15.1 Introduction 15.2 Strong orientations 15.3 Tournaments 15.4 Higher-order rankings in tournaments 15.5 Almost traceable and almost hamiltonian orient digraphs Exercises Computer exercises Projects Further reading PART 3 Topics in modern graph theory Chapter 16 Domination in graphs 16.1 Introduction 16.2 The domination number 16.2.1 Minimal dominating sets 16.2.2 Bounds on the domination number 16.2.3 Vizing's Conjecture 16.2.4 Nordhaus-Gaddum type bounds 16.2.5 NP-completeness of the domination problem 16.2.6 A polynomial-time tree domination algorithm 16.2.7 The upper domination number 16.3 The independent domination number 16.3.1 The domination inequality chain 16.3.2 <γ,i>-graphs 16.3.3 Domination-perfect graphs 16.3.4 -graphs 16.3.5 Bounds for K(1, k)-free graphs 16.3.6 Bounds in terms of maximum degree 16.3.7 Bounds relating i and γ 16.3.8 Bounds relating i and n 16.3.9 Bounds for bipartite graphs 16.3.10 Bounds for trees 16.3.11 Bounds for cubic graphs 16.3.12 Bounds for regular graphs 16.3.13 Bounds for triangle-free graphs 16.3.14 Nordhaus-Gaddum type bounds 16.4 The irredundance number 16.4.1 Maximal irredundant sets 16.4.2 The domination inequality chain revisited 16.4.3 Irredundance perfect graphs 16.4.4 Bounds involving the minimum and maximum degrees 16.5 Total domination 16.5.1 Minimal total dominating sets 16.5.2 Bounds on the total domination number 16.5.3 Bounds for graphs with minimum degree at least two 16.5.4 Bounds for graphs with minimum degree at least three 16.5.5 Bounds for graphs with minimum degree at least four 16.5.6 A heuristic bound 16.5.7 Summary of bounds 16.5.8 The upper total domination number 16.5.9 Total domination edge critical graphs Exercises Computer exercises Projects Further reading Chapter 17 Ramsey theory 17.1 Introduction 17.2 The classical two-colour Ramsey problem 17.3 Two-colour extensions 17.4 The multi-colour Ramsey problem 17.5 Multipartite Ramsey theory 17.6 Requirements other than that of a subgraph Exercises Computer exercises Projects Further reading Chapter 18 Extremal graph theory 18.1 Introduction 18.2 Cycles in graphs 18.3 Turán's theorem 18.4 Zarankiewicz numbers 18.5 Framing numbers 18.5.1 On cliques and independent sets 18.5.2 On cliques and bicliques 18.6 Diameter two graphs of minimum size 18.7 Diameter two critical graphs of maximum size Exercises Further reading Chapter 19 Graph enumeration 19.1 Counting labelled graphs 19.1.1 Labelled simple graphs of specified order and size 19.1.2 Labelled trees and rooted labelled trees 19.1.3 Genealogical registers 19.2 Counting unlabelled trees 19.2.1 Rooted trees 19.2.2 Trees that are not rooted 19.3 Pólya's enumeration theorem 19.3.1 Permutations 19.3.2 Permutation groups and (ordered) pair groups 19.3.3 The cycle index of a permutation group 19.3.4 The theorem in the context of graph enumeration 19.4 Using Pólya's theorem to enumerate graphs 19.4.1 Unlabelled graphs of specified order and size 19.4.2 Multigraphs of specified order, size and multiplicity 19.4.3 Unlabelled digraphs of specified order and size Exercises Computer exercises Projects Further reading Chapter 20 The probabilistic method 20.1 Introduction 20.2 Ramsey theory 20.3 Linearity of expectation 20.3.1 Bipartite subgraphs 20.3.2 Hamiltonian paths 20.3.3 Independent sets 20.3.4 Dominating sets 20.4 Random graphs 20.4.1 Colourings 20.4.2 Lovász Local Lemma Exercises Projects Further reading Index Subject index Author index