Graph Theory Applications

This text offers an upper undergraduate or first year graduate level introduction to the theory of graphs and its application in engineering and science. The first part covers the main graph theoretic topics: connectivity, trees, transversability, planarity, colouring, covering, matching, digraphs, networks, matrices of a graph, graph theoretic algorithms and matroids. In the second part, these concepts are applied to problems in engineering, operations research and science as well as to an interesting set of miscellaneous problems, illustrating the broad applicability of the subject. Some effort has been made to present applications that use not only the notation and terminology of graph theory but also the actual mathematical result of the subject. Some of the applications, such as molecular evolution, facilities layout and traffic network design have not appeared in book form before. The book is suitable for students of mathematics, engineering, operations research, computer science and physical science as well as researchers and practitioners with an interest in graph theoretic modelling.