Graphs

http://install4install.com

A graph is a collections of vertices/nodes and edges(arcs).It is like a tree structure with a difference that it does not have any parent-child relationship between nodes.Instead,any complex relationships are possible between the nodes.A Graph G(Fig 1) is defined as an ordered set (V,E),where V(G) is the set of vertices and E(G) represents the edges that connect the vertices together.

Fig 2 shows a graph with V(G) = {A,B,C,D,E,F}

E(G) = {(A,B),(A,C),(B,D),(C,D),(C,F),(D,E)}

There are 6 nodes and 6 edges in this Graph.

Fig 1 : A Graph

Fig 1 : A Graph

Screen Shot 2014-05-07 at 3.18.23 PM

Fig 2 : A Graph

 

Terms associated with Graph

Types of Graphs

Directed Graph

Screen Shot 2014-05-07 at 5.14.44 PM

Fig 3 : A Directed Graph

In a directed graph,edges have an orientation and  form an ordered pair (Fig 3). If there is an edge from A to B, then there is a path from A to B but not from B to A. The edge (A, B) is said to initiate from node A (also known as initial node) and terminate at node B (terminal node).Fig 3 is a directed graph with directed edges  {(A,B),(B,D),(D,E),(E,F),(F,D)}

 

Undirected Graph

Screen Shot 2014-05-08 at 2.49.21 PM

Fig 4 : Undirected Graph

A graph is called as undirected if the edges do not have any orientation.The edge can be traversed from one point to another and vice versa.Traversal can be done from A to B and B to A in Fig 4 and same is applicable for other nodes also.

Regular Graph

Fig 5 : A Regular Graph

Fig 5 : A Regular Graph

A regular graph is a graph where each vertex Â has the same number of neighbors, i.e., every vertex has the same degree . In Fig 5.degree of every vertex is 2.

Connected Graph

Screen Shot 2014-05-08 at 3.10.39 PM

Fig 6 : A Connected Graph

A graph is said to be connected if there is no isolated node and there exists a path between any of the two nodes i.e there will be at least one edge emerging from any of the vertices  in  graph(Fig 6).

 

Complete Graph

Screen Shot 2014-05-08 at 3.13.58 PM

Fig 7 : A Complete Graph

A graph G is said to be a complete, if there is always a  path from one node to another i.e if all the nodes are fully connected(Fig 7).

Weighted Graph

Screen Shot 2014-05-08 at 3.21.58 PM

Fig 8 ; A Weighted Graph

A graph is said to be weighted if every edge has some data/value  associated with it.It is denoted by w(e) and is a positive value referring to  the cost of traversing the edge.Weight of the graph as shown in Fig 8 , w(e) is 29.Cost of traversing edge A to B is 2,B to C is 5,C to D is 6,D to E is 9,E to A is 7.

 

Multi-Graph

Screen Shot 2014-05-08 at 3.27.48 PM

Fig 9 : Multi-Graph

 

A graph in which vertex  have  multiple edges  and /or  loops is called a multi-graph(Fig 9).



Short URL: http://tinyit.cc/448888
Author: Cusp2207 on May 8, 2014
Category: Computer Science, Data Structures
Tags:

Leave a Reply

Last articles