CS 103 1 Graphs • Definition of Graphs and Related Concepts Notes | EduRev

Created by: Kamran Nasir

: CS 103 1 Graphs • Definition of Graphs and Related Concepts Notes | EduRev

 Page 1


CS 103 1 
Graphs  
• Definition of Graphs and Related 
Concepts 
• Representation of Graphs 
• The Graph Class  
• Graph Traversal 
• Graph Applications 
Page 2


CS 103 1 
Graphs  
• Definition of Graphs and Related 
Concepts 
• Representation of Graphs 
• The Graph Class  
• Graph Traversal 
• Graph Applications 
CS 103 2 
Definition of Graphs 
• A graph is a finite set of nodes with edges 
between nodes 
• Formally, a graph G is a structure (V,E) 
consisting of  
– a finite set V called the set of nodes, and 
– a set E that is a subset of VxV. That is, E is a set 
of pairs of the form (x,y) where x and y are nodes 
in V  
 
Page 3


CS 103 1 
Graphs  
• Definition of Graphs and Related 
Concepts 
• Representation of Graphs 
• The Graph Class  
• Graph Traversal 
• Graph Applications 
CS 103 2 
Definition of Graphs 
• A graph is a finite set of nodes with edges 
between nodes 
• Formally, a graph G is a structure (V,E) 
consisting of  
– a finite set V called the set of nodes, and 
– a set E that is a subset of VxV. That is, E is a set 
of pairs of the form (x,y) where x and y are nodes 
in V  
 
CS 103 3 
Examples of Graphs 
• V={0,1,2,3,4} 
• E={(0,1), (1,2), (0,3), (3,0), (2,2), (4,3)} 
 
0 
1 
4 
2 
3 
When (x,y) is an edge, 
we say that x is adjacent to 
y, and y is adjacent from x. 
 
0 is adjacent to 1. 
1 is not adjacent to 0. 
2 is adjacent from 1. 
Page 4


CS 103 1 
Graphs  
• Definition of Graphs and Related 
Concepts 
• Representation of Graphs 
• The Graph Class  
• Graph Traversal 
• Graph Applications 
CS 103 2 
Definition of Graphs 
• A graph is a finite set of nodes with edges 
between nodes 
• Formally, a graph G is a structure (V,E) 
consisting of  
– a finite set V called the set of nodes, and 
– a set E that is a subset of VxV. That is, E is a set 
of pairs of the form (x,y) where x and y are nodes 
in V  
 
CS 103 3 
Examples of Graphs 
• V={0,1,2,3,4} 
• E={(0,1), (1,2), (0,3), (3,0), (2,2), (4,3)} 
 
0 
1 
4 
2 
3 
When (x,y) is an edge, 
we say that x is adjacent to 
y, and y is adjacent from x. 
 
0 is adjacent to 1. 
1 is not adjacent to 0. 
2 is adjacent from 1. 
CS 103 4 
A “Real-life” Example of a Graph 
• V=set of 6 people: John, Mary, Joe, Helen, 
Tom, and Paul, of ages 12, 15, 12, 15, 13, 
and 13, respectively. 
• E ={(x,y) | if x is younger than y} 
 
John 
Joe 
Mary Helen 
Tom Paul 
Page 5


CS 103 1 
Graphs  
• Definition of Graphs and Related 
Concepts 
• Representation of Graphs 
• The Graph Class  
• Graph Traversal 
• Graph Applications 
CS 103 2 
Definition of Graphs 
• A graph is a finite set of nodes with edges 
between nodes 
• Formally, a graph G is a structure (V,E) 
consisting of  
– a finite set V called the set of nodes, and 
– a set E that is a subset of VxV. That is, E is a set 
of pairs of the form (x,y) where x and y are nodes 
in V  
 
CS 103 3 
Examples of Graphs 
• V={0,1,2,3,4} 
• E={(0,1), (1,2), (0,3), (3,0), (2,2), (4,3)} 
 
0 
1 
4 
2 
3 
When (x,y) is an edge, 
we say that x is adjacent to 
y, and y is adjacent from x. 
 
0 is adjacent to 1. 
1 is not adjacent to 0. 
2 is adjacent from 1. 
CS 103 4 
A “Real-life” Example of a Graph 
• V=set of 6 people: John, Mary, Joe, Helen, 
Tom, and Paul, of ages 12, 15, 12, 15, 13, 
and 13, respectively. 
• E ={(x,y) | if x is younger than y} 
 
John 
Joe 
Mary Helen 
Tom Paul 
CS 103 5 
Intuition Behind Graphs 
• The nodes represent entities (such as people, cities, 
computers, words, etc.) 
• Edges (x,y) represent relationships between entities x and 
y, such as: 
– “x loves y”  
– “x hates y” 
– “x is a friend of y” (note that this not necessarily reciprocal) 
– “x considers y a friend” 
– “x is a child of y” 
– “x is a half-sibling of y” 
– “x is a full-sibling of y” 
• In those examples, each relationship is a different graph 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!