内容

目次

INTRODUCTION TO GRAPH MODELSGraphs and DigraphsCommon Families of GraphsGraph Modeling ApplicationsWalks and DistancePaths, Cycles, and TreesVertex and Edge Attributes: More ApplicationsSTRUCTURE AND REPRESENTATIONSubgraphsSome Graphs OperationsGraph IsomorphismTests for Non-IsomorphismMatrix RepresentationsTREESCharacterizations and Properties of TreesRooted TreesBinary TreesCounting Binary Trees-The Catalan RecursionTraversing a Binary TreeBinary-Search TreesPriority TreesSPANNING TREESAn Intuitive Tree-Growing SchemeDepth-First and Breadth-First SearchApplications of Depth-First SearchCounting Spanning Trees: Prüfer EncodingMinimum Spanning Trees and Shortest PathsCycles, Edge Cuts, and Spanning TreesGraphs and Vector SpacesMatroids and the Greedy AlgorithmCONNECTIVITYVertex- and Edge-ConnectivityConstructing Reliable NetworksMax-Min Duality and Menger's TheoremsBlock DecompositionOPTIMAL GRAPH TRAVERSALSEulerian Trails and ToursDeBruijn Sequences and Postman ProblemsHamilton Paths and CyclesGray Codes and Traveling Salesman ProblemsGRAPH OPERATIONS AND MAPPINGSBinary Operations on GraphsLinear Graph MappingsModeling Network EmulationSubdivision and HomeomorphismTransforming a Graph by Edge ContractionDRAWING GRAPHS AND MAPSThe Topology of Graphs and of the SphereHigher-Order SurfacesDrawing ImbeddingsNumerical Relations for ImbeddingsRegular Sphere MapsPLANARITY OF GRAPHSPlanarity and NonplanarityExtending Planar DrawingsKuratowski's TheoremPlanarity AlgorithmGRAPH COLORINGSVertex-ColoringsMap-ColoringsEdge-ColoringsSPECIAL DIGRAPH MODELSBasic Properties and Some New TerminologySelected Applications of the General DigraphTournaments and Project SchedulingFinding the Strong Components of a DigraphNETWORK FLOWS AND MATCHINGFlows and Cuts in NetworksSolving the Maximum-Flow ProblemDetermining the Connectivity of a GraphMatchings, Transversals, and Vertex CoversGRAPHICAL ENUMERATIONAutomorphisms and SymmetryGraph Colorings and SymmetryCycle Index of a Permutation GroupBurnside's LemmaEnumerating Vertex- and Edge-ColoringsCounting Simple GraphsALGEBRAIC SPECIFICATION OF GRAPHSCyclic VoltagesCayley Graphs and Regular VoltagesPermutation VoltagesSymmetric Graphs and Parallel ArchitecturesInterconnection-Network PerformanceNON-PLANAR LAYOUTSCrossing Numbers and ThicknessImbeddings in General SurfacesRepresenting Imbeddings by RotationsGenus Distribution of a GraphVoltage-Graph Specification of Graph LayoutsNon-KVL Imbedded Voltage GraphsHeawood Map-Coloring ProblemAPPENDICESLogic FundamentalsRelations and FunctionsSome Basic CombinatoricsAlgebraic StructuresAlgorithmic ComplexitySupplementary ReadingBIBLIOGRAPHYINDICES Index of Applications Index of Algorithms Index of Notations General Index