| contents preface chapter 1 fundamental concepts 1.1 what is a graph? the definition, 1 graphs as models, 3 matrices and isomorphism, 6 . decomposition and special graphs, 11 exercises, 14 1.2 paths, cycles, and trails connection in graphs, 20 bipartite graphs, 24 eulerian circuits, 26 exercises, 31 1.3 vertex degrees and counting counting and bijections, 35 extremal problems, 38 graphic sequences, 44 exercises, 47 1.4 directed graphs .definitions and examples, 53 vertex degrees, 58 eulerian digraphs, 60 orientations and tournaments, 61 exercises, 63 chapter 2 trees and distance 2.1 basic properties properties of trees, 68 distance in trees and graphs, 70 disjoint spanning trees (optional), 73 exercises, 75 2.2 spanning trees and enumeration enumeration of trees, 81 spanning trees in graphs, 83 decomposition and graceful labelings, 87 branchings and eulerian digraphs (optional), 89 exercises, 92 2.3 optimization and trees minimum spanning tree, 95 shortest paths, 97 trees in computer science (optional), 100 exercises, 103 chapter 3 matchings and factors 3.1 matchings and covers maximum matchings, 108 hall's matching condition, 110 mm-max theorems, 112 independent sets and covers, 113 dominating sets (optional), 116 exercises, 118 3.2 algorithms and applications maximum bipartite matching, 123 weighted bipartite matching, 125 stable matchings (optional), 130 faster bipartite matching (optional), 132 exercises, 134 3.3 matchings in general graphs tutte's l-factor theorem, 136 f-factors of graphs (optional), 140 edmonds' blossom algorithm (optional), 142 exercises, 145 chapter 4 connectivity and paths 4.1 cuts and connectivity connectivity, 149 edge-connectivity, 152 blocks, 155 exercises, 158 4.2 k-connected graphs 2-connected graphs, 161 connectivity of digraphs, 164 k-connected and k-edge-connected graphs, 166 applications of menger's theorem, 170 exercises, 172 4.3 network flow problems maximum network flow, 176 integral flows 181 supplies and demands (optional), 184 exercises, 188 chapter 5 coloring of graphs 5.1 vertex colorings and upper bounds definitions and examples, 191 upper bounds, 194 brooks' theorem, 197 exercises, 199 5.2 structure of k-chromatic graphs graphs with large chromatic number, 205 extremal problems and turan's theorem 207 color-critical graphs, 210 forced subdivisions, 212 exercises, 214 5.3 enumerative aspects counting proper colorings, 219 chordal graphs, 224 a hint of perfect graphs, 226 counting acyclic orientations (optional), 228 exercises, 229 chapter 6 planar graphs 6.1 embeddings and euler's formula drawings in the plane, 233 dual graphs, 236 euler's formula, 241 255 exercises, 243 6.2 characterization of planar graphs preparation for kuratowski's theorem, 247 convex embeddings, 248 planarity testing (optional), 252 exercises, 255 6.3 parameters of planarity coloring of planar graphs, 257 crossing number, 261 surfaces of higher genus (optional), 266 exercises, 269 chapter 7 edges and cycles 7.1 line graphs and edge-coloring edge-colorings, 274 characterization of line graphs (optional), 279 exercises, 282 7.2 hamiltonian cycles necessary conditions, 287 sufficient conditions, 288 cycles in directed graphs (optional), 293 exercises, 294 7.3 planarity, coloring, and cycles tait's theorem, 300 grinberg's theorem, 302 snarks (optional), 304 flows and cycle covers (optional), 307 exercises, 314 chapter 8 additional topics (optional) 8.1 perfect graphs the perfect graph theorem, 320 chordal graphs revisited, 323 other classes of perfect graphs, 328 imperfect graphs, 334 the strong perfect graph conjecture, 340 exercises, 344 8.2 matroids hereditary systems and examples, 349 properties of matroids, 354 the span function, 358 the dual of a matroid, 360 matroid minors and planar graphs, 363 matroid intersection, 366 matroid union, 369 exercises, 372 8.3 pamsey theory, the pigeonhole principle revisited, 378 ramsey's theorem, 380 ramsey numbers, 383 'graph ramsey theory, 386 sperner's lemma and bandwidth, 388 exercises, 392 8.4 more extremal problems encodings of graphs, 397 branchings and gossip, 404 list coloring and choosability, 408 partitions using paths and cycles, 413 circumference, 416 exercises, 422 8.5 random graphs existence and expectation, 426 properties of almost all graphs, 430 threshold functions, 432 evolution and graph parameters, 436 connectivity, cliques, and coloring, 439 martingales, 442 exercises, 448 8.6 eigenvalues of graphs the characteristic polynomial, 453 linear algebra of real symmetric matrices, 456 eigenvalues and graph parameters, 458 eigenvalues of regular graphs, 460 eigenvalues and expanders, 463 strongly regular graphs, 464 exercises, 467 appendix a mathematical background sets, 471 quantifiers and proofs, 475 induction and recurrence, 479 functions, 483 counting and binomial coefficients, 485 relations, 489 the pigeonhole principle, 491 appendix b optimization and complexity intractability, 493 heuristics and bounds, 496 np-completeness proofs, 499 exercises, 505 appendix c hints for selected exercises general discussion, 507 supplemental specific hints, 508 appendix d glossary of terms appendix e supplemental reading appendix f references author index subject index |
内容加载中，请稍后...
商品评论（0条）