What is a Graph ? Explain Graph Terminology?


Graph : A graph is a  non linear data structure which organizes data values in memory as a network form then it provides relationship between them. Data values stored in memory are called vertices of a graph and relationship between different parts of vertices in a graph are called edges.

(or)

A graph is defined as set of vertices and set of edges where each edge is formed between pair of vertices. A graph is represented by G= (v, E) where ‘v’ is set of vertices and ‘E’ is set of edges. Each edge in E is relationship between pair of vertices belonging to E

Ex 1 : G1           

graph
                                           










G1=( V1, E1)
V1 ={1,2,3,4}
E1={(1,2),(2,3),(3,4),(4,1),(2,4)}


Terminology Used in Graphs:
  
Vertex : vertex is also called as node in graphs. A vertex is a memory location where data is stored . All the vertices in graphs collectively called as vertices.

Ex : in the above example G1 , V1 =(1, 2, 3 ,4}

Adjacent Node : Any two nodes which are connected by an edge in a graph are called adjacent nodes.

Ex : nodes 1 and 2 are adjacent nodes in graph G1

Directed Edge : In a graph G =(V , E)an edge which is directed from one node to another node is called as directed edge. Directed edges are shown by ‘®’.

Ex : (1 , 2), (2, 3), (3, 4) are directed edges in graph G1.

Undirected Edge : in a graph G=(V, E) an edge which has no specified direction is called an undirected edge. These are denoted by “___”,

Ex : (7, 8),(8, 5),(5 ,6) are undirected edges in group G2.

Out Degree of a Node : In a directed graph for any node V, the number of edges which are going out from a node V is called the out degree of V.

Ex :

out degree











out degree of 1 is -2                                              
Out degree of 2 is -1
Out degree of 3 is -1
Out degree of 4 is -2

Indegree of a Node :In a directed graph for any node V , the number of edges which are coming into the node V is called the indegree of ‘V’.

in degree











In  degree of 1  is 0                                    
In  degree of 2 is -2
In  degree of 3 is -2
In  degree of 4 is -2

Total Degree of a Node : The sum of out degree and in degree of node ‘V’ is called the total degree of node V for the above graph.

          Total degree of 1 is -2
Total degree of 1 is -3
Total degree of 1 is -3
Total degree of 1 is -4

Note : the total degree of an isolated node is zero.

Cycle or Circuit :  A path which originates and ends with the same node is called a circuit or cycle. A cycle is called elementary if it doesn’t travels through any node more than once.

Ex :

cycle











C1={(2, 2)}
C2={(1 , 2), (2,1)}
C3={(2,3),(3,1),(1,2)}

Acyclic Graph : a simple graph which does not have any cycle is called “acyclic graph”.

acycle graph








Directed Graph or Digraph : A graph in which every edge is directed is called as directed graph.

Ex : G1 graph

Undirected Graph : A graph in which every edge is undirected is called as an undirected graph.

Ex : G2 graph

Mixed Graph : A graph in which some of the edges are directed and some of the edges are undirected is called a mixed graph.

Ex :

mixed graph








Loop :  The edge of a graph  which joins a node to itself is called a loop. It can be either directed edge or undirected edge.

Ex :

loop








(2 ,2) and (3, 3)

Parallel Edges : A pair of nodes joined by more than one edge are called parallel edges.

Ex :

parallel edges








Simple Graph : Any graph which doesn’t have any parallel edges is called simple graph.

Ex :

graph










Multi Graph :Any graph which contains some parallel edges is called multi graph.

Ex :

multi graph









Isolated  Node : In a graph a node which is not adjacent to any other node is called a isolated node.

Ex :

isolated


















1   is called isolated node .

Null Graph : A graph containing only isolated nodes is called null graph . The set of edges in null graph is empty.

Ex :

null graph






Path of a Graph: Any sequence of edges of a graph suchthat the terminal node of any edge in the sequenceis the initial node of the edge appearing next in the sequence , if any.

Number of edges appearing in the sequence of a path is called length of the path.

Ex :

path








Path from node 2 to node 4

Path
P1 =(2, 4)
P2  =((2, 3),(3, 4))
P3 = ((2, 1), (1, 4))
P4=((2, 3), (3,2),(2, 4))
P5=((2, 3),(3, 1),(1 , 4))
P6=((2,2), (2, 4))
Length
1
2
2
3
3
2



Related

Data Structures 1490722379079974595

Post a Comment

emo-but-icon
:noprob:
:smile:
:shy:
:trope:
:sneered:
:happy:
:escort:
:rapt:
:love:
:heart:
:angry:
:hate:
:sad:
:sigh:
:disappointed:
:cry:
:fear:
:surprise:
:unbelieve:
:shit:
:like:
:dislike:
:clap:
:cuff:
:fist:
:ok:
:file:
:link:
:place:
:contact:

item