image image

The cover page of the book gives the solution to the popular puzzle,

Is it possible for a knight to tour the chessboard, visiting every square once and only once, and return to its initial square?

The solution to the puzzle lies in thinking about a graph containing vertices as squares of the chess board and the adjacency of two vertices based on the validity of a knight move. If you want to solve such a problem for a general n*n square, you need a graph processing algorithm.

Graphical models are considered as of the most important classes of models in applied mathematics. The first time I came across graphs in the context of statistics was in Larry Wasserman book, ”All of Statistics”. According to Wasserman,

The typical mathematical statistics course spends too much time on tedious and uninspiring topics (counting methods, two dimensional integrals, etc.) at the expense of covering modern concepts (bootstrapping, curve estimation, graphical models, etc.).

Wasserman devotes one full chapter on Directed Acyclic Graphs and its connections to statistical modeling. At the time I was reading Wasserman’s book , I was clueless and had deferred that chapter until I understood some basic principles of graph theory. It has been almost three years since I read Wasserman’s book and yet I could not find time to go over Graph theory. Sometimes I feel that there are so many things that I am ignorant of, that it will take my entire life to get a good understanding of modern statistics and build some meaningful models. In any case, I can only do one thing at a time and so I finally decided to understand this topic by going over a book that is targeted towards undergrads.

The first chapter of the book is on Mathematical models and gives a basic flavor of the modeling process. The chapter then goes on to define various terms relevant to graph theory such as

  • graph

  • edge set

  • edges

  • vertex set

  • vertices

  • order of graph

  • size of graph

  • adjacent vertices

  • incident to an edge or incident with an edge

  • directed graph / digraph

  • directed edge

  • symmetric digraphs

  • network

  • undirected network

  • directed network

  • signed graph

  • positive edge

  • negative edge

  • multigraph

  • multi edges

  • loop graph

  • loop digraphs

  • loop-networks

  • loop multigraphs

By going over the definitions and explanations carefully, a reader will have an understanding that Graph is a mathematical object that is characterized by edge set, vertex set and relation set on vertex set. Order and size of the graph capture the number of nodes and edges in a graph. Depending on the type of edges, the graphs can be directed or undirected.

The second chapter introduces the term “isomorphism” and gives examples of identifying isomorphic graphs. In fact “ is isomorphic” is an equivalence relation and can be used to partition the universe of graphs. The chapter then introduces the following terms with rich visuals :

  • degree of the vertex

  • graph of degree r / r regular graph

  • complete graph

  • isomorphic

  • isomorphism

  • subgraph

  • u-v walk

  • u-v trail

  • u-v path

  • connected graph

  • disconnected graph

  • circuit

  • cycle

  • cut vertex

  • bridge

The book then takes a novel approach for explaining various principles of graph theory. Instead of defining the terms, giving theorems and proofs, it gives a set of applications where graphs can be used as effective tools for problem solving. In the process, it explains all the relevant theorems and principles.

The book uses Konisberg 7 bridges problem and Traveling Salesman problem to explain the following terms

  • eulerian trail

  • eulerian circuit

  • eulerian graph

  • eulerian multigraph

  • traversable graph

  • hamiltonian graph

  • hamiltonian cycle

A reader will never confuse the meaning of the above terms once they are explained in terms of a problem. Eulerian / Traversable graph comes up in 7 bridges problem where it deals with traversing each edge once . A Hamiltonian graph is relevant to solving Traveling salesman problem where each vertex needs to be touched once. The chapter also states the conditions (sometimes necessary, sometimes sufficient) for a graph to be Eulerian / Hamiltonian. There is also some historical trivia mentioned  , for example

Hamiltonian graph got its name from the famous Irish mathematician Sir William Rowan Hamilton(1805-1865) who invented a game that involved a regular solid dodecahedron. Hamilton labeled each vertex with a name of a well known city and object of the game was to travel ``All around the world'' with traversing each city exactly once.

Using an example of building a rail network between a set of cities, the book introduces the terms like trees, forest, spanning trees, spanning forests and minimum spanning trees. Digraphs are introduced via PERT. There are a lot of algorithms in the CS literature that can be used to find the minimum spanning trees in a graph. I think this book gives enough motivation for an interested reader to look up various graph processing algorithms.

Using party puzzles the book introduces bipartite graphs and Ramsey numbers. In the process it also shows that graph theory development is far from over as there a quite a number of problems yet to be cracked.

The book also contains a chapter that is full of puzzles and the way they can be solved by looking for a graph structure. Towards the end of the book, the author talks about representing the graph as a incidence matrix. By looking at the graph from a matrix stand point, relations between edges, nodes etc. can be culled out from the four fundamental subspaces of the matrix. After reading through this book, I think I am little bit equipped to slog through application of DAGs in statistical modeling.