Chapter 6: Graphs

6.1 Graphs and Graph Models

Definition 1:
A graph G = (V , E ) consists of V, a nonempty set
of vertices (or nodes) and E, a set of edges. Each
edge has either one or two vertices associated with
it, called its endpoints. An edge is said to connect
its endpoints.

2
 Summary

• It is a pair G = (V, E ), where

o V = V (G ) = Set of vertices
o E = E (G ) = Set of edges

• Example:
o V = {s, u, v, w, x, y, z}
o E = {(x, s), (x, v)1, (x, v)2, (x, u), (v, w), (s, v), (s, u),
(s, w), (s, y), (w, y), (u, y), (u, z), (y, z)}
 Example
This computer network can be modeled using a graph in
which the vertices of the graph represent the data centers and
the edges represent communication links.

4
 Graphs Types

• simple graph.
• Multi - Graph
• Pseudo - graph
• Directed Graph
• Multi Directed Graph

5
 Simple Graphs

A graph in which each edge connects two different

vertices and where no more than one edge connect
the same pair of vertices is called a simple graph.
E: (undirected edges)

e.g.

6
 Multigraphs
A computer network may contain multiple links between data
centers, as shown in Figure 2. To model such networks we
need graphs that have more than one edge connecting the
same pair of vertices. Graphs that may have multiple edges
connecting the same vertices are called multigraphs.

7
 Pseudographs
Sometimes a communication link connects a data center with
itself. To model this network we need to include edges that
connect a vertex to itself. Such edges are called loops.
Graphs that may include loops, and possibly multiple
edges are sometimes called pseudographs.

8
 Directed Graphs
Definition 2: 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. When a
directed graph has no loops and has no multiple
directed edges, it is called a simple directed
graph.

9
Simple Directed Graph

10
 Directed Multigraph
Directed graphs that may have multiple directed edges from a
vertex to a second (possibly the same) vertex are to used
model such networks. We call such graphs directed
multigraphs.
12
 6.2: Graph Terminology

• Adjacent, connects, endpoints, degree, initial,

terminal, in-degree, out-degree, complete,
complete bipartite, cycles, wheels, n-cubes.

13
 Undirected Graph: Adjacency

Let G be an undirected graph with edge set E. Let e

 E where e = {u ,v}. We say that:
• The vertices u and v are adjacent / neighbors /
connected.
• The edge e connects u and v.
• The vertices u and v are endpoints of the edge e.

14
 Undirected Graph: Degree of a Vertex

• Let G be an undirected graph, v V a vertex.

• The degree of v, deg(v), is its number of incident
edges. (Except that any self-loops are counted
twice.)
• A vertex with degree 0 is isolated.

15
 Handshaking Theorem

• Let G = (V, E ) be an undirected (simple, multi- or

pseudo-) graph with e edges. Then:

 deg(v)  2 E
v V

16
 Example

How many edges are there in a graph with ten

vertices each of degree 6?

Solution:
Sum of the degrees of the vertices 6×10 = 60.
Therefore: 60 = 2|E| , |E| = 30
deg(a ) = 6
deg(b ) = 4
deg(c ) = 1 pendant
deg(d ) = 0 isolated
deg(e ) = 3
deg(f ) = 4
deg(g ) = 2
∑deg(v ) = 20 = 2 ∑edges = 2 (10)
18
 Directed Graph: Adjacency
• Let G be a directed (possibly multi-) graph, and
let e be an edge of G that is (u ,v). Then we say:
u v
– u is adjacent to v, v is adjacent from u
– e comes from u, e goes to v.
– e connects u to v, e goes from u to v
– The initial vertex of e is u
– The terminal vertex of e is v

19
 Directed Graph: Degree of a vertex

• Let G be a directed graph and v a vertex of G.

• The in-degree of v, deg(v), is the number of
edges going to v (v is terminal).
• The out-degree of v, deg(v), is the number of
edges coming from v (v is initial).
• The degree of v, deg(v) = deg(v) + deg(v), is the
sum of v’s in-degree and out-degree.
• A loop at a vertex contributes 1 to both in-degree
and out-degree of this vertex.

20
 Directed Handshaking Theorem

• Let G be a directed (possibly multi-) graph with

vertex set V and edge set E. Then:
1

v V
deg (v)   deg (v)   deg(v)  E


v V


2 v V
• Note that the degree of a node is unchanged by
whether we consider its edges to be directed or
undirected.

21
• deg+(a ) = 3 deg - (a ) = 3
• deg+(b ) = 3 deg - (b ) = 1
• deg+(c ) = 0 deg - (c ) = 1
• deg+(d ) = 0 deg - (d ) = 0
• Deg+(e ) = 1 deg - (e ) = 2
• Deg+(f ) = 2 deg - (f ) = 2
• Deg+(g ) = 1 deg - (g ) = 1

∑deg+ (v ) = ∑deg - (v ) = 1/2 ∑deg(v ) = ∑edges = 10

22
 Special Graph Structures

Special cases of undirected graph structures:

• Complete graphs: Kn
• Complete bipartite graphs: Km,n
• Cycles: Cn
• Wheels: Wn

23
 Complete Graphs
• For any n  N, a complete graph on n vertices,
Kn , is a simple graph with n nodes in which every
node is adjacent to every other node:
u , v V : u  v  {u , v}  E.

K1 K2 K3 K4
K5 K6
Note that Kn has n vertices and n(n  1) edges.
2
 Complete Bipartite Graphs
• The complete bipartite graph Km,n is the graph
that has its vertex set partitioned into two subsets
of m and n vertices such that there is an edge
between vertices if and only if one vertix in the
first set and the other vertix in the second set.

K2,3 K3,5
Note that Km,n has m+n vertices and mn edges.
 Cycles

• For any n  3, a cycle on n vertices, Cn , is a

simple graph where V = {v1,v2, … ,vn} and
E = {{v1, v2}, {v2, v3}, …, {vn1, vn}, {vn , v1}}.

C3 C4 C5 C6 C8
C7
Note that Cn has n vertices and n edges.

26
 Wheels
• For any n  3, a wheel Wn , is a simple graph
obtained by taking the cycle Cn and adding one
extra vertex vhub and n extra edges {{vhub, v1}, {vhub,
v2}, …, {vhub, vn}}.

W3 W4 W5 W6 W7edges.W8
Note that Wn has n+1 vertices and 2n

27
 6.3 Graph Representations

• Graph representations:
– Adjacency Lists.
– Adjacency Matrices.

28
 Undirected: Adjacency Lists
• A table with 1 row per vertex, listing its adjacent
vertices.
Adjacent
a b Vertex
Vertices
d a b, c
c e b a, c, e, f
f c a, b, f
d
e b
f c, b

29
 Undirected: Adjacency Matrices
• Matrix A = [aij], where aij is 1 if {vi ,vj } is an edge
of G, 0 otherwise.

a b a b c d e
a 0 1 1 0 0
c e b1 0 1 0 1

d
c 1 1 0 0 0
 
d 0 0 0 0 0
e 
0 1 0 0 0


30
 Example 1

Draw a graph using the following adjacency matrix A

with respect to the vertices: a, b, c, d :

1 1 1 0 a b
1 0 0 1
A 
1 0 0 1
 
0 1 1 0
d c

31
 Example 2

Find an adjacency matrix that represents the graph:

a b c d
a b a 0 3 0 2
3 0 1 1 
b 
c 0 1 1 2
 
d c d 2 1 2 0

32
 Example 3
Let A be the adjacency matrix of a graph G with vertices a, b, c,
d . Find the degrees of the vertices of G.

0 1 1 1 
1 0 1 0
A 
1 1 0 0
 vertices a, b,c and d of G are 3, 2, 2
Answer: The degrees of the
1 0 0 0
and 1, respectively.

33
 Directed Adjacency Lists
• 1 row per node, listing the terminal nodes of each
edge incident from that node.
Initial Terminal
vertex vertices
V1 V2, V4, V5
V2 V4

V3 V5

V4
V5 V2

34
 Directed Adjacency Matrices

• Matrix A = [aij], where aij is 1 if {vi ,vj } is an edge

of G, 0 otherwise.

a b a b c d e
c a 0 1 1 0 0
e b 0 0 0 0 0
d
c 0 1 0 0 0
d 0 0 0 0 0
e 
0 1 0 0 0

35
 6.4 Connectivity

• In an undirected graph, a path of length n from u

to v is a sequence of adjacent edges going from
vertex u to vertex v.
• A path is a circuit if u = v.
• A path traverses the vertices along it.
• A path is simple if it contains no edge more than
once.

36
Example:

• Simple path: a, d, c, f, e
The edges are {a, d }, {d, c}, {c, f }, {f, e}
Length = 4
• Circuit: b, c, f, e, b
The edges are {b, c},{c, f }, {f, e},{e, b}
Length = 4
• Not a path : d, e, c, a because {e, c} is not an edge
• Not a simple path: a, b, e, d, a, b because {a, b} appears
twice
Length = 5
37
 Paths in Directed Graphs

• Same as in undirected graphs, but the path must go

in the direction of the arrows.
e.g. Simple path a, b, c
a

b d

38
 Undirected Graphs: Connectedness

• An undirected graph is called connected if there is

a path between every pair of distinct vertices of
the graph.
e.g.
a b e a b c
c d d e
Connected Not connected
(No path between a and c)

39
Directed Graphs: Connectedness
• Definition 1:
A directed graph is strongly connected if there is
a path from a to b and from b to a whenever a and
b are vertices in the graph.
• Definition 2:
A directed graph is weakly connected if there is a
path between every two vertices

40
 Example

a b a b

c d c d

Strongly connected weakly connected

(No directed path from a to b)

41
 9.6 Shortest-Path Problems

Many problems can be modeled using graphs with weights

assigned to their edges. As an illustration, consider how an
airline system can be modeled. We set up the basic graph
model by representing cities by vertices and flights by
edges. Problems involving distances can be modeled by
assigning distances between cities to the edges. Problems
involving flight time can be modeled by assigning flight
times to edges. Problems involving fares can be modeled
by assigning fares to the edges. Graphs that have a number
assigned to each edge are called weighted graphs.

42
 Example

Flight mileage

43
 Example
Flight times
 Example
Flight Fares
 Example
Shortest path, is a path of least length, between two given
vertices
What is the shortest path from a to z in the figure ?

Path length
abcz 4+3+2=9
abez 4+3+1=8
adez 2+3+1=6 (the shortest path)