1

CSC102: Discrete Structure

Credit Hours: 3(3,0)
Lecture #: 25, 26
Unit # 6

Instructor:
MISHAL IQBAL

COMSATS University Islamabad

Vehari Campus
 2

Topic
Graph & basic graph terminologies
Special Types of Graphs
Bipartite Graph
Application of Graph
Representing Graphs
Adjacency Lists
Adjacency & Incidence Matrices
Isomorphism of Graphs
 3

Graphs Graph’s Definition

 Remark: The set of vertices V of a graph G may be infinite. A graph

with an infinite vertex set or an infinite number of edges is called an
infinite graph, and in comparison, a graph with a finite vertex set and a
finite edge set is called a finite graph.
 4

Graphs Graph’s Definition

 Now suppose that a network is made up of data centers and
communication links between computers.
 We can represent the location of each data center by a point and each
communications link by a line segment.
 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.
 5

Graphs Graph’s Definition

 In general, we visualize graphs by using points to represent vertices and
line segments, possibly curved, to represent edges, where the endpoints
of a line segment representing an edge are the points representing the
endpoints of the edge.
 When we draw a graph, we generally try to draw edges so that they do
not cross. However, this is not necessary because any depiction using
points to represent vertices and any form of connection between vertices
can be used. Indeed, there are some graphs that cannot be drawn in the
plane without edges crossing.
 The key point is that the way we draw a graph is arbitrary, as long as the
correct connections between vertices are depicted.
 6

Graphs Simple Graph

 A graph in which each edge connects two different vertices and where no
two edges connect the same pair of vertices is called a simple graph.
 Note that in a simple graph, each edge is associated to an unordered pair
of vertices, and no other edge is associated to this same edge.
 Consequently, when there is an edge of a simple graph associated to
{u, v}, we can also say, without possible confusion, that {u, v} is an edge
of the graph.
 7

Graphs Multigraph
 A computer network may contain multiple links between data centers, as
shown in Figure.
 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.
 When there are m different edges associated to the same unordered pair
of vertices {u, v}, we also say that {u, v} is an edge of multiplicity m.
That is, we can think of this set of edges as m different copies of an edge
{u, v}.
 8
Loops & Pseudo-
Graphs graphs
 Sometimes a communications link connects a data center with itself,
perhaps a feedback loop for diagnostic purposes. Such a network is
illustrated in Figure.
 To model this network we need to include edges that connect a vertex to
itself. Such edges are called loops, and sometimes we may even have
more than one loop at a vertex.
 Graphs that may include loops, and possibly multiple edges connecting
the same pair of vertices or a vertex to itself, are sometimes called
pseudographs.
 9

Graphs Directed Graphs

 The graphs we have introduced are undirected graphs. Their edges are
also said to be undirected.
 However, to construct a graph model, we may find it necessary to assign
directions to the edges of a graph. E.g., in a computer network, some
links may operate in only one direction (such links are called single
duplex lines).
 This may be the case if there is a large amount of traffic sent to some
data centers, with little or no traffic going in the opposite direction. Such
a network is shown in Figure.
 10

Graphs Directed Graphs

 To model such a computer network we use a directed graph.
 Note that we obtain a directed graph when we assign a direction to each
edge in an undirected graph.
 Each edge of a directed graph is associated to an ordered pair.
 The definition of directed graph we give here is more general.

 When we depict a directed graph with a line drawing, we use an arrow

pointing from u to v to indicate the direction of an edge that starts at u
and ends at v.
 11
Simple Directed
Graphs Graphs

 A directed graph may contain loops and it may contain multiple directed
edges that start and end at the same vertices.
 When a directed graph has no loops and has no multiple directed edges,
it is called a simple directed graph.
 Because a simple directed graph has at most one edge associated to
each ordered pair of vertices (u, v), we call (u, v) an edge if there is an
edge associated to it in the graph.
 A directed graph may also contain directed edges that connect vertices u
and v in both directions; that is, when a digraph contains an edge from u
to v, it may also contain one or more edges from v to u.
 12
Directed
Graphs Multigraphs
 In some computer networks, multiple communication links between two
data centers may be present, as illustrated in Figure.
 Directed graphs that may have multiple directed edges from a vertex to
a second (possibly the same) vertex are used to model such networks.
 We called such graphs directed multigraphs. When there are m directed
edges, each associated to an ordered pair of vertices (u, v), we say that
(u, v) is an edge of multiplicity m.
 13

Graphs Graph Types

 Graphs 14

Terminology Basic Terminology

 First, we give some terminology that describes the vertices and edges of
undirected graphs.

 We will also find useful terminology describing the set of vertices

adjacent to a particular vertex of a graph.
 Graphs 15

Terminology Basic Terminology

 To keep track of how many edges are incident to a vertex, we make the
following definition.

 Example: What are the degrees and what are the neighbourhoods of the
vertices in the graphs G and H displayed in Figure
 Graphs 16

Terminology Basic Terminology

 Solution: In G, deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1,

deg(e) = 3, and deg(g) = 0. The neighbourhoods of these vertices:
N(a) = {b, f }, N(b) = {a, c, e, f }, N(c) = {b, d, e, f }, N(d) = {c},
N(e) = {b, c, f }, N(f ) = {a, b, c, e}, and N(g) = ∅.
 In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, and deg(d ) = 5. The
neighbourhoods of these vertices: N(a) = {b, d, e}, N(b) = {a, b, c, d, e},
N(c) = {b}, N(d) = {a, b, e}, and N(e) = {a, b, d}.
 Graphs 17

Terminology Basic Terminology

 A vertex of degree zero is called isolated. It follows that an isolated

vertex is not adjacent to any vertex. Vertex g in graph G is isolated.
 A vertex is pendant if and only if it has degree one. Consequently, a
pendant vertex is adjacent to exactly one other vertex. Vertex d in graph
G is pendant.
 Graphs The Handshaking
18

Terminology Theorem
Theorem 1: Let G = (V ,E) be an undirected graph with m edges. Then

 Example: How many edges are there in a graph with 10 vertices each of
degree six?
 Solution: Sum of the degrees of the vertices is 6 ・ 10 = 60, it follows
that 2m = 60 where m is the number of edges. Therefore, m = 30.
Theorem 1 shows that the sum of the degrees of the vertices of an
undirected graph is even.
 Theorem 2: An undirected graph has an even number of vertices of odd
degree.
 Graphs Basic Terminology
19

Terminology of directed graphs

 Because the edges in graphs with directed edges are ordered pairs, the
definition of the degree of a vertex can be refined to reflect the number
of edges with this vertex as the initial vertex and as the terminal vertex.
 Graphs Basic Terminology
20

Terminology of directed graphs

 Example: Find the in-degree and out-degree of each vertex in the graph
G with directed edges shown in Figure.

 Solution: The in-degrees in G are deg−(a) = 2, deg−(b) = 2, deg−(c) = 3,

deg−(d) = 2, deg−(e) = 3, and deg−(f ) = 0.
 The out-degrees are deg+(a) = 4, deg+(b) = 1, deg+(c) = 2, deg+(d) = 2,
deg+(e) = 3, and deg+ (f ) = 0.
 Graphs Basic Terminology
21

Terminology of directed graphs

 Because each edge has an initial vertex and a terminal vertex, the sum
of the in-degrees and the sum of the out-degrees of all vertices in a
graph with directed edges are the same. Both of these sums are the
number of edges in the graph.
Special Types of 22

Graphs Complete Graphs

 Complete Graphs: A complete graph on n vertices, denoted by Kn, is
a simple graph that contains exactly one edge between each pair of
distinct vertices.
 The graphs Kn, for n = 1, 2, 3, 4, 5, 6, are displayed in Figure.
 A simple graph for which there is at least one pair of distinct vertex not
connected by an edge is called non-complete graph.
Special Types of 23

Graphs Cycles
 Cycles: A cycle Cn, n ≥ 3, consists of n vertices v 1, v2, . . . , vn and edges
{v1, v2}, {v2, v3}, . . . , {vn−1, vn}, and {vn, v1}.
 The cycles C3, C4, C5, and C6 are displayed in Figure.
Special Types of 24

Graphs Wheels
 Wheels: We obtain a wheel Wn when we add an additional vertex to a
cycle Cn, for n ≥ 3, and connect this new vertex to each of the n vertices
in Cn, by new edges.
 The wheels W3, W4, W5, and W6 are displayed in Figure.
Special Types of 25

Graphs n-Cubes
 n-Cubes: An n-dimensional hypercube, or n-cube, denoted by Qn, is a
graph that has vertices representing the 2 n bit strings of length n.
 Two vertices are adjacent if and only if the bit strings that they represent
differ in exactly one bit position. We display Q1, Q2, and Q3 in Figure.
Special Types of 26

Graphs Bipartite Graphs

 Sometimes a graph has the property that its vertex set can be divided
into two disjoint subsets such that each edge connects a vertex in one of
these subsets to a vertex in the other subset.
 This leads us to Definite Bipartite Graph:

 C6 is bipartite, as shown in Figure, because its vertex set can be

partitioned into the two sets V1 = {v1, v3, v5} and V2 = {v2, v4, v6}, and
every edge of C6 connects a vertex in V1 and a vertex in V2.
Special Types of 27

Graphs Bipartite Graphs

 Example: Are the graphs G and H displayed in Figure bipartite?

 Solution: Graph G is bipartite because its vertex set is the union of two
disjoint sets, {a, b, d} and {c, e, f, g}, and each edge connects a vertex
in one of these subsets to a vertex in the other subset.
 (To be G bipartite it is not necessary that every vertex in {a, b, d} be
adjacent to every vertex in {c, e, f, g}. E.g., b and g are not adjacent.).
Graph H is not bipartite: its vertex set cannot be partitioned into two
subsets so that edges do not connect two vertices from the same subset.
Special Types of Complete Bipartite
28

Graphs Graphs
 Complete Bipartite Graphs: A complete bipartite graph Km,n is a
graph that has its vertex set partitioned into two subsets of m and n
vertices, respectively with an edge between two vertices if and only if
one vertex is in the first subset and the other vertex is in the second
subset.
 The complete bipartite graphs K2,3, K3,3, K3,5, and K2,6 are displayed in
Figure.
Special Types of 29

Graphs Applications
 Bipartite graphs can be used to model many types of applications that
involve matching the elements of one set to elements of another.
 Job Assignments
 Marriages on an Island
 Local Area Networks
 The various computers in a building, such as minicomputers and
personal computers, as well as peripheral devices such as printers and
plotters, can be connected using a local area network.
Special Types of 30

Graphs Applications
 Some of these networks are based on a star topology, where all devices
are connected to a central control device.
 A local area network can be represented using a complete bipartite
graph K1,n, as shown in Figure (a).
 Messages are sent from device to device through the central control
device.
 Other local area networks are based on a ring topology, where each
device is connected to exactly two others. Local area networks with a
ring topology are modeled using n-cycles, Cn, as shown in Figure (b).
 Messages are sent from device to device around the cycle until the
intended recipient of a message is reached.
Special Types of 31

Graphs Applications
 Some local area networks use a hybrid of these two topologies.
Messages may be sent around the ring, or through a central device.
 This redundancy makes the network more reliable.
 Local area networks with this redundancy can be modeled using wheels
Wn, as shown in Figure (c).
Special Types of 32

Graphs Applications
 Interconnection Networks for Parallel Computation
 For many years, computers executed programs one operation at a time.
Consequently, the algorithms written to solve problems were designed
to perform one step at a time; such algorithms are called serial.
 However, many computationally intense problems, such as weather
simulations, medical imaging, and cryptanalysis, cannot be solved in a
reasonable amount of time using serial operations, even on a
supercomputer. Parallel processing, which uses computers made up of
many separate processors, each with its own memory, helps overcome
the limitations of computers with a single processor. Parallel
algorithms, which break a problem into a number of subproblems that
can be solved concurrently.
 Representing 33

Graphs Introduction

 There are many useful ways to represent graphs. In working with a

graph it is helpful to be able to choose its most convenient
representation.
 Sometimes, two graphs have exactly the same form, in the sense that
there is a one-to-one correspondence between their vertex sets that
preserves edges. In such a case, we say that the two graphs are
isomorphic.
 Determining whether two graphs are isomorphic is an important
problem of graph theory.
 Representing Representing
34

Graphs Graphs

 One way to represent a graph without multiple edges

is to list all the edges of this graph.
 Another way to represent a graph with no multiple
edges is to use adjacency lists, which specify the
vertices that are adjacent to each vertex of the graph.
 Example: Use adjacency lists to describe the simple
graph given in Figure.
 Solution: Table lists those vertices adjacent to each
of the vertices of the graph.
 Representing Representing
35

Graphs Graphs

 Example: Represent the directed graph shown in

Figure by listing all the vertices that are the
terminal vertices of edges starting at each vertex
of the graph.
 Solution: Table represents the directed graph
shown in Figure.
 Representing Adjacency
36

Graphs Matrices
 To simplify computation, graphs can be represented using matrices.
 Two types of matrices commonly used to represent graphs will be
presented here. One is based on the adjacency of vertices, and the other
is based on incidence of vertices and edges.
 Suppose that G = (V ,E) is a simple graph where |V| = n. Suppose that
the vertices of G are listed arbitrarily as v1, v2, . . . , vn.
 The adjacency matrix A (or AG) of G, with respect to this listing of the
vertices, is the n x n zero–one matrix with 1 as its (i, j )th entry when vi
and vj are adjacent, and 0 as its (i, j )th entry when they are not adjacent.
In other words, if its adjacency matrix is A = [aij ], then
 Representing Adjacency
37

Graphs Matrices

 Example: Use an adjacency matrix to represent

the graph shown in Figure.
 Solution: We order the vertices as a, b, c, d. The
matrix representing this graph is:
 Representing Adjacency
38

Graphs Matrices

 Example: Draw a graph with the adjacency matrix

with respect to the ordering of vertices a, b, c, d.

 Solution: A graph with this adjacency matrix is shown in Figure.
 Representing Adjacency
39

Graphs Matrices
 Note that an adjacency matrix of a graph is based on the ordering chosen
for the vertices.
 Hence, there may be as many as n! different adjacency matrices for a
graph with n vertices, because there are n! different orderings of n
vertices.
 The adjacency matrix of a simple graph is symmetric, that is, aij = aji ,
because both of these entries are 1 when vi and vj are adjacent, and both
are 0 otherwise.
 Furthermore, because a simple graph has no loops, each entry aii, i = 1, 2,
3, . . . , n, is 0.
 Representing Adjacency
40

Graphs Matrices
 Adjacency matrices can also be used to represent undirected graphs with
loops and with multiple edges.
 A loop at the vertex vi is represented by a 1 at the (i, i)th position of the
adjacency matrix.
 When multiple edges connecting the same pair of vertices vi and vj, or
multiple loops at the same vertex, are present, the adjacency matrix is no
longer a zero–one matrix, because the (i, j )th entry of this matrix equals
the number of edges that are associated to {vi , vj }.
 All undirected graphs, including multigraphs and pseudographs, have
symmetric adjacency matrices.
 Representing Adjacency
41

Graphs Matrices

 Example: Use an adjacency matrix to represent the

pseudograph shown in Figure.
 Solution: The adjacency matrix using the ordering
of vertices a, b, c, d is:
a b c d
 Representing Adjacency
42

Graphs Matrices
 The matrix for a directed graph G = (V ,E) has a 1 in its (i, j )th position
if there is an edge from vi to vj , where v1, v2, . . . , vn is an arbitrary listing
of the vertices of the directed graph.
 In other words, if A = [aij ] is the adjacency matrix for the directed graph
with respect to this listing of the vertices, then

 The adjacency matrix for a directed graph does not have to be symmetric,
because there may not be an edge from vj to vi when there is an edge from
vi to vj . In the adjacency matrix (not zero–one matrix) for a directed
multigraph, aij equals the number of edges that are associated to (vi , vj ).
 Representing Incidence
43

Graphs Matrices

 Another common way to represent graphs is to use incidence matrices.

 Let G = (V ,E) be an undirected graph. Suppose that v1, v2, . . . , vn are the
vertices and e1, e2, . . . , em are the edges of G.
 Then the incidence matrix with respect to this ordering of V and E is the
n × m matrix M = [mij ], where
 Representing Incidence
44

Graphs Matrices
 Example: Represent the graph shown in Figure with an incidence
matrix.

 Solution: The incidence matrix:

 Representing Incidence
45

Graphs Matrices
 Incidence matrices can also be used to represent multiple edges and
loops. Multiple edges are represented in the incidence matrix using
columns with identical entries, because these edges are incident with the
same pair of vertices. Loops are represented using a column with exactly
one entry equal to 1, corresponding to the vertex that is incident with this
loop.
 Example: Represent the
pseudograph shown in Figure
using an incidence matrix.
 Solution: The incidence
matrix for this graph:
 Isomorphism of 46

Graphs Introduction

 In chemistry, graphs are used to model chemical compounds.

 Different compounds can have the same molecular formula but can differ
in structure.
 Such compounds can be represented by graphs that cannot be drawn in
the same way.
 The graphs representing previously known compounds can be used to
determine whether a supposedly new compound has been studied before.
 There is a useful terminology for graphs with the same structure.
 Isomorphism of 47

Graphs Definition

 In other words, when two simple graphs are isomorphic, there is a one-
to-one correspondence between vertices of the two graphs that preserves
the adjacency relationship.
 Isomorphism of simple graphs is an equivalence relation.
 Isomorphism of 48

Graphs Example
 Example: Show that the graphs G = (V ,E) and H = (W, F),
displayed in Figure, are isomorphic.
 Solution: The function f with f (u1) = v1, f (u2) = v4, f
(u3) = v3, and f (u4) = v2 is a one-to-one correspondence
between V and W.
 To see that this correspondence preserves adjacency, note
that adjacent vertices in G are u1 and u2, u1 and u3, u2 and u4,
and u3 and u4, and each of the pairs f (u1) = v1 and f
(u2) = v4, f (u1) = v1 and f (u3) = v3, f (u2) = v4 and f
(u4) = v2, and f (u3) = v3 and f (u4) = v2 consists of two
adjacent vertices in H.
 Are Two Simple
Isomorphism of Graphs
49

Graphs Isomorphic?

 It is often difficult to determine whether two simple graphs are

isomorphic.
 Sometimes it is not hard to show that two graphs are not isomorphic.
 In particular, we can show that two graphs are not isomorphic if we can
find a property only one of the two graphs has, but that is preserved by
isomorphism.
 A property preserved by isomorphism of graphs is called a graph
invariant.
 Are Two Simple
Isomorphism of Graphs
50

Graphs Isomorphic?
 For instance, isomorphic simple graphs must have the same number of
vertices, because there is a one-to-one correspondence between the sets
of vertices of the graphs.
 Isomorphic simple graphs also must have the same number of edges,
because the one-to-one correspondence between vertices establishes a
one-to-one correspondence between edges.
 In addition, the degrees of the vertices in isomorphic simple graphs must
be the same.
 That is, a vertex v of degree d in G must correspond to a vertex f (v) of
degree d in H, because a vertex w in G is adjacent to v if and only if f (v)
and f (w) are adjacent in H.
 Are Two Simple
Isomorphism of Graphs
51

Graphs Isomorphic?
 Example: Show that the graphs
displayed in Figure are not isomorphic.
 Solution: Both G and H have five
vertices and six edges.
 However, H has a vertex of degree one,
namely, e, where as G has no vertices of
degree one.
 It follows that G and H are not
isomorphic.
 Are Two Simple
Isomorphism of Graphs
52

Graphs Isomorphic?

 The number of vertices, the number of edges, and the number of vertices
of each degree are all invariants under isomorphism.
 If any of these quantities differ in two simple graphs, these graphs cannot
be isomorphic.
 However, when these invariants are the same, it does not necessarily
mean that the two graphs are isomorphic.
 There are no useful sets of invariants currently known that can be used to
determine whether simple graphs are isomorphic.
 Are Two Simple
Isomorphism of Graphs
53

Graphs Isomorphic?
 Example: Determine whether the graphs shown in Figure are
isomorphic.
 Solution: The graphs G and H both have eight vertices and 10
edges. They also both have four vertices of degree two and four of
degree three.
 Because these invariants all agree, it is still conceivable that these
graphs are isomorphic.
 However, G and H are not isomorphic. To see this, note that because
deg(a) = 2 in G, a must correspond to either t , u, x, or y in H,
because these are the vertices of degree two in H.
 However, each of these four vertices in H is adjacent to another
vertex of degree two in H, which is not true for a in G.
54