Graphs

Slides based on those of Kenneth H. Rosen

Slides by Sylvia Sorkin, Community College of Baltimore County - Essex Campus

1
 Simple Graph

Definition 1. 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.

2
 A simple graph

Detroit
New York
San Francisco

Chicago
Denver Washington

Los Angeles

How many vertices? How many edges?

3
 A simple graph
SET OF VERTICES

V = { Chicago, Denver, Detroit, Los Angeles,

New York, San Francisco, Washington }

SET OF EDGES

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
 A simple graph
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.

These are undirected edges,

each of which connects two distinct vertices, and
no two edges connect the same pair of vertices.
5
 A Non-Simple Graph

Definition 2. In a multigraph G = (V, E)

two or more edges may connect the
same pair of vertices.

6
 A Multigraph

THERE CAN BE MULTIPLE TELEPHONE LINES

BETWEEN TWO COMPUTERS IN THE NETWORK.

Detroit
New York
San Francisco

Chicago
Denver Washington

Los Angeles

7
 Multiple Edges

Detroit
New York
San Francisco

Chicago
Denver Washington

Los Angeles

Two edges are called multiple or parallel edges

if they connect the same two distinct vertices.

8
 Another Non-Simple Graph

Definition 3. In a pseudograph G = (V, E)

two or more edges may connect the
same pair of vertices, and in addition,
an edge may connect a vertex to itself.

9
 A Pseudograph
THERE CAN BE TELEPHONE LINES IN THE NETWORK
FROM A COMPUTER TO ITSELF (for diagnostic use).

Detroit
New York
San Francisco

Chicago
Denver
Washington

Los Angeles
10
 Loops

Detroit
New York
San Francisco

Chicago
Denver
Washington
Los Angeles

An edge is called a loop

if it connects a vertex to itself.

11
 Undirected Graphs

pseudographs
multigraphs
simple graphs

12
 A Directed Graph

Definition 4. In a directed graph G = (V, E)

the edges are ordered pairs of (not
necessarily distinct) vertices.

13
 A Directed Graph
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.
Detroit
New York
Chicago
San Francisco

Denver Washington

Los Angeles
14
 A Directed Multigraph

Definition 5. In a directed multigraph G = (V, E)

the edges are ordered pairs of (not
necessarily distinct) vertices, and in addition
there may be multiple edges.

15
 A Directed Multigraph
THERE MAY BE SEVERAL ONE-WAY LINES
IN THE SAME DIRECTION FROM ONE COMPUTER
TO ANOTHER IN THE NETWORK.

Detroit
New York
Chicago
San Francisco

Denver Washington

Los Angeles
16
 Types of Graphs
TYPE EDGES MULTIPLE EDGES LOOPS
ALLOWED? ALLOWED?

Simple graph Undirected NO NO

Multigraph Undirected YES NO

Pseudograph Undirected YES YES

Directed graph Directed NO YES

Directed multigraph Directed YES YES

17
 Adjacent Vertices (Neighbors)

Definition 1. Two vertices, u and v in an undirected

graph G are called adjacent (or neighbors) in G, if
{u, v} is an edge of G.

An edge e connecting u and v is called incident with

vertices u and v, or is said to connect u and v. The
vertices u and v are called endpoints of edge {u, v}.

18
 Adjacency Matrix
A simple graph G = (V, E) with n vertices
can be represented by its adjacency matrix,
A, where entry aij in row i and column j is

1 if { vi, vj } is an edge in G,
aij =
0 otherwise.

19
 Finding the adjacency matrix

c This graph has 6 vertices

a, b, c, d, e, f. We can
b d arrange them in that order.
f

a e

W5

20
 Finding the adjacency matrix
TO
c a b c d e f
FROM
a 0 1 0 0 1 1
b d
f b
c
a e
d
W5 e
f
There are edges from a to b, from a to e, and from a to f
21
 Finding the adjacency matrix
TO
c a b c d e f
FROM
a 0 1 0 0 1 1
b d
f b 1 0 1 0 0 1
c
a e
d
W5 e
f
There are edges from b to a, from b to c, and from b to f
22
 Finding the adjacency matrix
TO
c a b c d e f
FROM
a 0 1 0 0 1 1
b d
f b 1 0 1 0 0 1
c 0 1 0 1 0 1
a e
d
W5 e
f
There are edges from c to b, from c to d, and from c to f
23
 Finding the adjacency matrix
TO
c a b c d e f
FROM
a 0 1 0 0 1 1
b d
f b 1 0 1 0 0 1
c 0 1 0 1 0 1
a e
d
W5 e
f
COMPLETE THE ADJACENCY MATRIX . . .
24
 Finding the adjacency matrix
TO
c a b c d e f
FROM
a 0 1 0 0 1 1
b d
f b 1 0 1 0 0 1
c 0 1 0 1 0 1
a e
d 0 0 1 0 1 1
W5 e 1 0 0 1 0 1
f 1 1 1 1 1 0
Notice that this matrix is symmetric. That is aij = aji Why?
25
 Degree of a vertex

Definition 1. The degree of a vertex in an

undirected graph is the number of edges
incident with it, except that a loop at a vertex
contributes twice to the degree of that vertex.

c d
deg( d ) = 1
b

a g f e
26
 Degree of a vertex

Definition 1. The degree of a vertex in an

undirected graph is the number of edges
incident with it, except that a loop at a vertex
contributes twice to the degree of that vertex.

c d
b

deg( e ) = 0
a g f e
27
 Degree of a vertex

Definition 1. The degree of a vertex in an

undirected graph is the number of edges
incident with it, except that a loop at a vertex
contributes twice to the degree of that vertex.

c d
deg( b ) = 6
b

a g f e
28
 Degree of a vertex

Find the degree of all the other vertices.

deg( a ) deg( c ) deg( f ) deg( g )

c d
deg( b ) = 6 deg( d ) = 1
b

deg( e ) = 0
a g f e
29
 Degree of a vertex

Find the degree of all the other vertices.

deg( a ) = 2 deg( c ) = 4 deg( f ) = 3 deg( g ) = 4

c d
deg( b ) = 6 deg( d ) = 1
b

deg( e ) = 0
a g f e
30
 Degree of a vertex

Find the degree of all the other vertices.

deg( a ) = 2 deg( c ) = 4 deg( f ) = 3 deg( g ) = 4
TOTAL of degrees = 2 + 4 + 3 + 4 + 6 + 1 + 0 = 20

c d
deg( b ) = 6 deg( d ) = 1
b

deg( e ) = 0
a g f e
31
 Degree of a vertex

Find the degree of all the other vertices.

deg( a ) = 2 deg( c ) = 4 deg( f ) = 3 deg( g ) = 4
TOTAL of degrees = 2 + 4 + 3 + 4 + 6 + 1 + 0 = 20
TOTAL NUMBER OF EDGES = 10
c d
deg( b ) = 6 deg( d ) = 1
b

deg( e ) = 0
a g f e
32
 Handshaking Theorem
Theorem 1. Let G = (V, E) be an undirected
graph G with e edges. Then

 deg( v ) = 2 e
vV

“The sum of the degrees over all the vertices

equals twice the number of edges.”

NOTE: This applies even if multiple edges and loops are

present.
33