Prentice Hall, 1974. - 480 pages.
The last two decades have witnessed an upsurge of interest and activity in graph theory, particularly among applied mathematicians and engineers. Clear evidence of this is to be found in an unprecedented growth in the number of papers and books being published in the field. In 1957 there was exactly one book on the subject (namely, Konig's Theorie der Endlichen und Unendlichen Graphen). Now, sixteen years later, there are over two dozen textbooks on graph theory, and almost an equal number of proceedings of various seminars and conferences.
Each book has its own strength and points of emphasis, depending on the axe (or the pen) the author has to grind. I have emphasized the computational and algorithmic aspects of graphs. This emphasis arises from the experience and conviction that whenever graph theory is applied to solving any practical problem (be it in electrical network analysis, in circuit layout, in data structures, in operations research, or in social sciences), it almost always leads to large graphs—graphs that are virtually impossible to analyze without the aid of the computer. An engineer often finds that those real-life problems that can be modeled into graphs small enough to be worked on by hand are also small enough to be solved by means other than graph theory. (In this respect graph theory is different from college algebra, elementary calculus, or complex variables. ) In fact, the high-speed digital computer is one of the reasons for the recent growth of interest in graph theory.
Convinced that a student of applied graph theory must lea to enlist the help of a digital computer for handling large graphs, I have emphasized algorithms and their efficiencies. In proving theorems, constructive proofs have been given preference over nonconstructive existence proofs. Chapter 11, the largest in the book, is devoted entirely to computational aspects of graph theory, including graph-theoretic algorithms and samples of several tested computer programs for solving problems on graphs.
The last two decades have witnessed an upsurge of interest and activity in graph theory, particularly among applied mathematicians and engineers. Clear evidence of this is to be found in an unprecedented growth in the number of papers and books being published in the field. In 1957 there was exactly one book on the subject (namely, Konig's Theorie der Endlichen und Unendlichen Graphen). Now, sixteen years later, there are over two dozen textbooks on graph theory, and almost an equal number of proceedings of various seminars and conferences.
Each book has its own strength and points of emphasis, depending on the axe (or the pen) the author has to grind. I have emphasized the computational and algorithmic aspects of graphs. This emphasis arises from the experience and conviction that whenever graph theory is applied to solving any practical problem (be it in electrical network analysis, in circuit layout, in data structures, in operations research, or in social sciences), it almost always leads to large graphs—graphs that are virtually impossible to analyze without the aid of the computer. An engineer often finds that those real-life problems that can be modeled into graphs small enough to be worked on by hand are also small enough to be solved by means other than graph theory. (In this respect graph theory is different from college algebra, elementary calculus, or complex variables. ) In fact, the high-speed digital computer is one of the reasons for the recent growth of interest in graph theory.
Convinced that a student of applied graph theory must lea to enlist the help of a digital computer for handling large graphs, I have emphasized algorithms and their efficiencies. In proving theorems, constructive proofs have been given preference over nonconstructive existence proofs. Chapter 11, the largest in the book, is devoted entirely to computational aspects of graph theory, including graph-theoretic algorithms and samples of several tested computer programs for solving problems on graphs.