Applied Graph Theory: An Introduction With Graph Optimization And Algebraic Graph Theory - Hardcover

Griffin, Christopher H

Hardcover

ISBN 10: 9811273103 ISBN 13: 9789811273100

Publisher: WSPC, 2023

Synopsis

This book serves as an introduction to graph theory and its applications. It is intended for a senior undergraduate course in graph theory but is also appropriate for beginning graduate students in science or engineering. The book presents a rigorous (proof-based) introduction to graph theory while also discussing applications of the results for solving real-world problems of interest. The book is divided into four parts. Part 1 covers the combinatorial aspects of graph theory including a discussion of common vocabulary, a discussion of vertex and edge cuts, Eulerian tours, Hamiltonian paths and a characterization of trees. This leads to Part 2, which discusses common combinatorial optimization problems. Spanning trees, shortest path problems and matroids are all discussed, as are maximum flow problems. Part 2 ends with a discussion of graph coloring and a proof of the NP-completeness of the coloring problem. Part 3 introduces the reader to algebraic graph theory, and focuses on Markov chains, centrality computation (e.g., eigenvector centrality and page rank), as well as spectral graph clustering and the graph Laplacian. Part 4 contains additional material on linear programming, which is used to provide an alternative analysis of the maximum flow problem. Two appendices containing prerequisite material on linear algebra and probability theory are also provided.

About this title

About the Author

Dr Christopher Griffin is a Research Professor at the Applied Research Laboratory (ARL) at Penn State. He was a Eugene Wigner Fellow in the Computational Science and Engineering Division of the Oak Ridge National Laboratory, and has taught in the Mathematics Departments of the United States Naval Academy and the Pennsylvania State University. He holds a courtesy appointment in the Harold and Inge Marcus Dept. of Industrial and Manufacturing Engineering and the Dept. of Mathematics at Penn State, where he is also a member of the Operations Research Graduate Faculty. Dr Griffin's research interests are in applied dynamical systems, game theory and optimization. His research has been funded by the National Science Foundation, the Office of Naval Research, the Army Research Office, the Intelligence Advanced Research Projects Agency, the Defense Advanced Research Projects Agency, the Minerva Program, and other elements of the US Government. He has published over 100 peer reviewed research papers in game theory, applied optimization and applied dynamical systems.

Edition details

• Publisher: WSPC
• Publication date: 2023
• Language: English
• ISBN 10: 9811273103
• ISBN 13: 9789811273100
• Binding: Hardcover
• Number of pages: 304