Graph Operations

Introduction

This is the third article in the Graph Theory – Online Classes.

With some basic concepts we learnt in the previous two articles listed here in Graph Theory, now we have enough tools to discuss some operations on any graph. In this article we will try to define some basic operations on the Graph.

Graph Operations – Extracting sub graphs

In this section we will discuss about various types of sub graphs we can extract from a given Graph.

Sub graph

Getting a sub graph out of a graph is an interesting operation. A sub graph of a graph G(V,E) can be obtained by the following means:

  • Removing one or more vertices from the vertex set.
  • Removing one or more edges from the edge family.
  • Removing either vertices or edges from the graph.

Points worth noting

  • The vertices of sub graphs are subsets of the original vertices
  • The edges of sub graphs are subsets of the original edges

We can extract sub graphs for simple graphs, directed graphs, multi edge graphs and all types of graphs.
The Null Graph is always a sub graph of all the graphs. There can be many sub graphs for a graph.
Below is a graph and its sub graphs.

Graph Operations

Neighbourhood graph

The neighbourhood graph of a graph G(V,E) only makes sense when we mention it with respect to a given vertex set. For e.g. if V = {1,2,3,4,5} then we can find out the Neighbourhood graph of G(V,E) for vertex set {1}.

So, the neighbourhood graphs contains the vertices 1 and all the edges incident on them and the vertices connected to these edges.
Below is a graph and its neighbourhood graphs as described above.
neighbourhoodgraph
We can also extract neighbourhood graph for a distance more than 1, which means that we do not stop at the first neighbour and also extend it to second, third and more.
Another example for neighbourhood graph up to distance 2 is given below:
Graph Operations

Spanning Tree

A spanning tree of a connected graph G(V,E) is a sub graph that is also a tree and connects all vertices in V. For a disconnected graph the spanning tree would be the spanning tree of each component respectively.

There is an interesting set of problems related to finding the minimum spanning tree (which we will be discussing in upcoming posts). There are many algorithms available to solve this problem, for e.g.: Kruskal’s, Prim’s etc. Note that the concept of minimum spanning tree mostly makes sense in case of weighted graphs. If the graph is not weighted, we consider all the weights to be one and any spanning tree becomes the minimum spanning tree.

We can use traversals like Breadth First Scan and Depth First Scan to fight the Spanning Tree. We can find spanning tree for undirected graphs, directed graphs, multi graphs as well.

Below is an example of spanning tree for the given graph.
spanningtree

Graph Operations – Conversions of Graphs

In this section we discuss about converting one graph into another graph. Which means all the graphs can be converted into any of the below forms.

Conversion from Directed Graph to Undirected graph

This is the simplest conversions possible. A directed graph has directions represented by arrows, in this conversion we just remove all the arrows and do not store the direction information. Below is an example of the conversion.
Please note that the graph remains unchanged in terms of its structure. However, we can choose to remove edges if there are multi edges. But it is strictly not required.
undirected

Conversion from Undirected Graph to Directed graph

This conversion gives a directed graph given an undirected graph G(V,E). It is the exact reverse of the above. The trick to achieve this is to add one edge for each existing edge in the edge family E. Once the extra edges are added, we just assign opposite direction to each pair of edges between connecting vertices.

Below is a demonstration for the same.
DIRECTED

Reversing a graph

Reversing a graph is an operation meant for directed graphs. To reverse a graph we reverse the direction of the edges. The reverse graph has the same vertex set as the original graph. As the edges are reversed, the adjacency matrix for this graph is the Transpose of the adjacency matrix for the original graph (Left to the user to draw and check if this holds true).

Below is the illustration of reversing a graph G(V,E)
REVERSE

Deriving a Simple graph

The operation is to derive a simple graph out of any given graph. A simple graph by definition must not contain any self loops or multi edges. As we understand that a graph can contain loops and multiple edges, this operation shall remove the loops and multiple edges from the graph G(V,E) to obtain a simple graph.

The adjacency matrix of such a graph will surely have the diagonal elements as zero, because there is no self loops.
Below is the image to demonstrate this operation.
smiplegraph

Graph Operations – Modifications of Graphs

This section talks about some important modifications on a graph. These operations will majorly change the structure of the underlying graph.

Delete Vertex

What happens when we delete a vertex from a given Graph G(V, E)?
We cannot successfully remove a vertex if we do not remove all the edges incident on the vertex. Once we remove the vertex then the adjacency matrix will not contain the row and column for the corresponding vertex.
This operation changes the vertex set and the edge family of the graph.

Below image helps in understanding the removal of vertex.
removevertex

Contract Vertex

One of the important operations on a graph is contraction. It can be done by contracting two vertices into one. Also, it can be done by contracting an edge, which we will see later in this article.

We cannot contract one vertex, for contraction we need a set of vertices, minimum two. Contraction can only be done when there is an edge between the two vertices. The operation basically removes all the edges between the two vertices.

In the below illustration vertices 1,2 are contracted and 5,6 are also contracted. Please notice the removal of edges between them.
contracting

Add & Delete Edge

Adding an edge to a graph can be done by connecting two given vertices.
Deleting an edge can be done by removing the connection between the given vertices. I am not putting any image as it is very trivial operation.

Contracting an Edge

Edge contraction is exactly similar to vertex contraction. It removes the edge from the graph and merges the vertices on which the edge is incident.

We will be ending up this post here, in the next post we will try to do some more complex operations like Union, Difference, Intersection Disjoint, Union etc. Don’t forget to subscribe to TechieMe to get updates on latest posts.