Free E-books

In recent years, graph theory has established itself as an important mathematical tool in a wide variety of subjects, ranging from operational research and chemistry to genetics and linguistics, and from electrical engineering and geography to sociology and architecture. At the same time it has also emerged as a worthwhile mathematical discipline in its own right. In view of this, there is a need for an inexpensive introductory text on the subject, suitable both for mathematicians taking courses in graph theory and also for nonspecialists wishing to learn the subject as quickly as possible.

It is my hope that this book goes some way towards filling this need. The only prerequisites to reading it are a basic knowledge of elementary set theory and matrix theory, although a further knowledge of abstract algebra is needed for more difficult exercises. The contents of this book may be conveniently divided into four parts. The first of these (Chapters 1-4) provides a basic foundation course, containing definitions and examples of graphs, connectedness, Eulerian and Hamiltonian paths and cycles, and trees.

This is followed by two chapters (Chapters 5 and 6) on planarity and colouring, with special reference to the four-colour theorem. The third part (Chapters 7 and 8) deals with the theory of directed graphs and with transversal theory, with applications to critical path analysis, Markov chains and network flows. The book ends with a chapter on matroids (Chapter 9), which ties together material from the previous chapters and introduces some recent developments.

Before there were computers, there were algorithms. But now that there are computers,there are even more algorithms, and algorithms lie at the heart of computing. This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor. Each chapter presents an algorithm, a design technique, an application area, or a related topic.

Algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The book contains 244 figures—many with multiple parts—illustrating how the algorithms work. Since we emphasize efficiency as a design criterion, we include careful analyses of the running times of all our algorithms. e text is intended primarily for use in undergraduate or graduate courses in Algorithms or data structures.

Because it discusses engineering issues in algorithm design, as well as mathematical aspects, it is equally well suited for self-study by technical professionals. In this, the third edition, we have once again updated the entire book. The changes cover a broad spectrum, including new chapters, revised pseudocode, and a more active writing style.