Applications of Graphs - Assignment No 4 (Solved)

Graph

            A Graph is a non-linear data structure consisting of nodes and edges to represent the relationship among the objects. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

Or

A Graph consists of a finite set of vertices (or nodes) and set of Edges which connect a pair of nodes.

Types of Graphs

i.                    Simple Graph

ii.                  Multi Graph

iii.                Pseudo Graph

iv.                Directed Graph

v.                  Multi-Directed Graph

Simple Graph

            Simple Graph is an undirected graph containing no graph loops or multiple edges. It is a graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices.

Example:

            The Social Network is the example of Simple Graph.

Multi Graph

            Multi Graph is a graph in which two vertices can be conned with more than one edges but loop edges are not allowed.

Example

            Inter-City cites road network.

Pseudo Graph

            Pseudo Graph is same like Multi Graph but edges connecting a node to itself are allowed.

Example:

            A computer network model with a diagnostic links with our PC. In which we can send a request to own PC to diagnose.

Directed Graph:

            A directed graph is graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another. A directed graph is sometimes called a digraph or a directed network

Example:

1.      To Show the Friend Request Relationship, Directed graph is used.

2.      Intra-City Road Network which needs directions also.

Directed Multi Graph

            A graph which has directed parallel edges is called Directed Multi Graph.

Example

1.      www (World Wide Web) is the best example of Directed Graph. And the application of Directed graph is web crawling e.g google web crawler)