Graph Theory : A Problem Oriented Approach.

Cover -- Title page -- Preface -- Contents -- Introduction -- Path Problems -- Coloring Problems -- Isomorphic Graphs -- Planar Graphs -- Disjoint Paths -- Shortest Paths -- ... and More -- A Basic Concepts -- Equivalent Graphs -- Multigraphs -- Directed Graphs and Mixed Graphs -- Complete Graphs -- Cycle Graphs -- Paths in a Graph -- Open and Closed Paths -- Cycles -- Subgraphs -- The Complement of a Graph -- Degrees of Vertices -- The Degree Sequence of a Graph -- Regular Graphs -- Connected and Disconnected Graphs -- Components of a Graph -- More Problems -- Matrices Associated with a Graph -- The Degree Sequence Algorithm -- B Isomorphic Graphs -- More Problems -- C Bipartite Graphs -- Complete Bipartite Graphs -- Bipartite Graphs and Matrices -- Cycles in a Bipartite Graph -- Cycle Theorem for Bipartite Graphs -- Proof of the Cycle Theorem -- More Problems -- D Trees and Forests -- Pruning a Tree -- Directed Trees -- Spanning Trees -- Counting Spanning Trees -- Codewords for Trees: Prufer's Method -- More Problems -- Three conditions -- Cycles and spanning trees -- E Spanning Tree Algorithms -- Constructing Spanning Trees -- Weighted Graphs -- Minimal Spanning Trees -- Prim's Algorithm -- Tables for Prim's Algorithm -- The Reduction Algorithm -- Spanning Trees and Shortest Paths -- Minimal Paths in a Weighted Graph -- Minimal Path Algorithm, first attempt -- Minimal Path Algorithm, revised -- Tables for Dijkstra's Algorithm -- Minimal Paths in a Directed Graph -- Negative Weights -- More Problems -- Justification of the reduction algorithm -- Justification of Prim's Algorithm -- Justification of Dijkstra's Algorithm -- Justification of Ford's Algorithm -- F Euler Paths -- The Königsberg Bridge Problem -- Euler Paths in Directed Graphs and Directed Multigraphs.

Application of Euler Paths: State diagrams, DeBruijn sequences, and rotating wheels -- More Problems -- G Hamilton Paths and Cycles -- Some Negative Tests -- Negative test for bipartite graphs -- Subgraph Test for Hamilton paths and cycles -- Positive Tests for Hamilton Cycles -- The Path/Cycle Principle -- Some Proofs -- Proof of the Path/Cycle Principle -- Proof of the Bondy-Chvatal Theorem -- Proof of Dirac's Theorem -- More Problems -- Proof of Posa's Theorem -- H Planar Graphs -- Regions Formed by a Plane Diagram -- Proof that K_5 is Non-Planar, Using Euler's Formula -- Non-Planar Graphs and Kuratowski's Theorem -- More Problems -- I Independence and Covering -- The Independence Numbers of a Graph -- A Graph Game -- Covering Sets and Covering Numbers -- More Problems -- J Connections and Obstructions -- Internally Disjoint Paths -- Edge-Disjoint Paths -- Path Connection Numbers -- Blocking Sets -- k-Connected Graphs -- Vertex Cut Sets and Vertex Cut Numbers -- The vertex cut number of a graph -- More Problems -- K Vertex Coloring -- The Vertex Coloring Number of a Graph -- Vertex Coloring Theorems -- Algorithm form of Vertex Coloring Theorem #3:The Upper Bound Algorithm for chi -- Why the algorithm works -- The Four Color Theorem -- Proof of the Six Color Theorem -- Proof of the Five Color Theorem -- Color switch -- Map Coloring -- More Problems -- Proof of the Four Color Theorem? -- Proof of Brooks' Theorem for regular graphs -- L Edge Coloring -- The Edge Coloring Number of a Graph -- Edge Coloring of Complete Graphs -- Edge Coloring of Bipartite Graphs -- Edge Color Switch -- Proof of Edge Coloring Theorem #3 -- Application of Edge Coloring: the Scheduling Problem -- More Problems -- Proof of Edge Coloring Theorem #2 -- M Matching Theory for Bipartite Graphs -- The Max/Min Principle -- Proof of the König-Egervary Theorem.

The Colored Digraph Construction -- Matching Extension Algorithm -- Proof of the Colored Digraph Theorem -- Matrix Interpretation of the König-Egervary Theorem -- Hall's Theorem and Its Consequences -- More Problems -- N Applications of Matching Theory -- Sets and Representatives -- Latin Squares -- Permutation Matrices -- The Optimal Assignment Problem -- More Problems -- O Cycle-Free Digraphs -- Chains and Antichains -- Chain Decompositions -- Proof of Dilworth's Theorem -- More Problems -- P Network Flow Theory -- Flows in a Network -- Path flows -- The value of a flow -- The matrix of a flow -- Capacities in a network -- Maximal flow algorithm (first attempt) -- The maximal flow algorithm -- Cuts and Capacities -- The minimal cut algorithm -- More Problems -- Q Flow Problems with Lower Bounds -- The Supply and Demand Problem -- Supply and Demand Theorem #1 -- Supply and Demand Theorem #2 (Gale's Feasibility Theorem) -- The lower capacity problem -- Maximizing the flow -- Maximal flow algorithm in networks with lower capacities -- More Problems -- Answers to Selected Problems -- Chapter A -- Chapter B -- Chapter C -- Chapter D -- Chapter E -- Chapter F -- Chapter G -- Chapter H -- Chapter I -- Chapter J -- Chapter K -- Chapter L -- Chapter M -- Chapter N -- Chapter O -- Index -- About the Author.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2024. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.