CME1205

Discrete Computational
Structures
Lecture - 5

 Graphs
 Graphs and Graph Models
 Graph Types and Terminology

2
Graphs and Graph Models

3
What are Graphs?
General meaning in everyday math: Not

A plot or chart of numerical data using

a coordinate system.

Technical meaning in discrete

mathematics:
A particular class of discrete
structures (to be defined) that is
useful for representing relations and
has a convenient webby-looking
graphical representation.

4
Applications of Graphs

 Potentially anything (graphs can

represent relations, relations can
describe the extension of any predicate).

 Apps in networking, scheduling, flow

optimization, circuit design, path
planning.

 More apps: Geneology analysis,

computer game-playing, program
compilation, object-oriented design, …
5
 A Niche Overlap Graph.

6
 An Acquaintanceship Graph.

7
 A Graph Model of a Round-Robin
Tournament.

8
 A Precedence Graph.

9
Introduction

 What is a graph G?
 It is a pair G = (V, E),
where
 V = V(G) = set of vertices
 E = E(G) = set of edges
 Example:
 V = {s, u, v, w, x, y, z}

 E = {(x,s), (x,v) , (x,v) , (x,u),

1 2
(v,w), (s,v), (s,u), (s,w), (s,y),
(w,y), (u,y), (u,z),(y,z)}

10
Edges
 An edge may be labeled by a pair of vertices, for
instance e = (v,w).
 e is said to be incident on v and w.
 Isolated vertex = a vertex without incident edges.

11
Special edges
 Parallel edges
 Two or more edges

joining a pair of vertices

 in the example, a and b
are joined by two parallel
edges
 Loops
 An edge that starts and

ends at the same vertex

 In the example, vertex d
has a loop

12
 Simple graph
 A graph without
loops or parallel
edges.

 Weighted graph
 A graph where each
edge is assigned a
numerical label or
“weight”.

13
Directed graphs (digraphs)

G is a directed graph or
digraph if each edge
has been associated
with an ordered pair of
vertices, i.e. each
edge has a direction

14
Graph Types

15
Simple Graph
Definition. A simple graph G = (V, E)
consists of V, a nonempty set of
vertices,
and E, a set of unordered pairs of
distinct elements of V called edges.

Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles

16
 Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles

SET OF VERTICES

V = { Chicago, Denver, Detroit, Los Angeles,

New York, San Francisco, Washington }

SET OF EDGES

E = { {San Francisco, Los Angeles}, {San Francisco, Denver},

{Los Angeles, Denver}, {Denver, Chicago},
{Chicago, Detroit}, {Detroit, New York},
{New York, Washington}, {Chicago, Washington},
{Chicago, New York} }
17
 A Multigraph

THERE CAN BE MULTIPLE TELEPHONE LINES

BETWEEN TWO COMPUTERS IN THE NETWORK.

Detroit
New York

San Francisco

Chicago
Denver Washington

Los Angeles

Two edges are called multiple or parallel edges

if they connect the same two distinct vertices.

18
 A Pseudograph
THERE CAN BE TELEPHONE LINES IN THE NETWORK
FROM A COMPUTER TO ITSELF (for diagnostic use).

Detroit
New York
San Francisco

Chicago
Denver
Washington

Los Angeles
An edge is called a loop
if it connects a vertex to itself.
19
Undirected Graphs

pseudographs
multigraphs
simple graphs

20
Directed Graph
Definition. In a directed graph G = (V, E) the
edges are ordered pairs of (not necessarily
distinct) vertices.

SOME TELEPHONE LINES IN THE NETWORK

MAY OPERATE IN ONLY ONE DIRECTION .
Those that operate in two directions are represented
by pairs of edges in opposite directions.
Detroit
New York
Chicago
San Francisco

Denver Washington

Los Angeles 21
Directed Multigraph
Definition. In a directed multigraph G = (V, E) the
edges are ordered pairs of (not necessarily distinct)
vertices, and in addition there may be multiple
edges.

THERE MAY BE SEVERAL ONE-WAY LINES

IN THE SAME DIRECTION FROM ONE COMPUTER
TO ANOTHER IN THE NETWORK. Detroit
New York
Chicago
San Francisco

Denver Washington

Los Angeles
22
Types of Graphs
TYPE EDGES MULTIPLE EDGES
(SELF)LOOPS
ALLOWED?
ALLOWED?

Simple graph Undirected NO NO

Multigraph Undirected YES NO

Pseudograph Undirected YES YES

Directed graph Directed NO YES

Directed multigraph Directed YES YES

Mixed graph Directed and YES YES

Undirected

23
Types of Graphs?

Simple graph
Multigraph
Pseudograph

Directed graph
Directed multigraph
Mixed graph

24
Graph Terminology

25
Graph Terminology
 You need to learn the following terms:
 Adjacent, connects, endpoints, degree,
initial, terminal, in-degree, out-degree,
complete, cycles, wheels, n-cubes, bipartite,
subgraph, union.

26
 Adjacent Vertices (Neighbors)
Definition. 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}.
c d
b

a g f e

27
Adjacency
 LetG be an undirected graph with edge set E.
Let eE be (or map to) the pair {u,v}. Then we
say:
 u, v are adjacent / neighbors / connected.
 Edge e is incident with vertices u and v.
 Edge e connects u and v.
 Vertices u and v are endpoints of edge e.

u v
e

28
Directed Adjacency
 Let G be a directed (possibly multi-) graph,
and let e be an edge of G that is (or maps to)
(u,v). Then we say:
 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

u v
e

29
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 called isolated.

30
Degree of a vertex

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.

c d
deg( b ) = 6 deg( d ) = 1
b

deg( e ) = 0
a g f e

31
Degree of a vertex

deg( a ) = 2 deg( c ) = 4 deg( f ) = 3 deg( g ) = 4

TOTAL of degrees = 2 + 4 + 3 + 4 + 6 + 1 + 0 = 20
TOTAL NUMBER OF EDGES = 10

c d
deg( b ) = 6 deg( d ) = 1
b

deg( e ) = 0
a g f e

32
Handshaking Theorem
 Let G be an undirected (simple, multi-, or
pseudo-) graph with vertex set V and edge
set E. Then

 deg(v) 2 E
vV

 Corollary: Any undirected graph has an

even number of vertices of odd degree.

33
Directed Degree
 Let G be a directed graph, v a vertex of G.

 The in-degree of v, deg(v), is the number of edges going

to v.
 The out-degree of v, deg(v), is the number of edges
coming from v.

 The degree of v, deg(v) : deg(v) + deg(v),

is the sum of v’s in-degree and out-degree.

34
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.

35
Path of Length n

Definition 1. A path of length n from u to v in an

undirected graph is a sequence of edges
e1, e2, . . ., en of the graph such that
edge e1 has endpoints xo and x1 ,
edge e2 has endpoints x1 and x2 ,
...
and edge en has endpoints xn-1 and xn ,
where x0 = u and xn = v.

36
One path from a to e

This path passes through vertices f

b d
f and d in that order.

a e

W5

37
One path from a to a

b d
f This path passes through vertices f, d,
e, in that order. It has length 4.
a e
It is a circuit because it begins and
ends at the same vertex.
W5
It is called simple because it does not
contain the same edge more than
once.
38
Paths of Length r between Vertices

Theorem. Let G be a graph with adjacency

matrix A with respect to the ordering v1 , v2 ,
. . . , vn .
The number of different paths of length r
from vi to vj , where r is a positive integer,
equals the entry in row i and column j of Ar.

NOTE: This applies with directed or undirected

edges, with multiple edges and loops allowed.

39
Subgraphs
Definition. A subgraph of a graph G = (V, E )
is a graph H = (W, F) where W  V and F 
E.

G H

40
 C5 is a subgraph of
K5

K5 C5

41
Graph Unions
Definition. The union of 2 simple graphs G1 = ( V1 , E1 )
and G2 = ( V2 , E2 ) is the simple graph with
vertex set V = V1  V2 and edge set E = E1  E2 .
The union is denoted by G1  G2 = ( V , E )

a a


b c b c

d e d f

42
W5 is the union of S5 and C5

c b d
f

a e c
b d
f
S5
a e b d

W5 a e
C5
43
Special Types of Simple Graphs

44
Special Graph Structures
 Special cases of undirected graph structures:
 Complete graphs Kn
 Cycles Cn
 Wheels Wn
 n-Cubes Qn
 Bipartite graphs
 Complete bipartite graphs Km,n

45
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

n 1
n(n  1)
Note that Kn has  i  edges.
i 1 2
46
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

How many edges are there in Cn?

47
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 W7 W8

How many edges are there in Wn?

48
n-cubes (hypercubes)
 For any nN, the hypercube Qn is a simple
graph consisting of two copies of Qn-1
connected together at corresponding nodes.
Q0 has 1 node.

Q0 Q1 Q2 Q3 Q4

49
n-cubes (hypercubes)
 For any nN, the hypercube Qn can be defined
recursively as follows:
Q0={{v0},} (one node and no edges)

For any nN,

if Qn=(V,E), where V={v1,…,va} and E={e1,…,eb}, then
Qn+1=(V{v1´,…,va´}, E{e1´,…,eb´}{{v1,v1´},{v2,v2´},…, {va,va´}})
where v1´,…,va´ are new vertices, and where if ei={vj,vk} then ei´={vj´,vk
´}.

50
Bipartite Graphs
 Def’n.: A graph G=(V,E) is bipartite (two-
part)
iff V = V1  V2 where V1 ∩ V2= and
eE:  v1V1, v2V2 : e={v1,v2}.

 In English: The graph can

be divided into two parts
in such a way that all edges
go between the two parts.
V1 V2

51
Bipartite?

G H

52
Bipartite?

C3 C4
C5 C6

53
Complete Bipartite Graphs
 For m,n  N, the complete bipartite graph
Km,n is a bipartite graph where
|V1| = m, |V2| = n, and
E = {{v1,v2}|v1V1  v2V2}.

 That is, there are m nodes K4,3

in the left part, n nodes in
the right part, and every
node in the left part is
connected to every node Km,n has _____ nodes
in the right part.
and _____ edges.

54
Complete Bipartite Graph Examples

55
Some Applications of Special Types of Graphs
 Job Assignments
 m people, n jobs

56
Some Applications of Special Types of Graphs
 Local Area Networks

57
Representing Graphs

58
Graph Representations
 Graph representations:
 Adjacency lists
 Adjacency matrices
 Incidence matrices

59
Adjacency Lists
 A table with one row per vertex, listing its adjacent
vertices.

Adjacent
b Vertex Vertices
a
a b, c
c d b a, c, e, f
e
c a, b, f
f
d
e b
f c, b

60
61
Adjacency Matrix

A simple graph G = (V, E) with n vertices

can be represented by its adjacency matrix,
A, where entry aij in row i and column j is

1 if { vi, vj } is an edge in G,
aij =
0 otherwise.

62
Finding the adjacency matrix

c
This graph has 6 vertices
a, b, c, d, e, f. We can
b d arrange them in that order.
f

a e

W5

63
Finding the adjacency matrix

TO
c a b c d e f
FROM
a 0 1 0 0 1 1
b d
f b
c
a e
d
W5 e
f
There are edges from a to b, from a to e, and from a to f
64
Finding the adjacency matrix

TO
c a b c d e f
FROM
a 0 1 0 0 1 1
b d
f b 1 0 1 0 0 1
c
a e
d
W5 e
f
There are edges from b to a, from b to c, and from b to f
65
Finding the adjacency matrix

TO
c a b c d e f
FROM
a 0 1 0 0 1 1
b d
f b 1 0 1 0 0 1
c 0 1 0 1 0 1
a e
d 0 0 1 0 1 1
W5 e 1 0 0 1 0 1
f 1 1 1 1 1 0
Notice that this matrix is symmetric. That is aij = aji Why?
66
Adjacency matrix for a
multigraph/pseudograph

67
Multigraph/pseudograph or weighted matrix

68
Incidence Matrices

69
70
Graph Isomorphism

71
Graph Isomorphism
 Graph isomorphism:
 Two graphs are isomorphic iff they are

identical except for their node names.

72
Graph Isomorphism

 Formal definition:
 Simple graphs G1=(V1, E1) and G2=(V2, E2) are
isomorphic iff  a bijection f:V1V2 such that 
a,b V1, a and b are adjacent in G1 iff f(a) and
f(b) are adjacent in G2.

 f is the “renaming” function between the two

node sets that makes the two graphs identical.

 This definition can easily be extended to other

types of graphs.

73
Graph Invariants under Isomorphism
Necessary but not sufficient conditions for G1=(V1, E1)
to be isomorphic to G2=(V2, E2):
 We must have that |V1|=|V2|, and |E1|=|E2|.
 The number of vertices with degree n is the same in both
graphs.
 For every proper subgraph g of one graph, there is a
proper subgraph of the other graph that is isomorphic to
g.

74
Isomorphic?

75
Isomorphism Example

 If isomorphic, label the 2nd graph to show

the isomorphism, else identify difference.

b d
a b a
d c
e
e c f
f

76
Are These Isomorphic?
 If isomorphic, label the 2nd graph to show
the isomorphism, else identify difference.

• Same # of
vertices
a
b • Same # of
edges

d • Different # of
e verts of
c
degree 2!
(1 vs 3)
77