Graphs

Use of Graphs

• Graphs can be used to model many types of relations and processes in

physical, biological, social and information systems.
• In computer science-
✓ graphs are used to represent networks of communication, data
organization, computational devices, the flow of computation, etc.
✓For instance, the link structure of a website can be represented by a
directed graph, in which the vertices represent web pages and directed
edges represent links from one page to another.

• This course we focus more on the properties of abstract graphs rather

on algorithms.
 Graphs

• Graphs is special discrete data structure, which we can represent through

two sets-
• Set of Vertices / Nodes - V
1 1
Rajshahi 22
DHK
• Set of Edges - E

• Let,
• V = {1, 2, 3, 4}
• E = {(1,2), (2,3), (1,4)} 33
Khulna 4CTG
4
 Graphs
• A graph is a bunch of vertices (or nodes) represented by circles which
are connected by edges, represented by line segments
 Graphs

Definition

A graph G = (V , E) consists of V, a nonempty set of vertices (or nodes)

and E, a set of edges (possibly empty).
Each edge has either one or two vertices associated with it, called its
end points.
An edge is said to connect its endpoints.
 Graphs Example
{1,2}
1 2

{1,3} {2,3} {2,4}

{3,4}
3 4

{1,4}

SET OF VERTICES

V = { 1, 2, 3, 4 }
SET OF EDGES
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (1, 4) }
L23 6
 Simple Graphs

Definition
A graph in which each edge connects two different vertices and where
no two edges connect the same pair of vertices is called a simple graph.

Dhaka Raj

Bangkok NY
 Multi-graphs

Definition
Graphs that may have multiple edges connecting the same vertices are
called multigraphs.

Dhaka Raj

Bangkok NY
 Undirected Graphs

Dhaka
Raj

Bangkok NY
 Pseudo graphs
Definition
Edges that connect a vertex to itself are called loops. A graph with loop
(self-loop) is called pseudo graph.

Dhaka
Raj

Bangkok NY
 Directed Graphs

• Dhaka to Rajshahi
• Dhaka to Chapai
• Rajshahi to Dhaka
• No Chapai to Dhaka, but Chapai to Rajshahi

Dhaka
Rajshahi

Chapai
 A Directed Graph

Definition
A directed graph (or digraph) (V, E) consists of a nonempty set of vertices V
and a set of directed edges (or arcs) E. Each directed edge is associated with
an ordered pair of vertices. The directed edge associated with the ordered
pair (u, v) is said to start at u and end at v.

The edge (a,b) is also denoted by a →b

• a is called the source of the edge while
• b is called the target of the edge.
 Directed Graphs

• Simple Directed Graphs

• Multiple Directed Graphs

• Mixed Graphs
Types of Graphs
 Undirected Graphs: Adjacent
Definition
Vertices are adjacent if they are the endpoints of the same edge or they
are connected by the same edge.

1 2
Adjacent of 1 : 2 and 4

Adjacent of 2 : 1 and 3

Adjacent of 3 : 2 3 4
Undirected Graphs Terminology
Adjacent Vertices (Neighbors)

Definition 1. Two vertices, u and v in an undirected graph G are

called adjacent (or neighbors) in G, if {u, v} is an edge of G.

An edge e connecting u and v is called incident with vertices u and

v, or is said to connect u and v. The vertices u and v are called
endpoints of edge {u, v}.

16
 Undirected Graphs
Terminology
e1
1 e2 2

e3 e4 e5
3 e6 4

A: 1 is adjacent to 2 and 3
2 is adjacent to 1 and 3
3 is adjacent to 1 and 2
4 is not adjacent to any vertex

L23 17
 Undirected Graphs
Terminology

A vertex is incident with an edge (and the edge is

incident with the vertex) if it is the endpoint of the edge.

e1
1 e2 2

e3 e4 e5
3 e6 4

Q: Which edges are incident to 1? How about incident

to 2, 3, and 4?
L23 18
 Undirected Graphs
Terminology
e1
1 e2 2

e3 e4 e5
3 e6 4

A: e1, e2, e3, e6 are incident with 1

2 is incident with e1, e2, e4, e5, e6
3 is incident with e3, e4, e5
4 is not incident with any edge

L23 19
 Undirected Graphs: Degree
Definition
The degree of a vertex in an undirected graph is the number of edges incident with
it, except that a loop at a vertex contributes twice to the degree of that vertex. The
degree of the vertex v is denoted by deg(v).

1 2
deg (1) : 2

deg (3) : 1

deg (4) : 3 3 4
 Directed Graphs : Adjacent
Definition

1 2
Adjacent of 1 : 2 and 4

Adjacent of 2 : 1 and 3

Adjacent of 3 : 2 3 4
 Directed Graphs : Degree

1 2

In degree :

Out degree:
3 4
 Directed Graphs : Degree
Definition
 Oriented Degree
when Edges Directed
The in-degree of a vertex (deg-) counts the number of edges
that stick in to the vertex.
The out-degree (deg+) counts the number sticking out.

1 3

Q: What are in-degrees and out-degrees of all the vertices?

L23 24
 Oriented Degree
when Edges Directed
A: deg-(1) = 0
deg-(2) = 3
deg-(3) = 4 2
deg+(1) = 2
1 3
deg+(2) = 3
deg+(3) = 2

L23 25
Any Questions?