文档介绍：Jørgen Bang-Jensen, Gregory Gutin
Digraphs
Theory, Algorithms and
Applications
15th August 2007
Springer-Verlag
Berlin Heidelberg NewYork
London Paris Tokyo
Hong Kong Barcelona
Budapest
We dedicate this book to our parents, especially to our fathers, Børge
Bang-Jensen and the late Mikhail Gutin, who, through their very broad
knowledge, stimulated our interest in science enormously.
Preface
Graph theory is a very popular area of discrete mathematics with not only
numerous theoretical developments, but also countless applications to prac-
tical problems. As a research area, graph theory is still relatively young, but
it is maturing rapidly with many deep results having been discovered over
the last couple of decades.
The theory of graphs can be roughly partitioned into two branches: the
areas of undirected graphs and directed graphs (digraphs). Even though both
areas have numerous important applications, for various reasons, undirected
graphs have been studied much more extensively than directed graphs. One
of the reasons is that undirected graphs form in a sense a special class of
directed graphs (symmetric digraphs) and hence problems that can be for-
mulated for both directed and undirected graphs are often easier for the
latter. Another reason is that, unlike for the case of undirected graphs, for
which there are several important books covering both classical and recent
results, no previous book covers more than a small fraction of the results
obtained on digraphs within the last 25 years. Typically, digraphs are consid-
ered only in one chapter or by a few elementary results scattered throughout
the book.
Despite all this, the theory of directed graphs has developed enormously
within the last three decades. There is an extensive literature on digraphs
(more than 3000 papers). Many of these papers contain, not only interesting
theoretical results, but also important algorithms as well as applications.
This clearly indicates