UNIVERSITY OF SOUTHERN MINDANAO

Discrete Mathematics
(CpE 04)
Prepared by:
JEANNALEN P. LUNOD
Department of Computer Engineering
 Topic Outline
• Graphs
• Definition
• Types of Graphs
• Graph Models
• Shortest-Path Problems
• Shortest-Path Algorithm

Discrete Mathematics - Graph Theory 2

Intended Learning Outcomes
• ILO1: identify the type of graph
• ILO2: identify graph model
• ILO3: solve shortest-path problems in
undirected weighted graphs

Discrete Mathematics - Graph Theory 3

 Graphs
• are discrete structures consisting of vertices
and edges that connect these vertices.
• TYPES of GRAPHS
a) Simple graph
b) Multigraph
c) Pseudograph
d) Directed graph
e) Directed multigraph

Discrete Mathematics - Graph Theory 4

 A. Simple graph
• 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.

Discrete Mathematics - Graph Theory 5

 Example:
• Suppose that a network is made up of
computers and telephone lines between
computers.
• We can represent the location of each
computer by a point and each telephone line
by an arc, as shown in Figure 1.

Discrete Mathematics - Graph Theory 6

Discrete Mathematics - Graph Theory 7
• In the network in Figure 1 there is at most
one telephone line between two computers,
each line operates in both directions, and no
computer has a telephone line to itself.
• This network can be modeled using a simple
graph, consisting of vertices that represent
the computers and undirected edges that
represent telephone lines.

Discrete Mathematics - Graph Theory 8

• Each edge connects two distinct vertices
and no two edges connect the same pair of
vertices.

Discrete Mathematics - Graph Theory 9

 B. Multigraph
• A multigraph G = (V, E) consists of a set V of
vertices, a set E of edges, and a function f
from E to { {u,v}|u,vV, uv }.
• The edges e1 and e2 are called multiple or
parallel edges if f(e1) = f(e2).

Discrete Mathematics - Graph Theory 10

 Example:
• When there is heavy traffic, there may be
multiple telephone lines between computers
in a network, as illustrated in Figure 2.

Discrete Mathematics - Graph Theory 11

• Simple graphs are not sufficient to model
such networks.
• Instead, we use multigraphs, which consist
of vertices and undirected edges between
these vertices, with multiple edges between
pairs of vertices allowed.
• Every simple graph is also a multigraph.

Discrete Mathematics - Graph Theory 12

• However, not all multigraphs are simple
graphs, since in a multigraph two or more
edges may connect the same pair of
vertices,

Discrete Mathematics - Graph Theory 13

 C. Pseudograph
• A pseudograph G = (V, E) consists of a set V
of vertices, a set E of edges, and a function f
from E to { {u,v}|u,v  V }.
• An edge is a loop if f(e) = {u, u} = {u} for some
u V .

Discrete Mathematics - Graph Theory 14

 Example:
• A computer network may contain a
telephone line from a computer to itself
(perhaps for diagnostic purposes), as
illustrated in Figure 3.

Discrete Mathematics - Graph Theory 15

Discrete Mathematics - Graph Theory 16
• We cannot use multigraphs to model such
networks, since loops, which are edges from
a vertex to itself, are not allowed in
multigraphs.
• Instead, we use pseudographs, which are
more general than multigraphs, since an
edge in a pseudograph may connect a vertex
with itself.

Discrete Mathematics - Graph Theory 17

 D. Directed graph
• A directed graph ( V, E ) consists of a
set of vertices V and a set of edges E
that are ordered pairs of elements of V.

Discrete Mathematics - Graph Theory 18

 Example:
• Telephone lines in a computer network may
not operate in both directions.
• For instance, in Figure 4 the host computer
in New York can only receive data from other
computers and cannot send out data.

Discrete Mathematics - Graph Theory 19

Discrete Mathematics - Graph Theory 20
• Other telephone lines operating in both
directions are represented by pairs of edges
in opposite directions.
• We use directed graphs to model such
networks.
• The edges of a directed graph are ordered
pairs.

Discrete Mathematics - Graph Theory 21

• Loops, ordered pairs of the same element,
are allowed, but multiple edges in the same
direction between two vertices are not.

Discrete Mathematics - Graph Theory 22

 E. Directed multigraph
• A directed multigraph G = ( V, E ) consists of
a set V of vertices, a set E of edges, and a
function f from E to { (u,v)|u,v  V }.
• The edges e1 and e2 are multiple edges if f(e1)
= f(e2).

Discrete Mathematics - Graph Theory 23

 Example:
• Multiple lines may be present in the
computer network, so that there may be
several one-way lines to host in New York
from each location, and perhaps more than
one line back to each remote computer from
the host, as illustrated in Figure 5.

Discrete Mathematics - Graph Theory 24

Discrete Mathematics - Graph Theory 25
• The terminology for the various types of
graphs is summarized in Table 1.

Discrete Mathematics - Graph Theory 26

• We will use graph to describe graphs with
directed or undirected edges, with or
without loops and multiple edges.
• We will use the terms undirected graph or
pseudograph for an undirected graph that
may have multiple edges and loops.
• We will always use the adjective directed
when referring to graphs that have ordered
pairs associated to their edges.
Discrete Mathematics - Graph Theory 27
 Graph Models
• Graphs are used in a wide variety of
models.

Discrete Mathematics - Graph Theory 28

 Example 1: Niche Overlap
Graphs in Ecology
• Graphs are used in many models involving
the interaction of different species of
animals.
• For instance, the competition between
species in an ecosystem can be modeled
using a niche overlap graph.
• Each species is represented by a vertex.

Discrete Mathematics - Graph Theory 29

• An undirected edge connects two vertices if
the two species represented by these
vertices compete (that is, some of the food
resources they use are the same).

Discrete Mathematics - Graph Theory 30

• The graph in Figure
6 models the
ecosystem of a
forest.
• We see from this
graph that squirrels
and raccoons
compete but the
crows and shrews do
not.
Discrete Mathematics - Graph Theory 31
 Example 2: Acquaintanceship
Graphs
• We can use graph models to represent
various relationships between people.
• For example, we can use a graph to
represent whether two people know each
other, that is, whether they are acquainted.
• Each person in a particular group of people is
represented by a vertex.
• An undirected edge is used to connect two
people when these people know each other.
Discrete Mathematics - Graph Theory 32
• A small acquaintanceship graph is shown in
Figure 7.

Discrete Mathematics - Graph Theory 33

• The acquaintanceship graph of all people in
the world has more than 6 billion vertices
and probably more than 1 trillion edges!

Discrete Mathematics - Graph Theory 34

 Example 3: Influence graphs
• In studies of group behavior it is observed
that certain people can influence the
thinking of others.
• A directed graph called an influence graph
can be used to model this behavior.
• Each person of the group is represented by a
vertex.

Discrete Mathematics - Graph Theory 35

• There is a directed from vertex a to vertex b
when the person represented by vertex a
influences the person represented by vertex
b.
• An example of an influence graph for
members of a group is shown in Figure 8.

Discrete Mathematics - Graph Theory 36

Discrete Mathematics - Graph Theory 37
• In the group modeled by this influence
graph, Deborah can influence Brian, Fred,
and Linda, but no one can influence her.
• Also, Yvonne and Brian can influence each
other.

Discrete Mathematics - Graph Theory 38