|
Sorry! I can't
give that mathematical definition, involving all those Vs and Es,
for the Graphs. Rather, take it this way - a graph is a collection of
some finite VERTICES and some finite EDGES which happen to connect
these vertices. If I consider a given list of cities as my list of
VERTICES then you can, probably, call the air routes between them as to
be the EDGES for them.
Based on this analogy, we can say that a
Directed Graph is a one in which you have one way air routes and that
you can not come back through that same route; means, you can fly from
Delhi to Mumbai but can not come back through that same route.
Similarly, if you have two way air routes between the cities then I call
it, an Undirected Graph. Finally, if its not a sponsored journey then
certainly you will have to bear the ticket fare, which means every route
(EDGE) has some cost of journey attached and that makes it a Weighted
Graph. No fare, no weight!
Directed
Graph:- Vertices(cities): A, B, C and
D Edges(routes): AB, AC, CD
Undirected Graph:- Vertices: A, B, C,
D Edges: AB, AC, BA, CD,
DC
Weighted Graph:- Vertices: A, B, C,
D Weighted Edges: AC-10, AB-17, CD-13
You might be thinking by now, what these
Graphs have to do with computers! Well, to name a few I'll give you some
applications of it - in the study of information routing on computer
networks (helps in finding the shortest routes); electronic circuit
designing (helps to find out the electrical loops and overlaps);
ticketing software uses it to find out the shortest route... Got the
idea!
Note:-
When I said route here, I
meant the direct path between the adjacent vertices and that no other vertex is
there in that path except the two adjacent vertices forming the path.
Related Operations:
Concept
-- non-directed, directed and weighted
Adjacency matrix of a Graph
Linked representation of a Graph
Traversals – Depth First
& Breadth first Search
Transitive closure/ Warshall’s algorithm
Shortest Path Algorithm
Spanning Tree Algorithm
|
|
