GRAPH
=====
A graph is a datastructure consisting a set of vertices |V| and a set of edges |E|.
Vertices usually represent an entity and it might hold additional data pertaining to this entity.
The relationship between 2 different entities is represented by an edge. So if there is some relation between vertex a and vertex b, then there is an edge between a and b.
Example of graphs:
World wide web.
Social networks.
Internet Routers etc.
TYPES OF GRAPH
==============
1. UNDIRECTED GRAPHS
A graph is called as undirected graph if the edges are not directed meaning, there is a 2 way path for an edge i.e. the edge that goes out of the vertex also lead to this vertex from the connected vertex.
For eg. Social Network graph, if a is freind of b then it is tacit that b is also friend of a. Hence for representing this relation, we use an undirected graph.
Edge between a and b, leads to b from a and also to a from b.
2. DIRECTED GRAPH
A graph is called directed graph/digraph if the edges have directions meaning, the edge that goes out of a vertex doesnot lead to this vertex from connected vertex.
For eg. consider road network, It is possible that there is a one way road between city a and city b, hence people can reach b from a but not a from b since the graphs are directed.
3. WEIGHTED GRAPH
A graph is called as weighted graph if some weight is assigned to the edges.
For eg, again condier road network, There are 2 ways to reach city b from city a, but one of the path is shorter than the other than to represent this, we assign weight to the edges connecting city b from city a, the path taking less time is assign less weight and path taking more time might be assing more weight.
GRAPH REPRESENTATION
====================
There are many ways to represent graphs:
1. Adjacency Matrix.
2. Adjacency List.
3. Incidence Matrix.
4. Incidence List.
=====
A graph is a datastructure consisting a set of vertices |V| and a set of edges |E|.
Vertices usually represent an entity and it might hold additional data pertaining to this entity.
The relationship between 2 different entities is represented by an edge. So if there is some relation between vertex a and vertex b, then there is an edge between a and b.
Example of graphs:
World wide web.
Social networks.
Internet Routers etc.
TYPES OF GRAPH
==============
1. UNDIRECTED GRAPHS
A graph is called as undirected graph if the edges are not directed meaning, there is a 2 way path for an edge i.e. the edge that goes out of the vertex also lead to this vertex from the connected vertex.
For eg. Social Network graph, if a is freind of b then it is tacit that b is also friend of a. Hence for representing this relation, we use an undirected graph.
Edge between a and b, leads to b from a and also to a from b.
2. DIRECTED GRAPH
A graph is called directed graph/digraph if the edges have directions meaning, the edge that goes out of a vertex doesnot lead to this vertex from connected vertex.
For eg. consider road network, It is possible that there is a one way road between city a and city b, hence people can reach b from a but not a from b since the graphs are directed.
3. WEIGHTED GRAPH
A graph is called as weighted graph if some weight is assigned to the edges.
For eg, again condier road network, There are 2 ways to reach city b from city a, but one of the path is shorter than the other than to represent this, we assign weight to the edges connecting city b from city a, the path taking less time is assign less weight and path taking more time might be assing more weight.
GRAPH REPRESENTATION
====================
There are many ways to represent graphs:
1. Adjacency Matrix.
2. Adjacency List.
3. Incidence Matrix.
4. Incidence List.
No comments:
Post a Comment