All of us might have come across graphs in our life at some point in time these graphs may be pictorial graphs or line graphs etc. But here we talking about something different. Let’s first ask the simple question—?
What is Graph Theory?
A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices. Take a look at the following graph −
The lines represented in this diagram are actually the links it’s just like connecting dots with each other this diagrams must make a clear picture of a graph.
Why Graph Theory?
Why learn a new concept? Why increase the burden of defining a whole new domain of concept which includes numerous algorithms?
Many Graph Problems are NPComplete and provide a useful tool for study in Computational Complexity.
Graph Theory can be studied using tools from Topology, Combinatorics and Algebra.
– Topological Properties include Planarity and Embeddings.
– Combinatorial Properties include Matchings, Optimizations and Path
Since now it’s clear what the actual importance is. Now let’s quickly have a glimpse at some of the application of this concept as this would really motivate us to go the depth of concept.
Applications of Graph Theory
Graph theory has its applications in diverse fields of engineering −
 Electrical Engineering− The concepts of graph theory is used extensively in designing circuit connections.
 Computer Science− Graph theory is used for the study of algorithms. For example,

 Kruskal’s Algorithm
 Prim’s Algorithm
 Dijkstra’s Algorithm
 Computer Network− the relationships among interconnected computers in the network follows the principles of graph theory.
It’s really fascinating to know how important applications are of this particular concept let’ quickly have a look at some of the graphs.
Some of the graphs are mentioned here:
 Simple graph
 Undirected or directed graphs
 Cyclic or acyclic graphs
 labeled graphs
 Weighted graphs
 Infinite graphs
These graphs are really simple to trust me only understanding the basic concept will clear your concept.
The basic concept behind the graph theory is that how different nodes are to be connected with each other. The pattern of connection between all the nodes will define the type of graph and its properties.
Basic Operations performed are as follows
 Removing one or more vertices from the vertex set or edges from the edge family or either vertices or edges from the graph.
 Conversion from Directed Graph to Undirected graph
 Conversion from Undirected Graph to Directed graph
 Reversing a graph
 Deriving a Simple graph
These graphs actually the basic building blocks of your concept and find application in a real world as such. Consider the telephone connections as a graph now the point “Removing one or more vertices from the vertex set” is just like adding new connections to the graph.
Undirected Graph: Graph having all the edges bidirectional sometimes referred to as a undirected network.
Directed Graph: Graph having all the edges directed is referred to as a directed graph.
Sub Graph: Graph whose vertices edges are passed of some other graph is referred to as sub graph.
Neighborhood 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 Neighborhood graph of G(V,E) for vertex set {1}.
So, the neighbourhood graphs contain the vertices 1 and all the edges incident on them and the vertices connected to these edges.
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.
Note:
All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin @coderinme