Mathematical Foundations of Computing
UNIT 8
GRAPH THEORY
The graph
A graph G = (V, E) consists of:
V : a nonempty set of vertices (or nodes) and
E: a set of unordered pairs of distinct
elements of V called edges (or arcs).
Each edge has either one or two vertices associated with it,
called its endpoints.
An edge is said to connect its endpoints.
2
Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles
How many vertices? How many edges?
Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles
SET OF VERTICES (NODES)
V = { Chicago, Denver, Detroit, Los Angeles,
New York, San Francisco, Washington }
SET OF EDGES (arcs)
E = { {San Francisco, Los Angeles},
{San Francisco, Denver},
{Los Angeles, Denver}, {Denver, Chicago},
{Chicago, Detroit}, {Detroit, New York},
{New York, Washington}, {Chicago, Washington},
{Chicago, New York} }
4
Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles
The network is made up of computers and telephone lines
between computers.
There is at most 1 telephone line between 2 computers in the
network.
Each line operates in both directions.
No computer has a telephone line to itself.
Multiple (Parallel) Edges (arcs)
Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles
Edges (arcs) are called multiple or parallel edges if
they connect the same two distinct vertices.
When there are m multiple edges connecting the same
unordered pair of vertices {u, v}, we say that {u, v} is
an edge of multiplicity m.
6
Loops
An edge is called a loop if it connects a vertex to
itself.
Detroit
New York
San Francisco
Chicago
Denver
Washington
Los Angeles
THERE CAN BE TELEPHONE LINES IN THE NETWORK FROM A
COMPUTER TO ITSELF (for diagnostic use).
Undirected Graphs
Undirected graphs:
Graphs, whose edges are undirected.
8
Undirected Graphs: (i) The Simple Graph
Simple undirected graph:
An undirected graph in which each edge connects
two different vertices, where no two edges connect
the same pair of vertices (doesn’t have parallel
edges). It doesn’t have loops as well.
Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles
Undirected Graphs: (ii) Multigraphs
Are undirected graphs that may have multiple
edges connecting the same vertices, but they
don’t have loops
Detroit
New York
San Francisco
Chicago
Denver Washington
Los Angeles
THERE CAN BE MULTIPLE TELEPHONE LINES BETWEEN TWO
COMPUTERS IN THE NETWORK.
10
Undirected Graphs: (iii) Pseudograph Graph
A graph in which two or more edges may
connect the same pair of vertices (have
parallel edges), and in addition, an edge
may connect a vertex to itself (have loops).
Detroit
New York
San Francisco
Chicago
Denver
Washington
Los Angeles
11
The Directed Graph
Directed graph: A graph, that consists of a nonempty set of
vertices and a set of directed edges (or arcs). Each directed
edge is associated with an ordered pair of vertices.
Detroit
San Francisco Chicago New York
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.
12
The Directed Graph: (i) The Simple Directed Graph
Simple directed graph: is a directed graph
which has no loops and has no multiple
directed edges.
13
The Directed Graph: (ii) The Multigraph
The directed multigraph is a graph, in which the edges are
ordered pairs of (not necessarily distinct) vertices, and in
addition there may be multiple edges.
The directed multigraph may contain Loops
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.
14
The Mixed Graph
A mixed graph is a graph with both directed
and undirected edges
15
Graph Types_Summary
16
Graph Models (i)
Acquaintanceship Graph:
is a simple graph to represent whether two
people know each other, that is, whether they
are acquainted.
17
Graph Models (ii)
Influence Graph:
is a directed graph to show people who can
influence the thinking of others.
From the shown graph, Deborah cannot be influenced,
but she can influence Brian, Fred, and Linda.
Also, Yvonne and Brian can influence each other
18
Graph Models (iii)
Round-Robin Tournament
Graph:
Is a directed graph
representing a
tournament where each
team plays each other
team exactly once and no
ties are allowed.
Note that (a , b) is an
edge if team a beats team
b.
In the shown graph, team
1 is undefeated in this
tournament, and Team 3 is
winless.
19
Graph Models (iv): Call graphs
Directed multigraph (a) represents calls from a telephone
number to another, each telephone number is represented
by a vertex and each telephone call is represented by a
directed edge.
Undirected graph (b) represents calls between two
numbers. Here, we care only whether there has been call
connecting two telephone numbers.
20
