Courses

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

## : 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.

1 is not adjacent to 0.
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.

1 is not adjacent to 0.
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.

1 is not adjacent to 0.
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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!