This textbook covers a diversity of topics in graph and network theory,
both from a theoretical standpoint, and from an applied modelling point
of view. Mathematica(R) is used to demonstrate much of the modelling
aspects. Graph theory and model building tools are developed in tandem
with effective techniques for solving practical problems via computer
implementation. The book is designed with three primary readerships in
mind. Individual syllabi or suggested sequences for study are provided
for each of three student audiences: mathematics, applied
mathematics/operations research, and computer science. In addition to
the visual appeal of each page, the text contains an abundance of gems.
Most chapters open with real-life problem descriptions which serve as
motivation for the theoretical development of the subject matter. Each
chapter concludes with three different sets of exercises. The first set
of exercises are standard and geared toward the more mathematically
inclined reader. Many of these are routine exercises, designed to test
understanding of the material in the text, but some are more
challenging. The second set of exercises is earmarked for the computer
technologically savvy reader and offer computer exercises using
Mathematica. The final set consists of larger projects aimed at
equipping those readers with backgrounds in the applied sciences to
apply the necessary skills learned in the chapter in the context of
real-world problem solving. Additionally, each chapter offers
biographical notes as well as pictures of graph theorists and
mathematicians who have contributed significantly to the development of
the results documented in the chapter. These notes are meant to bring
the topics covered to life, allowing the reader to associate faces with
some of the important discoveries and results presented. In total,
approximately 100 biographical notes are presented throughout the book.
The material in this book has been organized into three distinct parts,
each with a different focus. The first part is devoted to topics in
network optimization, with a focus on basic notions in algorithmic
complexity and the computation of optimal paths, shortest spanning
trees, maximum flows and minimum-cost flows in networks, as well as the
solution of network location problems. The second part is devoted to a
variety of classical problems in graph theory, including problems
related to matchings, edge and vertex traversal, connectivity,
planarity, edge and vertex coloring, and orientations of graphs.
Finally, the focus in the third part is on modern areas of study in
graph theory, covering graph domination, Ramsey theory, extremal graph
theory, graph enumeration, and application of the probabilistic method.
