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

loopnetworks

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

uv walk

uv trail

uv 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(18051865) 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.
Leave a Reply