Plan: Introduction to Graph Theory, Defining Basic Terms , Representing Graphs , DFS , BFS

Homer Simpson is da bomb

Graph Theory is one topic which most of us probably would not have had as part of high school Mathematics. Leonhard Euler is regarded to have started this area of Discrete Mathematics in 1736 by describing The Konigsberg Bridge Problem. Since then it has found a lot of applications in Mathematics and Computer Science. In this tutorial we will see some of the basics of Graph Theory, mainly needed for Problem Solving. If you are already familiar with some of the topics, you can safely skip those parts, as its mainly intended for beginners. If you are a beginner, then its time to learn some fascinating stuff and solve very interesting problems. So, get ready .. take a book and a pen .. postpone your other works .. as you may get late, traversing through mazes - rescuing your friends, ride a knight, board a lot of flights and many more :)

 

---

Following the tradition of all the Graph Theory books, lets start with knowing what The Konigsberg Bridge Problem is.

The Konigsberg Bridge Problem

The city of Konigsberg occupied two islands plus the areas on both blanks. These regions were linked by seven bridges as shown in Fig 1

[Add Image of konigsberg : Fig 1 ]

Now the problem is to find if one could start from his/her home and walk around the city in a way that would involve crossing each bridge exactly once and return to home. The graph corresponding to this problem is on the right side in Fig 1 . Now that if each bridge has to be traversed exactly once, it follows that each part of land must have even number of bridges touching it ( also called the degree of the node, which we will see shortly ), one bridge to enter into land and other to leave from it . Clearly, all the land masses here have odd number of bridges touching them. So there doesn't exist such a walk.

 

The other famous theorem is the Four color theorem. If you happened to observe any map given in an Atlas carefully, you would have seen that the different states in a country are separated by borders and not only that, they are also colored with different colors, to distinguish between any two adjacent states (which share a common border segment) . Now the question is, how many colors do we need at max, to color the regions. Well, as the name of the theorem suggests, we need at max Four colors. This is in general true for any planar structure.

Now its time to know the formal definition of a Graph and many other basic terms related to Graphs, before we see other interesting problems :D.

 

---

There are a lot of terms associated with graphs and its properties. Fortunately, most of these terms are derived from the casual english words and common mathematical terms, most of which we know already. Lets take a quick look at some of the basic terms and define others as we move along.

Basic Terms used in Graph Theory

Graph: An abstract mathematical structure, to model pairwise relations between discrete objects. A graph G = ( V , E ) consists of a finite set V ( set of vertices or nodes ) and a set E (set of edges ) of 2-subsets of V. Each edge is a relation ( adjacency ) between two vertices. In general, the number of vertices is denoted by n and the number of edges is denoted by m. See the following graph and identify the set of vertices and edges.

[Add Image of a simple graph : Fig 2 ]

 

The degree of a vertex v is the number if edges which contain v i.e., the number of edges that are incident on v. Note: A loop contributes 2 to the degree of the vertex it is incident on. As each edge contributes 2 to the degree of its endpoints, the sum of all degrees of vertices equals twice the number of edges.

The different drawings of a graph, stretching, shrinking, rotating etc., will not change the properties of the graph. All those transformations represent the same graph and are said to be Isomorphic to eachother.

Multiple Edges are those edges that connect the same pair of distinct vertices. A loop is an edge which connects a vertex to itself. A graph without multiple edges and without loops is called a Simple Graph. Mostly we will deal with simple graphs only.

A Walk is a list of vertices and edges ( v₀ e₁ v₁ e₂ . . . . e_k v_k ), such that for 1<=i<=k, the edge e_i connects v_i-1 and v_i . A Trail is a walk with no repeated edge. A Simple Path is a walk with no repeated vertices (hence no repeated edges). A Cycle is a path in which no vertex is repeated, except the first and the last vertex, which are same. The lengthof any of these is equal to the number of edges in it.

 

Connected Components: Lets take an empty set V₁ and add a vertex u to it. Keep adding the vertices which are connected to u by some path, to the set. The maximal (no more vertices can be added) set V₁ is called a connected component. The vertex set V can be partitioned corresponsing to this equivalence relation 'is connected to'. For a graph G , V = V₁ U V₂ U V₃ ... U V_k has k connected components. If G has just one component, it is said to be a connected graph.

 

If in a graph, each edge has a sense of direction associated with it, it is called a Directed Graph. Its analogous to the one-way traffic on roads. If there is a directed edge from u to v, then using that edge we can go from u to v, but not from v to u. If each edge has some weight associated with it, it is called a Weighted Graph.

[Add image for directed and weigted graphs Fig3]

[Add example for each of these terms from Fig2]

---

 

Now that we know what a graph is and some basic terms, lets see how to represent a graph and store it in computer memory and access it.

Representing Graphs

To represent a graph, all we need is the set of vertices, and for each vertex the neighbors of the vertex (vertices directly connected to it by an edge) and if its a weighted graph, the weight associated with each edge. There are different ways to optimally represent a graph, depending on the density of its edges. A Sparse graph has relatively less number of edges m = O(n), where as a dense graph has significantly many edges m = O(n²)

Adjacency List

In this representation, for each node in the graph we maintain the list of its neighbors. We have an array of vertices, indexed by the vertex number and for each vertex v, the corresponding array element points to a singly-linked list of neighbors of v . The following firgure shows the Adjacency list of Graphs in Fig[ ?? ]

Here are how linked lists may be created in Ruby - in case you'd like to implement the Adjacency List in Ruby.

[ Add figure(s) for adjacency list ]

Adjacency Matrix

In this representation, we construct a nxn matrix A. If there is an edge from a vertex i to vertex j , then the corresponding element of A, a_i,j = 1, otherwise a_i,j= 0. Note, even if the graph on 100 vertices contains only 1 edge, we still have to have a 100x100 matrix with lots of zeroes. For a weighted graph, instead of 1s and 0s, we can store the weight of the edge. In that case, to indicate that there is no edge we can put a safely large value (we can call it INF (infinity) ). The following firgure shows the Adjacency Matrix of Graphs in Fig[ ?? ]

[ Add figure(s) for adjacency matrix ]

While the adjacency list saves a lot of space for sparse graphs, we cannot instantly access an edge. While we can access any edge instantly in adjacency matrix, it takes a lot of space (space is fine for graphs even with n = 1000 ) and to visit all the neighbors of a vertex, we have to traverse all the vertices in the graph ( the whole row corresponding to the vertex ), which takes quite some time. So there is a trade-off between the two representations, and one has to decide depending on the problem.

---

 

Hmm.. enough with all that theory part. Now lets see a very simple technique and solve some problems using it :)

Depth First Search (DFS)

Now we know what a graph is and how to represent it. Given a graph G, how to traverse the graph ? How do we know whether a vertex u is connected to a vertex v (by some path) ? How many connected components are there in G ? How to mark all the nodes that can be reached from a vertex v (  Flood-Fill ) ?

Tutorials and source codes related to Graph Theory

Depth First Search in Graphs - Tutorial and C Program
Breadth First Search in Graphs - Tutorial and C Program
Minimum Spanning Tree - Kruskal Algorithm - Tutorial and C Program
Dijkstra Shortest Path Algorithm - Tutorial and C Program
Bellman Ford Algorithm
All Pairs Shortest Paths
Minimum Spanning Trees: Kruskal Algorithm
Dijkstra Algorithm for Shortest paths

 In case you want to see a visualization of depth-first-search and breadth-first-search you might find this page useful: http://www.thelearningpoint.net/computer-science/graph-algorithms

how to implement connected and self referential data structures in ruby or python