Discrete Mathematics
Graphs
Graphs are everywhere
Graph Types and Terminology: Handshaking Lemma
Graph Representation, Complement, Transpose, Subgraph
Walks, Paths and Cycles
(Strongly) Connected Graphs, k-Connected Graphs
Graphs Applications: BFS, DFS, Eulerian Graphs
Graphs Applications in Optimization
Imdadullah Khan
Imdadullah Khan (LUMS) Graphs 1 / 10
Graph Representation: Adjacency Matrix
Undirected Simple Graphs Directed Graphs (digraphs)
G = (V , E ) G = (V , E )
V is set of vertices V is set of vertices
E is set of edges E is set of edges
(unordered pairs (2-subsets) of V ) (ordered pairs of V )
a d e1
c
a
b e
f b c d
h e2
g
Imdadullah Khan (LUMS) Graphs 2 / 10
Directed Graph Representation: Adjacency Matrix
Digraph G = (V , E ) is a relation on V
We represent G with an adjacency matrix AG
Fix an arbitrary ordering of V (
1 if (vi , vj ) ∈ E
One row for each vertex in V Aij =
0 if (vi , vj ) ∈
/E
One column for each vertex in V
e1
a 0 1 1 0
1 0 0 1
A=
0
c 1 0 1
b d
e2
1 0 0 0
Imdadullah Khan (LUMS) Graphs 3 / 10
Undirected Graph Representation: Adjacency Matrix
We represent undirected G = (V , E ) with an adjacency matrix AG
Fix an arbitrary ordering of V (
1 if (vi , vj ) ∈ E
One row for each vertex in V Aij =
0 if (vi , vj ) ∈
/E
One column for each vertex in V
e
d a b c d e f g h
a 0 1 1 1 0 0 0 0
f
a b 1 0 1 0 0 0 0 0
e2 c 1 1 0 0 1 0 1 0
e1 e4 g AG = d 1 0 0 0 0 1 0 0
c e 0 0 1 0 0 1 0 0
e3 f 0 0 0 1 1 0 1 0
b g 0 0 1 0 0 1 0 1
h h 0 0 0 0 0 0 1 0
Imdadullah Khan (LUMS) Graphs 4 / 10
Graph Representation: Adjacency List
Represent digraph by listing neighbors of each vertex
a b c e
b a d
e
f g c b d
a
d a g
c d
e
b f e g
g e
Imdadullah Khan (LUMS) Graphs 5 / 10
Graph Representation: Adjacency List
Represent undirected graph by listing neighbors of each vertex
a b c d
e b a c
d
c a b e g
f
a d a f
e2
e1 e4 g
e g f
c f d e g
e3
b g c f h
h
h g
Imdadullah Khan (LUMS) Graphs 6 / 10
Weighted Graph
Some applications work on graphs with weights on edges
Weighted Graphs (digraphs)
V : Set of vertices
E : Set of edges (directed edges)
w : cost/weight function: w : E → R
weights could be lengths, airfare, toll, energy
Denoted by G = (V , E , w )
Imdadullah Khan (LUMS) Graphs 7 / 10
Weighted Graph Representation
3 4
S A B
4 8 6
5
9 8
5 3
C E F
3 3
2 12
D 14 G
Weighted Adjacency Matrix Weighted Adjacency Lists
S A B C D E F G
S A 3 C 4 D 9
S 0 3 0 4 9 0 0 0
A B 4
A 0 0 4 0 0 0 0 0
B E 6 G 8
B 0 0 0 0 0 6 0 8
.. C
C . D
D E
E
F
F
G
G
Imdadullah Khan (LUMS) Graphs 8 / 10
Graph Representation: Tradeoff
G = (V , E ), |V | = n and |E | = m
Adjacency matrix representation
requires n2 bits
Edge query (Is (a, b) ∈ E ) requires one memory lookup
Adjacency list representation
requires 2m integers (vertex ids) ∼ 2m log n bits
Edge query (Is (a, b) ∈ E ) requires list traversal
Usually real-world graphs are very sparse m = C · n log n
Adjacency lists are preferred
For dense graphs adjacency matrix is better
Imdadullah Khan (LUMS) Graphs 9 / 10
Graph Complement
Graph Complement
G = (V , E ) → G = (V , E )
(u, v ) ∈ E iff (u, v ) ∈
/E
Vertex set is the same
Each edge become non-edge and each non-edge becomes edge
(except self-loops)
a a
b c d b c d
Compute G from adjacency matrix and adjacency list representations
Imdadullah Khan (LUMS) Graphs 10 / 10