A Tour through Graph Theory

Reviews / Votes

Graph theory has become a stand-alone subject long back due to its immense potential for solving real life problems with not much di?culty. This one aspect has attracted bright minds throughout the globe to pursue this subject vigorously. Saoub Karin is one such excellent mathematician with priceless writing skills, she decided to share her passion for the subject and she has come forward to throw her hat in the pool of graph theory textbooks. Her approach however is quite different from others in the sense that she wants to make her text book readable not only for sophomores but also for other non-mathematics major students. This book has enough material to be taught for one full semester even though not much weight is given for the rigorous proof of several wonderful results.

The organization of the text book is planned as tours within a graph (Chapters 1 to 3), structure within a graph (Chapters 4 to 6) and a few other topics (Chapter 7) for better and deep understanding of the concepts touched in the first two divisions.

In Chapter 1, that deals with Eulerian tours, basic concepts, definitions and standard results statements are covered with adequate examples from real life situations. Then standard algorithms like Fleury's, Hierholzer's are discussed with illustrations. The chapter ends with discussion on the Chinese postman problem and a number of problems exercise section that are numerical rather than theoretical in nature. A few project tasks are also given.

In Chapter 2, the author takes us along the study of Hamiltonian cycles. Notable inclusions are a brute force algorithm for the travelling salesman problem, both nearest and repetitive nearest neighbor algorithms, cheapest link algorithm, nearest insertion algorithm, asymmetric travelling salesman algorithm and undirecting algorithm. A number of interesting problems are available in exercise section.

In Chapter 3, paths are introduced and it starts with Dijkstra's algorithm for both undirected and directed graphs and sails through project scheduling and critical path algorithm and ends with adequate exercise problems.

In Chapter 4, trees and networks are introduced with explanation about Kruskal's algorithm, Prim's algorithm, Toricelli's construction, Steiner trees, and mTSP algorithm, along with the exercise section, Boruvka's algorithm is outlined in the projects section.

In Chapter 5, matching is covered while probing bipartite graphs, augmenting path algorithm, vertex cover method, Gale-Shapley algorithm for stable matching, matchings in non-bipartite graphs are some interesting topics covered with visual illustrations along with the exercise section and the projects section. A brief discussion on Christo des' algorithm is also found there.

In Chapter 6, graph coloring is given by starting with the four color problem, then coloring strategies, equitable coloring, online coloring, first-fit coloring algorithm are explained with examples. A brief study on perfect graphs, interval graphs, tolerance graphs and weighted coloring are made with simple examples. The chapter as usual ends with the exercise section and the project section.

In Chapter 7, the author provides us with a valuable exposure to additional topics such as complexity of algorithms, graph isomorphism, tournaments, ow and capacity, rooted trees, BFS tree, planarity, edge coloring and Ramsey number. All these topics are covered from non-mathematics major students' point of view, with simple but powerful visual representation.

At the end, solutions for selected exercise problems are given with brief hints. To conclude, the book really provides a wonderful learning experience. A positive aspect of this book is that most of the topics can be self learnt without teacher assistance.

V. Yegnanarayanan (Chennai)