Discrete Mathematics

Introduction to Graphs
Chapter 8- Rosen
Chapter 8,9- Schaum’s Outlines
 What is Graph?
• A graph G = (V, E) consists of a set of objects
V = {v1, v2, …} called vertices, and another set
E = {e1, e2, …}, whose elements are called
edges, such that each edge ek is identified with
an unordered pair (v1, v2) of vertices.
• Suppose G = (V, E) is a graph where V1 V4
• V = {v1, v2, v3, v4}
• E = {(v1, v2), (v2, v3), (v3, v1), (v3, v4)}
V2 V3
 Applications
7 88
88
77
22 9 1
1 66
9

11 33
5
5 22 33
99 66
2
55 44
44
 Applications
• Scheduling
 Applications
• Job assignments

People

Jobs
The House-and-Utilities Problem
 Applications
• Utilities Problem

H1 H2 H3

W G E
 Simple Graph Example

Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles

• This simple graph represents a network.

• The network is made up of computers and
telephone links between computers
 Multigraph
• A multigraph can have multiple edges (two or
more edges connecting the same pair of
vertices).
Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles

There can be multiple telephone lines between two

computers in the network.
 Pseudograph
• A Pseudograph can have multiple edges and
loops (an edge connecting a vertex to itself).
Detroit

San Francisco Chicago New York

Denver

Washington

Los Angeles There can be telephone lines in the network from

a computer to itself.
 Types of Undirected Graphs

Pseudographs
Multigraphs
Simple Graphs
 Directed Graph
The edges are ordered pairs of (not necessarily
distinct) vertices.
Detroit
Chicago New York
San Francisco

Denver Washington

Los Angeles

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.
 Directed Multigraph
A directed multigraph is a directed graph with multiple
edges between the same two distinct vertices.

Detroit
New York
Chicago
San Francisco

Denver Washington

Los Angeles

There may be several one-way lines in the same direction

from one computer to another in the network.
 Types of Directed Graphs

Directed
Multigraphs
Directed Graphs
 Graph Models

• Graphs can be used to model structures,

sequences, and other relationships.
• Example: ecological niche overlay graph
– Species are represented by vertices
– If two species compete for food, they are
connected by a vertex
Niche Overlay Graph
Acquaintanceship Graph
Influence Graph
Round-Robin Tournament Graph
 Call Graphs

Directed graph (a) represents calls from a telephone number

to another.
Undirected graph (b) represents called between two
numbers.
Precedence Graphs

In concurrent
processing,
some statements
must be
executed before
other statements.
A precedence
graph represents
these
relationships.
 Hollywood Graph

• In the Hollywood graph:

– Vertices represent actors
– Edges represent the fact that the two
actors have worked together on some
movie
• As of October 2007, this graph had 893,283
vertices, and over 20 million edges.
 Summary

Type Edges Loops Multiple

Edges
Simple Graph Undirected NO NO

Multigraph Undirected NO YES

Pseudograph Undirected YES YES

Directed Directed YES NO

Graph
 CSE 211
Discrete Mathematics

Chapter 8.2
Graph Terminology
 Graph Terminology
• Finite Graph:
• Finite number of vertices had finite number of edges

• Trivial Graph:
– The finite graph with one vertex and no edge
 Adjacent Vertices in Undirected
Graphs
• 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}.
 Degree of a Vertex

• 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 a vertex v is denoted by deg(v).
 Example
c d
b

a g f e

• Find the degrees of all the vertices:

deg(a) = 2, deg(b) = 6, deg(c) = 4, deg(d) = 1,
deg(e) = 0, deg(f) = 3, deg(g) = 4
Adjacent Vertices in Directed Graphs

When (u,v) is an edge of a directed graph G,

u is said to be adjacent to v and v is said to
be adjacent from u.

(u, v)

initial vertex terminal vertex

 Degree of a Vertex
• In-degree of a vertex v
– The number of vertices adjacent to v (the number of
edges with v as their terminal vertex
– Denoted by deg(v)
• Out-degree of a vertex v
– The number of vertices adjacent from v (the number
of edges with v as their initial vertex)
– Denoted by deg+(v)
• A loop at a vertex contributes 1 to both the in-
degree and out-degree.
Example
 Example
a c
b

e d f
Find the in-degrees and out-degrees of this digraph.
In-degrees: deg-(a) = 2, deg-(b) = 2, deg-(c) = 3,
deg-(d) = 2, deg-(e) = 3, deg-(f) = 0
Out-degrees: deg+(a) = 4, deg+(b) = 1, deg+(c) = 2,
deg+(d) = 2, deg+(e) = 3, deg+(f) = 0
 Handshaking Theorem
In an undirected graph
1
| E |   deg( e)
2 eE
An undirected graph has an even number of
vertices of odd degree:

2| E |   deg()   deg()
eV eV 1
  deg()
eV 2
 Handshaking Theorem
c d
b

a g f e
• Find the degrees of all the vertices:
deg(a) = 2, deg(b) = 6, deg(c) = 4, deg(d) = 1,
deg(e) = 0, deg(f) = 3, deg(g) = 4
So (2+6+4+1+0+3+4)/2=20/2=10
 Theorem 3
• The sum of the in-degrees of all vertices in
a digraph = the sum of the out-degrees =
the number of edges.
• Let G = (V, E) be a graph with directed
edges. Then:

 deg v    deg v   E
vV


vV

 Complete Graph

• The complete graph on n vertices (Kn) is the

simple graph that contains exactly one edge
between each pair of distinct vertices.
• The figures above represent the complete graphs,
Kn, for n = 1, 2, 3, 4, 5, and 6.
 Cycle
• The cycle Cn (n  3), consists of n vertices
v1, v2, …, vn and edges {v1,v2}, {v2,v3}, …,
{vn-1,vn}, and {vn,v1}.

Cycles: C3 C4 C5 C6
 Wheel
When a new vertex is added to a cycle Cn and
this new vertex is connected to each of the n
vertices in Cn, we obtain a wheel Wn.

Wheels: W3 W4 W5 W6
 Bipartite Graph
A simple graph is called bipartite if its vertex set V
can be partitioned into two disjoint nonempty sets
V1 and V2 such that every edge in the graph
connects a vertex in V1 and a vertex in V2 (so that
no edge in G connects either two vertices in V1 or
two vertices in V2).
a b a
b
c d d
c
e e
 Graph Theoretic Foundations
• Bipartite Graph
 Graph Theoretic Foundations
• Bipartite Graph
• Complete bipartite graph
 Bipartite Graph (Example)
1 2

Is C6 Bipartite?
6 3

Yes. Why? 5 4
Because:
• its vertex set can be partitioned into the two
sets V1 = {v1, v3, v5} and V2 = {v2, v4, v6}
• every edge of C6 connects a vertex in V1
with a vertex in V2
 Bipartite Graph (Example)
1

Is K3 Bipartite?
No. Why not?
2 3
Because:
• Each vertex in K3 is connected to every other
vertex by an edge
• If we divide the vertex set of K3 into two disjoint
sets, one set must contain two vertices
• These two vertices are connected by an edge
• But this can’t be the case if the graph is bipartite
 Graph Theoretic Foundations
• Subgraphs

Spanning subgraph of G; since V’ =

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

K5 C5
Is C5 a subgraph of K5?
 Union
• 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.
c c c

b d b f
f b d d

a e a e a e
S5 C5 W5
S5  C5 = W5
 CSE 211
Discrete Mathematics

Chapter 8.3
Representing Graphs and
Graph Isomorphism
 §8.3: Graph Representations &
Isomorphism
• Graph representations:
– Adjacency lists.
– Adjacency matrices.
– Incidence matrices.
• Graph isomorphism:
– Two graphs are isomorphic iff they are identical
except for their node names.
 Adjacency Lists
• A table with 1 row per vertex, listing its
adjacent vertices.
Adjacent
a b Vertex Vertices
a b, c
c d
e b a, c, e, f
f c a, b, f
d
e b
f c, b
 Directed Adjacency Lists
• 1 row per node, listing the terminal nodes of
each edge incident from that node.
0 1
node Terminal nodes
0 3
1 0, 2, 4
2 1

3 3
2 4
4 0,2
 Adjacency Matrix
• A simple graph G = (V,E) with n vertices
can be represented by its adjacency matrix,
A, where the entry aij in row i and column j
is:
1 if { vi ,v j } is an edge in G
aij  
0 otherwise
 Adjacency Matrix Example

c
To
a b c d e f
b d From
f a 0 1 0 0 1 1
b 1 0 1 0 0 1
a e c 0 1 0 1 0 1
d 0 0 1 0 1 1
W5 e 1 0 0 1 0 1
f 1 1 1 1 1 0
{v1,v2}
row column
 Adjacency Matrices
• Matrix A=[aij], where aij is 1 if {vi, vj} is an
edge of G, 0 otherwise.

a
a b c d
b a 0 1 1 1

b 1

0 1 0
d 
c 1 1 0 0
c
 
d 1 0 0 0
Adjacency Matrices for pseudo graph
• Matrix A=[aij], where aij is the number of
edges that are associated to {vi, vj}
a b c d
a
b
a 0 3 0 2

b 3

0 1 1

c 0 1 1 2
c  
d d 2 1 2 0
 Incidence Matrix
• Let G = (V,E) be an undirected graph.
Suppose v1,v2,v3,…,vn are the vertices and
e1,e2,e3,…,em are the edges of G. The
incidence matrix w.r.t. this ordering of V
and E is the nm matrix M = [mij], where
1 if edge e j is incident with vi
mij  
0 otherwise
 Incidence Matrix Example
• Represent the graph shown with an
incidence matrix.

e1 e2 e3 e4 e5 e6 edges
v1 v2 v3
e6 v11 1 0 0 0 0
e3 v02 0 1 1 0 1
e1 e4
e5 v03 0 0 0 1 1
e2
v14 0 1 0 0 0
v4 v5
v05 1 0 1 1 0

vertices
 Incidence matrices
• Matrix M=[mij], where mij is 1 when edge ej
is incident with vi, 0 otherwise
v1 e2 e1 e2 e3 e4 e5
e3 v4
v1 1 1 1 0 0
e1 e4
0 
0 1 1 0
v2
e5 v2 
v3 1 0 0 0 1
 
v3

v4 0 1 0 1 1
 Isomorphism

• Two simple graphs are isomorphic if:

– there is a one-to one correspondence
between the vertices of the two graphs
– the adjacency relationship is preserved
 Isomorphism (Cont.)

• The simple graphs G1=(V1,E1) and

G2=(V2,E2) are isomorphic if there is a
one-to-one and onto function f from V1 to
V2 with the property that a and b are
adjacent in G1 iff f(a) and f(b) are
adjacent in G2, for all a and b in V1.
 Example

u1 u2 v1 v2

u3 u4 v3 v4
G H

Are G and H isomorphic?

f(u1) = v1, f(u2) = v4, f(u3) = v3, f(u4) = v2
 Isomorphism Example

• If isomorphic, label the 2nd graph to show

the isomorphism, else identify difference.
d
b
a b a
d c

e
e c f
f
 Are These Isomorphic?
• If isomorphic, label the 2nd graph to show the
isomorphism, else identify difference.

* Same # of
a
vertices
b
* Same # of
edges

d
* Different
c e # of vertices of
degree 2!
(1 vs 3)
Example 11: a more general solution
 Invariants
• Invariants – properties that two simple
graphs must have in common to be
isomorphic
– Same number of vertices
– Same number of edges
– Degrees of corresponding vertices are the same
– If one is bipartite, the other must be; if one is
complete, the other must be; and others …
 Example

b b

a c a c

e d e d
G H

Are G and H isomorphic?

 Example
• Are these two graphs isomorphic?
u1 u2 v1 v2
v5
v3
u5 u3
u4 v4
G H
– They both have 5 vertices
– They both have 8 edges
– They have the same number of vertices with
the same degrees: 2, 3, 3, 4, 4.
 Example (Cont.)
G H H  G?
u1 u2 u3 u4 u5 v1 v2 v3 v4 v5 v1 v3 v2 v5 v4
u1 0 1 0 1 1 v1 0 0 1 1 1 v1
u2 1 0 1 1 1 v2 0 0 1 0 1 v3
u3 0 1 0 1 0 v3 1 1 0 1 1 v2
u4 1 1 1 0 1 v4 1 0 1 0 1 v5
u5 1 1 0 1 0 v5 1 1 1 1 0 v4

– G and H don’t appear to be isomorphic.

– However, we haven’t tried mapping vertices from
G onto H yet.
 Example (Cont.)
• Start with the vertices of degree 2 since each
graph only has one:
deg(u3) = deg(v2) = 2 therefore f(u3) = v2
 Example (Cont.)
• Now consider vertices of degree 3
deg(u1) = deg(u5) = deg(v1) = deg(v4) = 3
therefore we must have either one of
f(u1) = v1 and f(u5) = v4
f(u1) = v4 and f(u5) = v1
 Example (Cont.)
• Now try vertices of degree 4:
deg(u2) = deg(u4) = deg(v3) = deg(v5) = 4
therefore we must have one of:
f(u2) = v3 and f(u4) = v5 or
f(u2) = v5 and f(u4) = v3
 Example (Cont.)
• There are four possibilities (this can get messy!)
f(u1) = v1, f(u2) = v3, f(u3) = v2, f(u4) = v5, f(u5) = v4
f(u1) = v4, f(u2) = v3, f(u3) = v2, f(u4) = v5, f(u5) = v1
f(u1) = v1, f(u2) = v5, f(u3) = v2, f(u4) = v3, f(u5) = v4
f(u1) = v4, f(u2) = v5, f(u3) = v2, f(u4) = v3, f(u5) = v1
 Example (Cont.)
G H H’
u1 u2 u3 u4 u5 v1 v2 v3 v4 v5 v1 v3 v2 v5 v4
u1 0 1 0 1 1 v1 0 0 1 1 1 v1 0 1 0 1 1
u2 1 0 1 1 1 v2 0 0 1 0 1 v3 1 0 1 1 1
u3 0 1 0 1 0 v3 1 1 0 1 1 v2 0 1 0 1 0
u4 1 1 1 0 1 v4 1 0 1 0 1 v5 1 1 1 0 1
u5 1 1 0 1 0 v5 1 1 1 1 0 v4 1 1 0 1 0
We permute the adjacency matrix of H (per function choices
above) to see if we get the adjacency of G. Let’s try:
f(u1) = v1, f(u2) = v3, f(u3) = v2, f(u4) = v5, f(u5) = v4
Does G = H’? Yes!
 Example (Cont.)
G H H’
u1 u2 u3 u4 u5 v1 v2 v3 v4 v5 v4 v3 v2 v5 v1
u1 0 1 0 1 1 v1 0 0 1 1 1 v4 0 1 0 1 1
u2 1 0 1 1 1 v2 0 0 1 0 1 v3 1 0 1 1 1
u3 0 1 0 1 0 v3 1 1 0 1 1 v2 0 1 0 1 0
u4 1 1 1 0 1 v4 1 0 1 0 1 v5 1 1 1 0 1
u5 1 1 0 1 0 v5 1 1 1 1 0 v1 1 1 0 1 0

It turns out that

f(u1) = v4, f(u2) = v3, f(u3) = v2, f(u4) = v5, f(u5) = v1
also works.