Graph Theory
An Introduction to Proofs, Algorithms, and Applications
1st Edition
Published on 16. March 2021
437 pages
978-0-429-77988-6 (ISBN)
Description
Graph Theory: An Introduction to Proofs, Algorithms, and Applications
Graph theory is the study of interactions, conflicts, and connections. The relationship between collections of discrete objects can inform us about the overall network in which they reside, and graph theory can provide an avenue for analysis.
This text, for the first undergraduate course, will explore major topics in graph theory from both a theoretical and applied viewpoint. Topics will progress from understanding basic terminology, to addressing computational questions, and finally ending with broad theoretical results. Examples and exercises will guide the reader through this progression, with particular care in strengthening proof techniques and written mathematical explanations.
Current applications and exploratory exercises are provided to further the reader's mathematical reasoning and understanding of the relevance of graph theory to the modern world.
Features
The first chapter introduces graph terminology, mathematical modeling using graphs, and a review of proof techniques featured throughout the book
The second chapter investigates three major route problems: eulerian circuits, hamiltonian cycles, and shortest paths.
The third chapter focuses entirely on trees - terminology, applications, and theory.
Four additional chapters focus around a major graph concept: connectivity, matching, coloring, and planarity. Each chapter brings in a modern application or approach.
Hints and Solutions to selected exercises provided at the back of the book.
Author
Karin R. Saoub is an Associate Professor of Mathematics at Roanoke College in Salem, Virginia. She earned her PhD in mathematics from Arizona State University and BA from Wellesley College. Her research focuses on graph coloring and on-line algorithms applied to tolerance graphs. She is also the author of A Tour Through Graph Theory, published by CRC Press.
Graph theory is the study of interactions, conflicts, and connections. The relationship between collections of discrete objects can inform us about the overall network in which they reside, and graph theory can provide an avenue for analysis.
This text, for the first undergraduate course, will explore major topics in graph theory from both a theoretical and applied viewpoint. Topics will progress from understanding basic terminology, to addressing computational questions, and finally ending with broad theoretical results. Examples and exercises will guide the reader through this progression, with particular care in strengthening proof techniques and written mathematical explanations.
Current applications and exploratory exercises are provided to further the reader's mathematical reasoning and understanding of the relevance of graph theory to the modern world.
Features
The first chapter introduces graph terminology, mathematical modeling using graphs, and a review of proof techniques featured throughout the book
The second chapter investigates three major route problems: eulerian circuits, hamiltonian cycles, and shortest paths.
The third chapter focuses entirely on trees - terminology, applications, and theory.
Four additional chapters focus around a major graph concept: connectivity, matching, coloring, and planarity. Each chapter brings in a modern application or approach.
Hints and Solutions to selected exercises provided at the back of the book.
Author
Karin R. Saoub is an Associate Professor of Mathematics at Roanoke College in Salem, Virginia. She earned her PhD in mathematics from Arizona State University and BA from Wellesley College. Her research focuses on graph coloring and on-line algorithms applied to tolerance graphs. She is also the author of A Tour Through Graph Theory, published by CRC Press.
Reviews / Votes
"This book is at a very nice level for an undergraduate course in graph theory. One of the really nice features are the inclusion of a quick introduction to proof techniques and the appendix which includes some other foundational knowledge students would need to complete some sections of the book. Including these prerequisite knowledge pieces in the book allows instructors to use this with minimal course prerequisites, which is a nice feature at small, undergraduate only institutions.I also appreciate that the author highlights different ways to use this book: basics, application based, more theoretical. This allows the book to be used for a variety of courses. I appreciate the historical examples that appear in later sections (Eulerian graphs and planarity to name a few). I also like the emphasis on computation and modeling as this is a direction a lot of undergraduate curriculums are moving. The pseudocode at the end of the book is also really nice for departments (like my own) that are a joint mathematics and computer science department. This appendix allows instructors to potentially teach this class with more of a computer science focus as well.
I appreciate that the book seems to build in difficulty. The first few chapters seem pretty straight forward and basic, with little focus on proofs.
I also like that it is small and not as hefty as some of the other classic Graph Theory texts (like Doug West's book). It feels much more manageable to cover big portions of this in one semester. This would also be a great book for student self-study as it's friendly enough for students to read. The prose and multiple examples make it an easy read.
There are a good amount of exercises at the end of each section with both computational and theoretical options."
- Alison Marr, Southwestern University
More details
Series
Edition
1. Auflage
Language
English
Place of publication
London
United Kingdom
Publishing group
Taylor & Francis Ltd
Target group
College/higher education
Illustrations
20 Tables, black and white; 521 Halftones, black and white; 521 Illustrations, black and white
ISBN-13
978-0-429-77988-6 (9780429779886)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Book
03/2021
1st Edition
CRC Press
€133.80
Shipment within 10-20 days
Book
03/2021
1st Edition
Chapman & Hall/CRC
€75.50
Shipment within 15-20 days
Person
Dr. Karin R. Saoub is an Associate Professor of Mathematics at Roanoke College in Salem, Virginia. She received her PhD in Mathematics from Arizona State University and a Bachelor of Arts degree from Wellesley College. Her research focuses on graph coloring and on-line algorithms applied to tolerance graphs. She is also the author of A Tour Through Graph Theory, published by CRC Press.
Content
Chapter 1: Graph Models, Terminology, and Proofs
Chapter 2: Graph Routes
Chapter 3: Trees
Chapter 4: Connectivity and Flow
Chapter 5: Matching and Factors
Chapter 6: Graph Coloring
Chapter 7: Planarity
Appendix
Selected Hints and Solutions
Chapter 2: Graph Routes
Chapter 3: Trees
Chapter 4: Connectivity and Flow
Chapter 5: Matching and Factors
Chapter 6: Graph Coloring
Chapter 7: Planarity
Appendix
Selected Hints and Solutions
