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 graphRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!