graph is a visual representation of data or a mathematical relationship between points.ppt

A graph is a visual representation of data or a mathematical relationship between points, often displayed as lines, curves, or bars. In computer science and mathematics, a graph is a data structure of vertices (nodes) connected by edges (links) used to model relationships between objects, such as social networks or road maps.

1. Lecture 22: Graphs Data Structures
Graphs

2. Lecture 22: Graphs Data Structures
Graph Definitions
•A graph G is denoted by G = (V, E) where
–V is the set of vertices or nodes of the graph
–E is the set of edges or arcs connecting the vertices in V
•Each edge E is denoted as a pair (v,w) where v,w V
For example in the graph below
1
2
5
6 4
3
V = {1, 2, 3, 4, 5, 6}
E = {(1, 2) (2, 5) (3, 6) (4, 6) (5, 6)}
•This is an example of an unordered
or undirected graph

3. Lecture 22: Graphs Data Structures
Graph Definitions (contd.)
•If the pair of vertices is ordered then the graph is a directed
graph or a di-graph
1
2
5
6 4
3 Here,
V = {1, 2, 3, 4, 5, 6}
E = {(1, 2) (2, 5) (5, 6) (6, 3) (6, 4)}
•Vertex v is adjacent to w iff (v,w)  E
•Sometimes an edge has another component called a weight or
cost. If the weight is absent it is assumed to be 1

4. Lecture 22: Graphs Data Structures
Graph Definitions: Path
•A path is a sequence of vertices w
1
, w
2
, w
3
, ....w
n
such that
(w
i, w
i+1)  E
•Length of a path = # edges in the path
•A loop is an edge from a vertex onto itself. It is denoted by
(v, v)
•A simple path is a path where no vertices are repeated
along the path
•A cycle is a path with at least one edge such that the first
and last vertices are the same, i.e. w
1 = w
n

5. Lecture 22: Graphs Data Structures
Graph Definitions: Connectedness
•A graph is said to be connected if there is a path from every vertex to
every other vertex
•A connected graph is strongly connected if it is a connected graph as
well as a directed graph
•A connected graph is weakly connected if it is
–a directed graph that is not strongly connected, but,
–the underlying undirected graph is connected
1
2
5
6 4
3
1
2
5
6 4
3
Strong or Weak?

6. Lecture 22: Graphs Data Structures
Applications of Graphs
•Driving Map
–Edge = Road
–Vertex = Intersection
–Edge weight = Time required to cover the road
•Airline Traffic
–Vertex = Cities serviced by the airline
–Edge = Flight exists between two cities
–Edge weight = Flight time or flight cost or both
•Computer networks
–Vertex = Server nodes
–Edge = Data link
–Edge weight = Connection speed
•CAD/VLSI

7. Lecture 22: Graphs Data Structures
Representing Graphs: Adjacency Matrix
•Adjacency Matrix
–Two dimensional matrix of size n x n where n is the number of
vertices in the graph
–a[i, j] = 0 if there is no edge between vertices i and j
–a[i, j] = 1 if there is an edge between vertices i and j
–Undirected graphs have both a[i, j] and a[j, i] = 1 if there is an edge
between vertices i and j
–a[i, j] = weight for weighted graphs
•Space requirement is (N
2
)
•Problem: The array is very sparsely populated. For example if a
directed graph has 4 vertices and 3 edges, the adjacency matrix has 16
cells only 3 of which are 1

8. Lecture 22: Graphs Data Structures
Representing Graphs: Adjacency List
•Adjacency List
–Array of lists
–Each vertex has an array entry
–A vertex w is inserted in the list for vertex v if there is an outgoing
edge from v to w
–Space requirement = (E+V)
–Sometimes, a hash-table of lists is used to implement the
adjacency list when the vertices are identified by a name (string)
instead of an integer

9. Lecture 22: Graphs Data Structures
Adjacency List Example
1
2
5
6 4
3
1
2
3
4
5
6
2
5
6
43
Graph Adjacency List
•An adjacency list for a weighted graph should contain two elements in
the list nodes – one element for the vertex and the second element for
the weight of that edge

10. Lecture 22: Graphs Data Structures
Application of Graphs
Using a model to solve a complicated traffic light Using a model to solve a complicated traffic light
problemproblem
•GIVEN: A complex intersection.
• OBJECTIVE: Traffic light with minimum phases.
•SOLUTION:
• Identify permitted turns, going straight is a “turn”.
• Make group of permitted turns.
• Make the smallest possible number of groups.
• Assign each phase of the traffic light to a group.

11. Lecture 22: Graphs Data Structures
Using a model to solve a complicated traffic light problemUsing a model to solve a complicated traffic light problem
A
B
C
D
E
An intersection

12. Lecture 22: Graphs Data Structures
Using a model to solve a complicated traffic Using a model to solve a complicated traffic
light problemlight problem
Roads C and E are one way, others are two
way.
There are 13 permitted turns.
• EB,EC,ED,EA
• AB,AC,AD
• BA,BC,BD
• DA,DB,DC
Some turns such as AB (from A to B) and EC
can be carried out simultaneously.
Other like AD and EB cross each other and
can not be carried out simultaneously.
The traffic light should permit AB and EC
simultaneously, but should not allow AD and
EB.
A
B
C
D
E

13. Lecture 22: Graphs Data Structures
Using a model to solve a complicated traffic light problemUsing a model to solve a complicated traffic light problem
A
B
C
D
E
An intersection
AB & AC
AD & EB

14. Lecture 22: Graphs Data Structures
Using a model to solve a complicated traffic light problemUsing a model to solve a complicated traffic light problem
SOLUTION:
• We model the problem using a structure called graph G(V,E).
• A graph consists of a set of points called vertices, and lines
connecting the points, called edges.
•Drawing a graph such that the vertices represent turns.
• Edges between those turns that can NOT be performed
simultaneously.

15. Lecture 22: Graphs Data Structures
Using a model to solve a complicated traffic light problemUsing a model to solve a complicated traffic light problem
A
B
C
D
E
An intersection
AB AC AD
BA BC BD
DA DB DC
EA EB EC ED
Partial graph of incompatible turns

16. Lecture 22: Graphs Data Structures
Partial table of incompatible turns
Using a model to solve a complicated traffic light problemUsing a model to solve a complicated traffic light problem

17. Lecture 22: Graphs Data Structures
Using a model to solve a complicated traffic light problemUsing a model to solve a complicated traffic light problem
SOLUTION:
The graph can aid in solving our problem.
A coloring of a graph is an assignment of a color to
each vertex of the graph, so that no two vertices
connected by an edge have the same color.
Our problem is of coloring the graph of incompatible
turns using as few colors as possible.