Graph theory : a problem oriented approach / / Daniel A. Marcus

• Autore: Marcus Daniel A. <1945->
• Pubblicazione: Washington, D.C., : Mathematical Association of America, c2008
• Edizione: 1st ed.
• Descrizione fisica: 1 online resource (222 p.)
• Disciplina: 511.5
• Soggetto topico: Graph theory
• Note generali: Includes index.
• Nota di contenuto: ""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"" ; ""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""
• Sommario/riassunto: "Graph Theory presents a natural, reader-friendly way to learn some of the essential ideas of graph theory starting from first principles. The format is similar to the companion text, Combinatorics: A Problem Oriented Approach also by Daniel A. Marcus, in that it combines the features of a textbook with those of a problem workbook. The material is presented through a series of approximately 360 strategically placed problems with connecting text. This is supplemented by 280 additional problems that are intended to be used as homework assignments. Concepts of graph theory are introduced, developed, and reinforced by working through leading questions posed in the problems. This problem-oriented format is intended to promote active involvement by the reader while always providing clear direction. This approach figures prominently on the presentation of proofs, which become more frequent and elaborate as the book progresses. Arguments are arranged in digestible chunks and always appear along with concrete examples to keep the readers firmly grounded in their motivation. Spanning tree algorithms, Euler paths, Hamilton paths and cycles, planar graphs, independence and covering, connections and obstructions, and vertex and edge colorings make up the core of the book. Hall's Theorem, the Konig-Egervary Theorem, Dilworth's Theorem and the Hungarian algorithm to the optional assignment problem, matrices, and Latin squares are also explored."--Back cover.
• Titolo autorizzato: Graph theory
• ISBN: 0-88385-969-6
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9911136022103321
• Lo trovi qui: Univ. Federico II
• Serie: MAA Textbooks