Graph Theory

Preface

This is the first article in the Graph Theory – Online Classes. To all my readers and friends, you can safely skip the first two paragraphs.

The motivation to write this series
Its been long I have been planning to write this article and now I think is the right time to start a new category & series of articles in the Graph Theory. As a student it was always the most complicated topic for me and I was scared with the topic. I am sure many of you must have faced the same. Of course everyone has their own reason, for me it was the order in which it was taught and definitely it was complex. The topic used to be the last in the Data Structures and Algorithms and by the time we reached that, there was never enough time to understand this in detail. Thank fully now I have all the time to write this as I wanted. The study of graphs is tightly connected to Discrete Mathematics, and there may be places where we will refer to those concepts. In such cases I will provide links to required articles.

What to expect?
Well, you can expect most of the topics taught in graph theory here in subsequent articles. It would be tough for us to visit all available problems in Graph Theory, but we will be taking up several interesting and famous problems. One such problem is the Instant Insanity problem, to know more check out my section of the article on Wikipedia.org
You can also expect more details on all types of Graphs (Connected, Disconnected, Bipartites, Directed, Isomorphic, Simple, Complete, Eulerian, Hamiltonian, Planar, Null, Regular, Cubic, Peterson, Platonic, Star, Circuit, Wheel and many more). Of course we will start from the basics and try to build the foundation first. We will also learn about the algorithms we use and operations we can do on such graphs in detail.

So without much of a delay, let us start with the basics. If you are interested in learning all these topics in simple and easy way, you can choose to Subscribe us using email or get connected to us on FB, Twitter, Tumblr, Google+ or all the pages. 🙂

Introduction – Graph Theory

What is a Graph?
Few of the examples of valid graphs are:

  • The planets in the solar system.
  • The road network in a city.
  • The electrical circuit on a PCB.
  • The representation of number of way people in a group can shake hands.
  • The wheel of your bicycle.
  • The ceiling fan.
  • Your linkedin connections.

There are many more examples which can be a valid graph. Please see the below images each one is a valid graph.
graph theory
Terminologies

    1. Vertex : Each of the circles in the images are vertices. Graph 1 has 5 vertices, Graph 2 has 4 vertices, Graph 3 has 4 vertices and Graph 4 has 6 vertices.
    2. Edges : Each of the lines connecting the vertices are called edges. An edge connects two vertices. Graph 1 has 5 edges, Graph 2 has 3 edges, Graph 3 has 0 edges and Graph 4 has 4 edges.

graph theory

  1. Degree of a Vertex : Degree is defined for a vertex. It is the number of edges connected (coming in or leaving out, for the graphs in given images we cannot differentiate which edge is coming in and which one is going out) to a vertex. Let us name the vertices in Graph 5, the vertex S has degree 3, the vertices P, Q and R has degree 2 and the vertex T has degree 1.
  2. Loops : In a graph, if an edge starts and ends on the same vertex, it is called a loop. In Graph 6 vertex Z has a loop.
  3. Multiple Edges : In a graph, if two vertices are connected with more than 1 edge, it is called multiple edges. In Graph 7 vertices P, R and S, Q have multiple edges.
  4. Simple Graphs :A graph which has no loops or multiple edges is called a simple graph. Graph 1, Graph 2, Graph 3, Graph 4 and Graph 5 are simple graphs.
  5. Directed Graphs : In all the above graphs there are edges and vertices. It is tough to find out if a given edge is incoming or outgoing edge. If the graph carries that information with itself, it is called a directed graph. In such a graph, an edge is drawn using an arrow instead of a line. Graph 8 is a directed graph. A directed graph is also called a diagraph.

Any graph can be converted into a directed graph by replacing each of its edge with two edges one in each direction. See the below image.
graph theory

Some simple operations on a Graph

A Walk in a graph
A walk is termed as a sequence of edges. A vertex can appear more than once in a walk. For the Graph 7, a possible walk would be P -> R -> Q is a walk. Also, Q -> S -> Q -> R -> P -> R -> T is another walk.

A Path in a graph
A path is a walk in which the vertices do not repeat, that means no vertex can appear more than once in a path. For the Graph 7, a possible path would be P -> R -> Q. Another path could be P -> R -> T -> S -> Q

Adding the image again for convenience
graph theory

A Circuit is a path which begins and ends at the same vertex. In Graph 5 P -> Q -> R -> S -> P is a circuit.

There are many more concepts which we will talk about as and when required. With the above knowledge we acquired, it is good enough time to formally define a Graph.

A Simple Graph G is defined as a pair (V(G), E(G)) where V(G) is a non-empty finite set of vertices or points and E(G) is a finite set of edges. Also, E(G) can be further defined as a finite set of unordered pair of distinct elements of V(G). For the below graph (Graph 9) V(G) = { u, v, w, x, y} and E(G) = { 1, 2, 3, 4, 5 }. Also, E(G) can be represented as E(G) = {{x,u}, {u,v}, {v,w}, {w,x}, {x,y}}.
graph theory graph4
By this definition we can deduce that the a graph must contain at least one vertex.

All graphs are not simple graphs, there are graphs with multiple edges and loops as well, so if we want to define more generalized graphs then we need to update our definition of graphs. Hence the new definition is:
“A Graph G is defined as a pair (V(G), E(G)) where V(G) is a non-empty finite set of vertices or points and E(G) is a finite family of edges. Also, E(G) can be further defined as a finite family of unordered pair of distinct elements of V(G). We use the word family so that it can account for multiple edges between two vertices.”

For the above graph (Graph 10) V(G) = { a, b, c, d, e} and E(G) = { 1, 2, 3, 4, 5, 6, 7 }. Also, E(G) can be represented as E(G) = {{a,b}, {b,c}, {b,c}, {c,d}, {d,a}, {e,d}, {d,e}}.

If an edge uv connects two vertices u and v of a graph, then u and v are called adjacent vertices. Also, the vertices u and v are said to be incident on the edge uv.

Storing a graph

How do we represent a graph in a program?

It is a good idea to store the graph as a set of vertices V(G) and a set of edges E(G) as per our definition. There are few more ways we can store them and it can be useful because these ways uses a 2-dimensional array (or we can say a matrix).

Adjacency Matrix
An adjacency matrix is a N * N matrix where N is the number of vertices. Each cell of the matrix contains zero or a positive number. The number is the count of edges connecting the two vertices. Here is the adjacency matrix for Graph 9.
graph theory adjancency matrix

Adding the above graph again for convinience
graph theory graph4

Incidence Matrix
An incidence matrix is a M * N matrix where M is the number of edges and N is the number of vertices. Each row represents an edge and each cell in a row can either be a zero or a one. If the value is zero for a vertex then the vertex is not incidence on the edge and if the value is one for the vertex then the vertex is incident on the edge. Here is the Incident matrix for Graph 9.
graph theory incidentmatrix
Another representation is an Adjacency List, where each row of the adjacency matrix can be represented as one list. We can remove the nodes which contain a zero to save some space.

We end up this post with the mention of graph storage, In subsequent posts, we will learn more about graphs. Stay connected and stay subscribed.

  • Nillu

    A walk is a sequence of vertices and edges, v1,e1,v2,e2,v3,e3… where vi and ei denotes the ith vertices and edge respectively, also each edge ei is incident to vi and vi+1