## Graph Theory ApplicationsOver 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. |

### What people are saying - Write a review

User Review - Flag as inappropriate

ss

### Contents

BASIC IDEAS | 3 |

CONNECTIVITY | 17 |

TREES | 27 |

TRAVERSABILITY | 43 |

PLANARITY | 53 |

MATRICES | 75 |

DIGRAPHS | 93 |

COVERINGS AND COLOURINGS | 123 |

Applications | 193 |

OPERATIONS RESEARCH | 225 |

ELECTRICAL ENGINEERING | 269 |

INDUSTRIAL ENGINEERING | 291 |

SCIENCE | 323 |

CIVIL ENGINEERING | 343 |

Further Reading | 361 |

379 | |

### Other editions - View all

### Common terms and phrases

adjacency matrix adjacent algorithm analysis applications of graph arc vi,Vj assumed branch and bound calculate chapter chords colour complete component concept connected graph construction contains corresponding cost defined Definition deltahedron denoted digraph edges of G electrical network entries Euler trail Eulerian exactly example excess capacity exists Foulds fundamental cut-set fundamental cycles given graph graph G graph in Figure graph theoretic graph theoretic model greedy algorithm Hamiltonian heuristic identified incidence matrix incident independent set inserted isomorphic labelled layout least matching matroid maximally planar maximum parsimony method minimal spanning tree minimum number multigraph node NP-hard number of crossings number of edges number of vertices optimal solution orientation pairs of facilities partition permutation phylogenies planar graph polynomial possible problem Proof pseudograph puzzle relationships representing sequence shortest path shown in Figure solve spanning tree species subset termed Theorem theory tournament triangle vertex weighted graph

### Popular passages

Page 369 - Eades, P., Foulds, LR, and Giffin, J. (1982), "An efficient heuristic for identifying a maximum weight planar subgraph", in: Lecture Notes in Mathematics No.