# Graph Theory

This category is the parent of all articles which have mention of Graphs and Graph related problems.

## Minimum Spanning Tree Prim’s Algorithm

Introduction What is the minimum length of the network cable we require if we have to connect 100 computing machines in a building distributed across multiple floors? How do I guarantee that there can be no other minimum length possible than what I derive? Why is it even important to find the minimum length? The history of the problem You can read the classic problem solved by MST Applications of Minimum Spanning Tree Defining Spanning Trees A spanning tree is always defined for a weighted Graph G(V,E) where the weights are positive. This means that all the edges carry some positive we...

## Shortest Path using Dijkstra’s Algorithm

Introduction This is the third post in the Graph Traversals – Online Classes. After learning how to move through a graph, we might be interested in learning more. One interesting problem is determining the shortest path between two vertices of a graph. The problem can be extended and defined in many other forms. I prefer to call it "minimizing the cost". For e.g. When we measure the cost in terms of the distances between vertices, it can be called as the Shortest Path. When we measure the cost in terms of the money spent between vertices, it can be called as the Cheapest Path. Whe...

## Depth First Traversal

Introduction This is the second post in the Graph Traversals – Online Classes. I Recommend you to look at the first post Breadth First Traversal as it contains more explanation and details and I will keep this post smaller just around the depth first concept. Depth First Traversal The Idea In this traversal, we choose a start vertex and keep moving forward along the length of the graph until there is no undiscovered vertex in that path. Once reaching a dead end, we back track to all the visited vertices and check if we have any vertex which has an adjacent undiscovered vertex. We kee...

## Complex Graph Operations

Introduction This is the fourth article in the Graph Theory - Online Classes. After learning the basic graph operations, its time to dive deeper and have some understanding about the complex operations which we can be done over a graph or a set of graphs. To learn about the basics you can always visit Graph Theory Basics. Complex Graph Operations Union of Graphs The union of two graphs G(VG, EG) and H(VH, EH) is the union of their vertex sets and their edge families. Which means G ∪ H = (VG ∪ VH, EG ∪ EH). The below image shows a union of graph G and graph H. Make sure that all the v...

## 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...