Introduction to Graph Theory

所需积分/C币:38 2018-07-20 12:43:37 62.65MB PDF

Introduction to Graph Theory Second Edition by D. West
The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs Copyright 2001 by Pearson Education, Inc This edition is published by arrangement with Pearson Education, Inc. All rights reserved. No part of this publication may be reproduced, stored in a database or retrieval system, or transmitted in any form or by aily means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. ISBN81-7808-830-4 First Indian Reprint, 2002 This edition is manufactured in india and is authorized for sale only in India, Bangladesh, Pakistan, Nepal, Sri lanka and the Maldives. Published by Pearson Education(Singapore)Pte. Ltd, Indian Braneh, 482 F I.E. Patparganj Delhi 110092. india Printed in India by rashtriya Printers For my dear wife Ching and for all lovers of graph theory 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 19 Connection in Graphs, 20 Bipartite Graphs, 24 Eulerian Circuits. 26 Exercises. 31 1.3 Vertex Degrees and: Counting 844 Counting and Bijections, 35 Extremal Problems. 38 Graphic Sequences, 44 Exercises. 47 1.4 Directed Graphs 53 Definitions and Examples, 53 Vertex Degrees, 58 Eulerian Digraphs, 60 Orientations and Tournaments, 61 Exercises, 63 Content Chapter 2 Trees and Distance 67 2.1 Basic Properties 67 Properties of Trees. 68 Distance in Trees and Graphs, 70 Disjoint Spanning Trees(optional), 78 Exercises. 75 2.2 Spanning Trees and Enumeration 81 Enumeration of Trees. 81 panning Trees in graphs, 83 Decomposition and graceful Labelings 87 Branchings and Eulerian Digraphs(optional), 89 Exercises. 92 2.3 Optimization and Trees 95 Minimum Spanning Tree, 95 Shortest Paths. 97 Trees in Computer Science(optional), 100 Exercises. 103 Chapter 3 Matchings and Factors 107 3.1 Matchings and covers 107 Maximum Matchings, 108 Min-Max Theorems, 112,I1 Halls Matching Condition, 110 Independent sets and Covers, 113 Dominating Sets(optional), 116 Exercises. 118 8.2 Algorithms and applications 128 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 186 ①utte’s1 factor Theoren,136 f-factors of Graphs(optional), 140 Edmonds' Blossom Algorithm(optional), 142 Exercises. 145 Contents Chapter 4 Connectivity and Paths 149 4.1 Cuts and Connectivity 149 Connectivity, 149 Edge-connectivity, 152 Blocks. 155 Exercises. 158 4.2 k-connected Graphs 161 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 176 Maximum Network Flow. 176 Integral Flows, 181 Supplies and Demands(optional),184 Exercises. 188 Chapter 5 Coloring of Graphs 191 5.1 Vertex Colorings and Upper bounds 191 Definitions and Examples, 191 Upper Bounds, 194 Brooks, Theorem. 197 Exercises. 199 5.2 Structure of k-chromatic Graphs 204 Graphs with Large Chromatic Number, 205 Extremal Problems and Turan's Theorem 207 Color-Critical Graphs, 210 Forced Subdivisions. 212 Exercises. 214 5.8 Enumerative Aspects 219 Counting Proper colorings, 219 Chordal Graphs, 224 A Hint of Perfect Graphs, 226 Counting Acyclic Orientations(optional), 228 Exercises. 229 C contents Chapter 6 Planar graphs 238 6.1 Embeddings and Eulers Formula 238 Drawings in the Plane, 233 Dual Graphs, 236 Eulers Formula. 241 255 Exercises. 243 6.2 Characterization of Planar Graphs 246 Preparation for Kuratowski's Theorem, 247 Convex Embeddings, 248 Planarity Testing(optional), 252 Exercises. 255 6. 3 Parameters of planarity 257 Coloring of Planar graphs, 257 Crossing Number, 261 Surfaces of Higher Genus(optional), 266 Exercises. 269 Chapter 7 Edges and Cycles 278 7.1 Line Graphs and Edge-coloring 278 Edge-colorings, 274 Characterization of Line Graphs(optional), 279 Exercises. 282 7.2 Hamiltonian Cycles 26 Necessary Conditions, 287 Sufficient Conditions. 288 Cycles in Directed Graphs(optional), 293 Exercises. 294 7. 3 Planarity, Coloring, and Cycles 299 Taits Theorem. 300 Grinberg's Theorem, 302 Snarks(optional), 304 Flows and Cycle Covers (optional), 307 Exercises. 314 Content Chapter 8 Additional Topics(optional) 319 8.1 Perfect Graphs 819 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, 3445 8. 2 Matroids 849 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 Ramsey Theory 878 The Pigeonhole Principle Revisited, 378 Ramseys Theorem, 380 Ramsey Numbers, 383 Graph Ramsey Theory, 386 Sperner,s Lemma and Bandwidth, 388 Exercises. 392 8. 4 More Extremal Problems 896 Encodings of Graphs, 397 Branchings and Gossip, 404 List Coloring and Choosability, 408 Partitions Using Paths and Cycles, 413 Circumference. 416 Exercises. 422 8.3 Random Graphs 495 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

...展开详情

评论 下载该资源后可以进行评论 1

塞涅斯·杨 研究需要哦~!
2019-04-05
回复
img
Shenc0411

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐