Introduction to Graphs (Part-I)

Srikrishnan Divakaran
School of Engineering and Applied Sciences
Ahmedabad University
Lecture Set 11
 9.1: What are Graphs? Not
• Everyday Math:
• A plot or chart of numerical data using a
coordinate system.
• 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.
05/26/20 2
 What is a graph?
A set of points and lines joining these
points.
Formally:
e6
G=(V,E), V-vertices, E-edges
v1

v3
v4
V2 and v3 are
e1 adjacent. e2 is incident
e2 e3 with v2.
e5
v2
v5
e4

3
 Types of Graphs:
1. Simple Graphs

Visual Representation
• A simple graph G=(V,E) of a Simple Graph
consists of:
– a set V of vertices or nodes
– a set E of edges / arcs / links: unordered pairs
of [distinct?] elements u,v  V

05/26/20 4
 2. Multigraphs

• Like simple graphs, but there may be more

than one edge connecting two given nodes.
• A multigraph G=(V, E, f ) consists of a set V
of vertices, a set E of edges (as primitive
objects), and a function
Parallel
f:E{{u,v}|u,vV  uv}. edges
• E.g., nodes are cities, edges
are segments of major highways.
05/26/20 5
 3. Pseudographs
• Like a multigraph, but edges connecting a
node to itself are allowed.
• A pseudograph G=(V, E, f ) where
f:E{{u,v}|u,vV}. Edge eE is a loop if
f(e)={u,u}={u}.
• E.g., nodes are campsites
in a state park, edges are
hiking trails through the woods.

05/26/20 6
 Directed Graphs
• Correspond to arbitrary binary relations R,
which need not be symmetric.
• A directed graph (V,E) consists of a set of
vertices V and a binary relation E on V.
• E.g.: V = people,
E={(x,y) | x loves y}

05/26/20 7
Directed Multigraphs

• Like directed graphs, but there may be

more than one arc from a node to
another.
• A directed multigraph G=(V, E, f )
consists of a set V of vertices, a set E of
edges, and a function f:EVV.
• E.g., V=web pages,
E=hyperlinks. The WWW is
a directed multigraph...
05/26/20 8
 Types of Graphs: Summary
• Summary of the book’s definitions.
• Keep in mind this terminology is not fully
standardized...
Edge Multiple Self-
Term type edges ok? loops ok?
Simple graph Undir. No No
Multigraph Undir. Yes No
Pseudograph Undir. Yes Yes
Directed graph Directed No Yes
Directed multigraph Directed Yes Yes

05/26/20 9
 Graphs as models
• Networks: transportation, roadmaps, computer,
electrical, etc.

10
Graphs as models

11
 Matching Problem
women men
w1 m1

w2 m2

w3 m3

w4 m4

w5 m5

12
Matching Problem
women men

w1 m1

w2 m2

w3 m3

w4 m4

w5 m5

Is this a maximum matching?

13
Assignment Problem
workers machines

w1 1 m1
3
1
w2 2 m2
1.5
2
w3 2 m3

1.7 4
w4 m4
3
2
w5 m5

Find a minimum (maximum) cost

assignment of workers to machines 14
Stable Marriage Problem
women men

w1 1 m1
1
1 Does there exist a
w2 2 m2 stable marriage?
1.5
2
w3 2 m3

1.7 4
w4 m4
3
2
w5 m5

W2 prefers m5 to her spouse and m5 15

prefers w2 to his spouse.
 Timetabling problems
• m teachers, n classes.
T1 C1
• Teacher i is required to
teach class j for Pij periods. T2 C2
• In a given period a teacher
can be in at most 1 class, C3
and a class can have at
most 1 teacher.
• Design a timetable with
minimum no. of periods. Cn

• Tractable! Tm

16
 Connector problem
• Design a railway network
connecting a number of
cities, with a minimum
possible construction cost.
• Or electrical network,
cable TV, gas, etc.

17
 Chinese Postman Problem
• A postman begins in P.O.

the post office, has to

traverse all the
streets, and returns to
the post office in a
shortest possible
distance.

18
 Chinese Postman Problem
• A postman begins in P.O.

the post office, has to

traverse all the
streets, and returns to
the post office in a
shortest possible
distance.
• Tractable!

19
 Chinese Postman Problem-
graph theory
• Definition: an Euler tour P.O.

is a closed walk that

traverses all the edges in
the graph.
• Problem: Does a graph
have an Euler tour?
• Easy problem…
• Problem: Find a
minimum Chinese
Postman Tour.
• Tractable… 20
Travelling salesman problem
Delhi

Intractabl
e!
Mumbai Hyderabad

Bangalore Chennai

Madurai

A salesperson begins in Bangalore, has to visit all the

cities, and return to Bangalore in a shortest possible
distance. (or time, or cost) 21
 Vehicle Routing
• Need to transport n children to m
bus stops across the city.
• There are k buses, each bus j has
capacity cj. Each km has a cost.
(time).
• Problem: Route the buses s.t. the
total cost (or time) is minimized.
• Difficult – intractable problem!

22
 9.2: Graph Terminology
• Adjacent, connects, endpoints, degree,
initial, terminal, in-degree, out-degree,
complete, cycles, wheels, n-cubes,
bipartite, subgraph, union.

05/26/20 23
 9.2: Graph Terminology
• Adjacent, connects, endpoints, degree,
initial, terminal, in-degree, out-degree,
complete, cycles, wheels, n-cubes,
bipartite, subgraph, union.

05/26/20 24
 Adjacency
Let G 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.

05/26/20 25
 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.
• A vertex of degree 1 is pendant.

05/26/20 26
 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.

05/26/20 27
 • 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 x 10
05/26/20 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

05/26/20 29
 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.

05/26/20 30
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.

05/26/20 31
 • 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
05/26/20 32
 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

05/26/20 33
 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 `
n(n  1)
Note that Kn has i  edges.
i 1 2
05/26/20 34
 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
C7 C8

How many edges are there in Cn?

05/26/20 35
 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?

05/26/20 36
 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 Q4
Q3

Number of vertices: 2n. Number of edges:Exercise to try!

05/26/20 37
 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´}.

05/26/20 38
 9.3: Graph Representations
• Graph representations:
– Adjacency lists.
– Adjacency matrices.
– Incidence matrices.

05/26/20 39
 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

05/26/20 40
 Directed Adjacency Lists
• 1 row per node, listing the terminal nodes
of each edge incident from that node.

05/26/20 41
 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
d b 1 0 1 0 1
c 1 1 0 0 0
d 0 0 0 0 0
e 
0 1 0 0 0


05/26/20 42