Graph Theory : CoderInMe

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 −

graph theory

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 NP-Complete 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 MatchingsOptimizations 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

 

Application 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 bi-directional 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.

subgraph in graph theory

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.

 

spanning tree in graph theory

 

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

A Blogger, a coder and IT Student

Leave a reply:

Your email address will not be published.