Facebook

Graphs

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

  • Adjacent Nodes -  For every edge, E = (U, V) that connects nodes U and V; the nodes U and V are the end-points and are said to be the adjacent nodes.In Fig 2,A and B are adjacent nodes.
  • Degree - Degree of a node a is the total number of edges associated with the particular node.For e.g. ,degree of vertex A  in Fig 2 is 2.
  • Path - The route/way followed by edges from one node to another node.
  • Cycle - A closed simple path with length 3 or more is known as cycle.For e.g. P = {A,B,D,E,F,D} forms a cycle in Fig 3.
  • Multiple edges - Distinct edges which connect the same end points/vertex are known as multiple edges.E = (A,C) and E' = (D,C) are multiple edges in Fig 2.
  • Loop - An edge that has identical end points is called as Loop.P = {A,B,D,C,A} forms a loop in Fig 2.
  • Size of Graph - It is the total number of edges in the graph.Size of graph in Fig 2 is 6.

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).

Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar