Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010179351 | QA166 M37 2008 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
Combining the features of a textbook with those of a problem workbook, this text for mathematics, computer science and engineering students presents a natural, friendly way to learn some of the essential ideas of graph theory. The material is explained using 360 strategically placed problems with connecting text, which is then supplemented by 280 additional homework problems. This problem-oriented format encourages active involvement by the reader while always giving clear direction. This approach is especially valuable with the presentation of proofs, which become more frequent and elaborate as the book progresses. Arguments are arranged in digestible chunks and always appear together with concrete examples to help remind the reader of the bigger picture. Topics include spanning tree algorithms, Euler paths, Hamilton paths and cycles, independence and covering, connections and obstructions, and vertex and edge colourings.
Reviews 1
Choice Review
A graph, in this context, is a collection of points and a collection of links between some of these points. Many students are introduced to graphs in their discrete math courses. This book takes off from there and goes much further. Instead of the definition/theorem/proof format, it takes a problem-oriented approach. Marcus (formerly, California State Polytechnic Univ.) gives some examples and then by a series of questions drives the reader to a conjecture and an appropriate definition. Next, with more examples, the reader must revise the conjecture and finally try to prove it. In surprisingly few pages, this approach leads to many of the standard results in graph theory. This work could be the basis for a very nice one-semester "transition" course in which students evolve from users of theorems to creators of proofs. With their intuitive appeal and pictorial representations, graphs may be a better basis than analysis and limits for such a transition. Computer science students may find this book less helpful because it concentrates on theorems rather than applications/algorithms. The book's tone makes for easy reading and enjoyable self-study. Unfortunately, only some of the problems have answers. In particular, the last two chapters on network flows have no solutions. Summing Up: Highly recommended. All undergraduate math collections. P. Cull Oregon State University
Table of Contents
Preface |
A Basic Concepts |
B Isomorphic graphs |
C Bipartite graphs |
D Trees and forests |
E Spanning tree algorithms |
F Euler paths |
G Hamilton paths and cycles |
H Planar graphs |
I Independence and covering |
J Connections and obstructions |
K Vertex coloring |
L Edge coloring |
M Matching theory for bipartite graphs |
N Applications of matching theory |
O Cycle-Free digraphs |
Answers to selected problems |