Concisely written, gentle introduction to graph theory suitable as a textbook or for self-study Graph-theoretic applications from diverse fields (computer science, engineering, chemistry, management science) 2nd ed. includes new chapters on labeling and communications networks and small worlds, as well as expanded beginner's material Many additional changes, improvements, and corrections resulting from classroom use
Author(s): W.D. Wallis
Edition: 2nd
Publisher: Birkhäuser Boston
Year: 2007
Language: English
Pages: 282
Tags: Математика;Дискретная математика;Теория графов;
Cover......Page 1
Title Page......Page 5
Copyright Page......Page 6
Preface to the Second Edition......Page 9
Preface to the First Edition......Page 11
Outline of Topics......Page 12
Acknowledgments......Page 13
Table of Contents......Page 15
List of Figures......Page 19
1.1 Sets, Binary Relations and Graphs......Page 23
1.2 Some Definitions......Page 28
1.3 Degree......Page 35
2.1 Basic Ideas......Page 41
2.2 Radius, Diameter and Eccentricity......Page 45
2.3 Weighted Distance......Page 47
2.4 Euler Walks......Page 51
2.5 Hamilton Cycles......Page 56
2.6 The Traveling Salesman Problem......Page 61
3.1 Cutpoints and Bridges......Page 65
3.2 Blocks......Page 68
3.3 Connectivity......Page 71
4.1 Characterizations of Trees......Page 75
4.2 Spanning Trees......Page 77
4.3 Minimal Spanning Trees......Page 82
5.1 Finite Fields and Vector Spaces......Page 87
5.2 The Power Set as a Vector Space......Page 88
5.3 The Vector Spaces Associated with a Graph......Page 90
5.4 The Cutset Subspace......Page 92
5.5 Bases and Spanning Trees......Page 94
6.1 Definitions; One-Factorizations......Page 99
6.2 Tournament Applications of One-Factorizations......Page 105
6.3 A General Existence Theorem......Page 107
6.4 Graphs Without One-Factors......Page 111
7.1 Vertex Colorings......Page 115
7.2 Brooks' Theorem......Page 119
7.3 Counting Vertex Colorings......Page 121
7.4 Edge-Colorings......Page 126
7.5 Class 2 Graphs......Page 129
8.1 Representations and Crossings......Page 135
8.2 Euler's Formula......Page 138
8.3 Maps, Graphs and Planarity......Page 141
9.1 Introduction; Graceful Labelings......Page 145
9.2 Edge-Magic Total Labeling......Page 148
9.3 Edge-Magic Labelings of Complete Graphs......Page 154
10.1 The Graphical Case of Ramsey's Theorem......Page 161
10.2 Ramsey Multiplicity......Page 166
10.3 Application of Sum-Free Sets......Page 168
10.4 Bounds on Classical Ramsey Numbers......Page 171
10.5 The General Case of Ramsey's Theorem......Page 174
11.1 Basic Ideas......Page 177
11.2 Orientations and Tournaments......Page 181
11.3 Directed Euler Walks......Page 185
12.1 Activity Digraphs......Page 189
12.2 Critical Path Analysis......Page 192
12.3 Critical Paths Under Uncertainty......Page 198
13.1 Transportation Networks and Flows......Page 203
13.2 Maximal Flows......Page 208
13.3 The Max Flow Min Cut Theorem......Page 214
13.4 The Max Flow Min Cut Algorithm......Page 215
13.5 Supply and Demand Problems......Page 222
14.1 Computation Time......Page 227
14.2 Data Structures......Page 230
14.3 Some Graph Algorithms......Page 231
14.4 Intractability......Page 235
15.1 Preliminaries......Page 239
15.2 Functions on Graphs......Page 240
15.3 Classes of Graphs......Page 242
15.4 Small-World Graphs......Page 244
References......Page 247
Hints......Page 253
Answers and Solutions......Page 257
Index......Page 277
