Computational
Discrete Mathematics: Combinatorics and
Graph Theory with Mathematica
by Sriram Pemmaraju,
Steven Skiena
Cambridge University Press, Cambridge
UK, 2003
494 pp., illus. 10 b/w. Trade, $60.00
ISBN: 0-521-80686-0.
Reviewed by Martha Patricia Niño
Mojica
Pontificia Universidad Javeriana de Bogotá
Facultad de Artes Visuales
Colombia
ninom@javeriana.edu.co
This book is the definitive reference
guide to Combinatorica——an
extension of the popular computer software,
Mathematica——with examples
of the 450 combinatorics functions. The
authors developed the newest version of
this software that has dramatic
improvements in graphical processing performance,
representation, visualization, and many
brand new functions. Steven Skiena has
used Mathematica before the package
was commercially released, and he had
been working with Combinatorica
for about 15 years. In 1990, he wrote
the first book in the subject. Sriram
Pemmaraju is Associate Professor of Computer
Science at The University of Iowa, his
main interests are combinatorics and graph
theory, combinatorial optimization, approximation
algorithms, and distributed algorithms.
Combinatorics is a branch of mathematics
that studies counting. It analyses the
possible combinations or permutations
among numbers, and it is often related
to statistics and probability. The first
part of the book——from chapter
one to four——has an introduction
to Combinatorica and deals with
permutations and combinations, algebraic
combinatorics, partitions, compositions,
and Young tableaux. The second part of
the book——from chapter five
to eight——is about graph theory,
a subfield of mathematics that studies
diagrams or graphs in order to determine
relations among objects. Graphs serve
as an interface between mathematics and
computer science. The main topics are
graph representation, generating graphs,
properties of graphs such as traversals,
connectivity, cycles in graphs, graph
coloring, cliques, vertex cover and independent
sets, algorithmic graph theory, shortest
paths, minimum spanning trees, network
flow, matching, partial orders, graph
isomorphism, and planar graphs. It exhibits
a wide variety of graphs, functions to
generate them, invariants, and embeddings.
It also shows the main classical problems
such as flow, matching, Eurelian walks,
Hamilitonian walks, vertex or edge coloring,
and stable-dominant sets.
These two text’s sections are independent
of each other, so it is possible to start
in any of them. The book is also a good
guide for writing your own programs with
Mathematica. It is more than just
a reference since it has all the necessary
theory to comprehend the concepts. It
does not have formal demonstrations but
well explained practical thought, programming,
and experimental exercises that provide
a good flexibility for teaching a full
semester class in this subject.
It is a very readable edition full of
graphical and stimulating approaches to
combinatorics and graph theories. The
text is all about discover the excitement
of mathematics. This is a great resource
for the acknowledgement of beautiful patterns
and important properties of graphs and
other combinatorial objects. You can visualize
these theories in order to identify iterations
and make inferences. Since graphs are
structures of points connected by lines,
it shows how to generate fascinating constructions
such as three dimensional butterfly graphs,
stars, tree, hypercubes, dodecahedral,
grids, and many other configurations.
It is possible to animate interesting
structures and transform these videos
to animated GIF files for web pages. Combinatorica
won the EDUCOM Higher Education Software
Award and it is the most far-reaching
software in the field of discrete mathematics.
Animated examples and other useful information
can be found at http://www.combinatorica.com/.
In regard to the application of applications
of this field, the possibilities are endless:
road networks, robot navigation, electronic
circuits, artificial intelligence, evolutionary
game theory, Internet mapping, social
interactions among individuals, and even
graphic design problems similar as the
ones posed by the works of M.C. Escher
in the field of combinatorial patterns
that can be produced in an algorithmic.
The book doesn’t cover specific Escher’s
examples, but it is possible to find them
online.
Curiosity is the main requisite for exploring
this topic. This book is highly recommended.
It is a well organized, and readable textbook
for beginners and intermediate students.
It is always advisable to have some mathematical
savvy to get the most out of this text.
You should not expect find all the aspects
of Discrete Mathematics covered since
the focus is in Combinatorics and Graph
theory. Although the programs are not
extremely long, it would be a good idea
to supplement the book with a code repository
of the practical exercises.