A Tour through Graph Theory

Karin R Saoub

• Publisher: Chapman and Hall/CRC
• Year: 2017
• ISBN:
  9781351642958
• Edition: 1
• Topic: Mathematik
• Subtopic: Zählen & Numerieren

A Tour Through Graph Theory introduces graph theory to students who are not mathematics majors. Rather than featuring formal mathematical proofs, the book focuses on explanations and logical reasoning. It also includes thoughtful discussions of historical problems and modern questions. The book inspires readers to learn by working through examples, drawing graphs and exploring concepts.

This book distinguishes itself from others covering the same topic. It strikes a balance of focusing on accessible problems for non-mathematical students while providing enough material for a semester-long course.

• Employs graph theory to teach mathematical reasoning

• 
  
  

• Expressly written for non-mathematical students

• 
  
  

• Promotes critical thinking and problem solving

• 
  
  

• Provides rich examples and clear explanations without using proofs

• 
  
  

Contents

Preface

1 Eulerian Tours

1.1 Königsberg Bridge Problem

1.2 Introduction to Graph Models

1.3 Touring a Graph

1.4 Eulerian Circuit Algorithms

Fleury’s Algorithm

Hierholzer’s Algorithm

1.5 Eulerization

Chinese Postman Problem

1.6 Exercises

2 Hamiltonian Cycles

2.1 Conditions for Existence

2.2 Traveling Salesman Problem

Brute Force

Nearest Neighbor

Cheapest Link

Nearest Insertion

2.3 Digraphs

Asymmetric Traveling Salesman Problem

2.4 Exercises

3 Paths

3.1 Shortest Paths

Dijkstra’s Algorithm

Chinese Postman Problem Revisited

3.2 Project Scheduling

Critical Paths

3.3 Exercises

4 Trees and Networks

4.1 Trees

4.2 Spanning Trees

Kruskal’s Algorithm

Prim’s Algorithm

4.3 Shortest Networks

Steiner Trees

4.4 Traveling Salesman Problem Revisited

4.5 Exercises

5 Matching

5.1 Bipartite Graphs

5.2 Matching Terminology and Strategies

Augmenting Paths and Vertex Covers

5.3 Stable Marriages

Unacceptable Partners

5.4 Matchings in Non-Bipartite Graphs

Stable Roommates

5.5 Exercises

6 Graph Coloring

6.1 Four Color Theorem

6.2 Coloring Bounds

6.3 Coloring Strategies

General Strategies

On-line Coloring

6.4 Perfect Graphs

Interval Graphs

Tolerance Graphs

6.5 Weighted Coloring

6.6 Exercises

7 Additional Topics

7.1 Algorithm Complexity

Exercises

7.2 Graph Isomorphism

Exercises

7.3 Tournaments

Exercises

7.4 Flow and Capacity

Exercises

7.5 Rooted Trees

Depth-First Search Tree

Breadth-First Search Tree

Exercises

7.6 Planarity

Exercises

7.7 Edge-Coloring

Ramsey Numbers

Exercises

Appendix

Creating a Triangle

Finding Angle Measure

Finding the Fermat Point

Other Items

Exercises

Selected Answers and Solutions

Bibliography

Image Credits

Index

Preface

Graph theory has been my passion since senior year of college. I was hooked after just one week of my first course in graph theory. I completely changed my plans post-graduation, choosing to apply to graduate schools and study more mathematics. I found the interplay between rigorous proofs and simple drawings both appealing and a nice break from my more computationally heavy courses. Since becoming a teacher I have found a new appreciation for graph theory, as a concept that can challenge students’ notions as to what mathematics is and can be.

You might wonder why I chose to write this book, as there are numerous texts devoted to the study of graph theory. Most books either focus on the theory and the exploration of proof techniques, or contain a chapter or two on the algorithmic aspect of a few topics from graph theory. This book is intended to strike a balance between the two — focus on the accessible problems for college students not majoring in mathematics, while also providing enough material for a semester long course.

The goal for this textbook is to use graph theory as the vehicle for a one-semester liberal arts course focusing on mathematical reasoning. Explanations and logical reasoning for solutions, but no formal mathematical proofs, are provided. There are discussions of both historical problems and modern questions, with each chapter ending in a section detailing some more in-depth problems. The final chapter also provides more rigorous graph theory and additional topics that I personally find interesting but for which there is not enough material to warrant an entire chapter. Each chapter will include problems to test understanding of the material and can be used for homework or quiz problems. In addition, project ideas and items requ...