Atnaujinkite slapukų nuostatas

Introduction to Graph Theory (Classic Version) 2nd edition [Minkštas viršelis]

4.33/5 (6 ratings by Goodreads)
Kitos knygos pagal šią temą:
Introduction to Graph Theory (Classic Version) 2nd editionDidesnis paveikslėlis
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9780131437371.html
Raktažodžiai:
For undergraduate or graduate courses in Graph Theory in departments of mathematics or computer science.























This title is part of the Pearson Modern Classics series. Pearson Modern Classics are acclaimed titles at a value price. Please visit www.pearsonhighered.com/math-classics-series for a complete list of titles.







This text offers a comprehensive and coherent introduction to the fundamental topics of graph theory. It includes basic algorithms and emphasizes the understanding and writing of proofs about graphs. Thought-provoking examples and exercises develop a thorough understanding of the structure of graphs and the techniques used to analyze problems. The first seven chapters form the basic course, with advanced material in Chapter 8.
Preface xi
Chapter 1 Fundamental Concepts 1(66)
1.1 What Is a Graph?
1(18)
The Definition
1(2)
Graphs as Models
3(3)
Matrices and Isomorphism
6(5)
Decomposition and Special Graphs
11(3)
Exercises
14(5)
1.2 Paths, Cycles, and Trails
19(15)
Connection in Graphs
20(4)
Bipartite Graphs
24(2)
Eulerian Circuits
26(5)
Exercises
31(3)
1.3 Vertex Degrees and Counting
34(19)
Counting and Bijections
35(3)
Extremal Problems
38(6)
Graphic Sequences
44(3)
Exercises
47(6)
1.4 Directed Graphs
53(14)
Definitions and Examples
53(5)
Vertex Degrees
58(2)
Eulerian Digraphs
60(1)
Orientations and Tournaments
61(2)
Exercises
63(4)
Chapter 2 Trees and Distance 67(40)
2.1 Basic Properties
67(14)
Properties of Trees
68(2)
Distance in Trees and Graphs
70(3)
Disjoint Spanning Trees (optional)
73(2)
Exercises
75(6)
2.2 Spanning Trees and Enumeration
81(14)
Enumeration of Trees
81(2)
Spanning Trees in Graphs
83(4)
Decomposition and Graceful Labelings
87(2)
Branchings and Eulerian Digraphs (optional)
89(3)
Exercises
92(3)
2.3 Optimization and Trees
95(12)
Minimum Spanning Tree
95(2)
Shortest Paths
97(3)
Trees in Computer Science (optional)
100(3)
Exercises
103(4)
Chapter 3 Matchings and Factors 107(42)
3.1 Matchings and Covers
107(16)
Maximum Matchings
108(2)
Hall's Matching Condition
110(2)
Min-Max Theorems
112(1)
Independent Sets and Covers
113(3)
Dominating Sets (optional)
116(2)
Exercises
118(5)
3.2 Algorithms and Applications
123(13)
Maximum Bipartite Matching
123(2)
Weighted Bipartite Matching
125(5)
Stable Matchings (optional)
130(2)
Faster Bipartite Matching (optional)
132(2)
Exercises
134(2)
3.3 Matchings in General Graphs
136(13)
Tutte's 1-factor Theorem
136(4)
f-factors of Graphs (optional)
140(2)
Edmonds' Blossom Algorithm (optional)
142(3)
Exercises
145(4)
Chapter 4 Connectivity and Paths 149(42)
4.1 Cuts and Connectivity
149(12)
Connectivity
149(3)
Edge-connectivity
152(3)
Blocks
155(3)
Exercises
158(3)
4.2 k-connected Graphs
161(15)
2-connected Graphs
161(3)
Connectivity of Digraphs
164(2)
k-connected and k-edge-connected Graphs
166(4)
Applications of Menger's Theorem
170(2)
Exercises
172(4)
4.3 Network Flow Problems
176(15)
Maximum Network Flow
176(5)
Integral Flows
181(3)
Supplies and Demands (optional)
184(4)
Exercises
188(3)
Chapter 5 Coloring of Graphs 191(42)
5.1 Vertex Colorings and Upper Bounds
191(13)
Definitions and Examples
191(3)
Upper Bounds
194(3)
Brooks' Theorem
197(2)
Exercises
199(5)
5.2 Structure of k-chromatic Graphs
204(15)
Graphs with Large Chromatic Number
205(2)
Extremal Problems and Turan's Theorem
207(3)
Color-Critical Graphs
210(2)
Forced Subdivisions
212(2)
Exercises
214(5)
5.3 Enumerative Aspects
219(14)
Counting Proper Colorings
219(5)
Chordal Graphs
224(2)
A Hint of Perfect Graphs
226(2)
Counting Acyclic Orientations (optional)
228(1)
Exercises
229(4)
Chapter 6 Planar Graphs 233(40)
6.1 Embeddings and Euler's Formula
233(13)
Drawings in the Plane
233(3)
Dual Graphs
236(5)
Euler's Formula
241(2)
Exercises
243(3)
6.2 Characterization of Planar Graphs
246(11)
Preparation for Kuratowski's Theorem
247(1)
Convex Embeddings
248(4)
Planarity Testing (optional)
252(3)
Exercises
255(2)
6.3 Parameters of Planarity
257(16)
Coloring of Planar Graphs
257(4)
Crossing Number
261(5)
Surfaces of Higher Genus (optional)
266(3)
Exercises
269(4)
Chapter 7 Edges and Cycles 273(46)
7.1 Line Graphs and Edge-coloring
273(13)
Edge-colorings
274(5)
Characterization of Line Graphs (optional)
279(3)
Exercises
282(4)
7.2 Hamiltonian Cycles
286(13)
Necessary Conditions
287(1)
Sufficient Conditions
288(5)
Cycles in Directed Graphs (optional)
293(1)
Exercises
294(5)
7.3 Planarity, Coloring, and Cycles
299(20)
Tait's Theorem
300(2)
Grinberg's Theorem
302(2)
Snarks (optional)
304(3)
Flows and Cycle Covers (optional)
307(7)
Exercises
314(5)
Chapter 8 Additional Topics (optional) 319(152)
8.1 Perfect Graphs
319(30)
The Perfect Graph Theorem
320(3)
Chordal Graphs Revisited
323(5)
Other Classes of Perfect Graphs
328(6)
Imperfect Graphs
334(6)
The Strong Perfect Graph Conjecture
340(4)
Exercises
344(5)
8.2 Matroids
349(29)
Hereditary Systems and Examples
349(5)
Properties of Matroids
354(4)
The Span Function
358(2)
The Dual of a Matroid
360(3)
Matroid Minors and Planar Graphs
363(3)
Matroid Intersection
366(3)
Matroid Union
369(3)
Exercises
372(6)
8.3 Ramsey Theory
378(18)
The Pigeonhole Principle Revisited
378(2)
Ramsey's Theorem
380(3)
Ramsey Numbers
383(3)
Graph Ramsey Theory
386(2)
Sperner's Lemma and Bandwidth
388(4)
Exercises
392(4)
8.4 More Extremal Problems
396(29)
Encodings of Graphs
397(7)
Branchings and Gossip
404(4)
List Coloring and Choosability
408(5)
Partitions Using Paths and Cycles
413(3)
Circumference
416(6)
Exercises
422(3)
8.5 Random Graphs
425(27)
Existence and Expectation
426(4)
Properties of Almost All Graphs
430(2)
Threshold Functions
432(4)
Evolution and Graph Parameters
436(3)
Connectivity, Cliques, and Coloring
439(3)
Martingales
442(6)
Exercises
448(4)
8.6 Eigenvalues of Graphs
452(19)
The Characteristic Polynomial
453(3)
Linear Algebra of Real Symmetric Matrices
456(2)
Eigenvalues and Graph Parameters
458(2)
Eigenvalues of Regular Graphs
460(3)
Eigenvalues and Expanders
463(1)
Strongly Regular Graphs
464(3)
Exercises
467(4)
Appendix A: Mathematical Background 471(22)
Sets
471(4)
Quantifiers and Proofs
475(4)
Induction and Recurrence
479(4)
Functions
483(2)
Counting and Binomial Coefficients
485(4)
Relations
489(2)
The Pigeonhole Principle
491(2)
Appendix B: Optimization and Complexity 493(14)
Intractability
493(3)
Heuristics and Bounds
496(3)
NP-Completeness Proofs
499(6)
Exercises
505(2)
Appendix C: Hints for Selected Exercises 507(8)
General Discussion
507(1)
Supplemental Specific Hints
508(7)
Appendix D: Glossary of Terms 515(18)
Appendix E: Supplemental Reading 533(34)
Appendix F: References 567(2)
Author Index 569(6)
Subject Index 575