Graph Theory Applications

ISBN-13: 9780387975993 / Angielski / Miękka / 1991 / 408 str.

L. R. Foulds

Opis

Over the last 30 years graph theory has evolved into an important math- ematical tool in the solution of a wide variety of problems in many areas of society. The purpose of this book is to present selected topics from this theory that have been found useful and to point out various applications. Some important theoretical topics have been omitted as they are not es- sential for the applications in Part II. Hence Part I should not be seen as a well-rounded treatise on the theory of graphs. Some effort has been made to present new applications that do not use merely the notation and ter- minology of graphs but do actually implement some mathematical results from graph theory. It has been written for final undergraduate year or first year graduate students in engineering, mathematics, computer science, and operations research, as well as researchers and practitioners with an inter- est in graph theoretic modelling. Suggested plans for the reading of the book by people with these interests are given later. The book comprises two parts. The first is a brief introduction to the mathematical theory of graphs. The second is a discussion on the applications of this material to some areas in the subjects previously mentioned. It is, of course, possi- ble to read only the first part to attempt to gain an appreciation of the mathematical aspects of graph theory. However even the purest of mathe- maticians is strongly recommended to delve seriously into the second part.

Recenzje

L.R. Foulds

Graph Theory Applications

"This book put[s] together the theory and applications of graphs in a single, self-contained, and easily readable volume . . . the fundamentals of graph theory are presented in a very accessible way . . . Each part is divided into chapters, each concluding with a summary and a nice collection of exercises . . . The book can serve as an excellent textbook for a course in graph theory either at the undergraduate or graduate level. It can also be used by researchers in application areas who use graph theory in their research or by pure graph theorists who want to know about the applications of their research."-ZENTRALBLATT MATH

Spis treści

I: The Theory of Graphs.- 1: Basic Ideas.- History.- Initial Concepts.- Summary.- Exercises.- 2: Connectivity.- Elementary Results.- Structure Based on Connectivity.- Summary.- Exercises.- 3: Trees.- Characterizations.- Theorems on Trees.- Tree Distances.- Binary Trees.- Tree Enumeration.- Spanning Trees.- Fundamental Cycles.- Summary.- Exercises.- 4: Traversability.- Eulerian Graphs.- Hamiltonian Graphs.- Summary.- Exercises.- 5: Planarity.- The Utilities Problem.- Plane and Planar Graphs.- Planar Graph Representation.- Planarity Detection.- Duality.- Thickness and Crossing Numbers.- Summary.- Exercises.- 6: Matrices.- The Adjacency Matrix.- The Incidence Matrix.- The Cycle Matrix.- The Cut-Set Matrix.- The Path Matrix.- Summary.- Exercises.- 7: Digraphs.- Connectivity.- Traversability.- Directed Trees.- More Digraph Matrices.- The Principle of Directional Duality.- Tournaments.- Summary.- Exercises.- 8: Coverings and Colourings.- Covering, Independence, and Domination.- Colouring.- Matching.- Summary.- Exercises.- 9: Algorithms.- Algorithms.- Input.- Complexity.- Output.- Graph Analysis Algorithms.- Graph Optimization Algorithms.- Summary.- Exercises.- 10: Matroids.- Duality.- The Greedy Algorithm.- Summary.- Exercises.- II: Applications.- 11: Miscellaneous Applications.- Social Sciences.- Economics.- Geography.- Architecture.- Puzzles and Games.- Summary.- Exercises.- 12: Operations Research.- Operations Research and Graph Theory.- Graph Theoretic Algorithms in OR.- Graph Theoretic Heuristics in OR.- Digraphs in OR.- Optimization Algorithms.- Transportation Networks: Advanced Models.- Summary.- Exercises.- 13: Electrical Engineering.- Electrical Network Analysis.- Printed Circuit Design.- Summary.- Exercises.- 14: Industrial Engineering.- Production Planning and Control.- Facilities Layout.- Summary.- Exercises.- 15: Science.- Physics.- Chemistry.- Biology.- Summary.- Exercises.- 16: Civil Engineering.- Earthwork projects.- Traffic Network Design.- Summary.- Exercises.- Further Reading.