What is a Graph ? Explain Graph Terminology?
https://www.computersprofessor.com/2016/11/what-is-graph-explain-graph-terminology.html
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
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 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 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 :
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”.
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 :
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 :
(2 ,2) and (3, 3)
Parallel Edges : A pair of nodes joined by more than one edge are called parallel edges.
Ex :
Simple Graph : Any graph which doesn’t have any parallel edges is called simple graph.
Ex :
Multi Graph :Any graph which contains some parallel edges is called multi
graph.
Ex :
Isolated Node : In a
graph a node which is not adjacent to any other node is called a isolated node.
Ex :
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 :
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 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
|
