MODULE
SIX
PROBLEM
SET
1
Directions:
Type
your
solutions
into
this
document
and
be
sure
to
show
all
steps
for
arriving
at
your
solution.
Just
giving
a
final
number
may
not
receive
full
credit.
P
ROBLEM
1
For
parts
(a)
and
(b),
indicate
if
each
of
the
two
graphs
are
equal.
Justify
your
answer.
(a)
Figure
1:
Left:
An
undirected
graph
has
5
vertices.
The
vertices
are
arranged
in
the
form
of
an
inverted
pentagon.
From
the
top
left
vertex,
moving
clockwise,
the
vertices
are
labeled:
a,
b,
c,
d,
and
e.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
a
and
b;
a
and
c;
b
and
c;
c
and
d;
e
and
d;
and
e
and
c.
Figure
2:
Right:
The
adjacency
list
representation
of
a
graph.
The
list
shows
all
the
vertices,
a
through
e,
in
a
column
from
top
to
bottom.
The
adjacent
vertices
for
each
vertex
in
the
column
are
placed
in
a
row
to
the
right
of
the
corresponding
vertex’s
cell
in
the
column.
An
arrow
points
from
each
cell
in
the
column
to
its
corresponding
row
on
the
right.
Data
from
the
list,
as
follows:
Vertex
a
is
adjacent
to
vertices
b
and
c.
Vertex
b
is
adjacent
to
vertices
a
and
c.
Vertex
c
is
adjacent
to
vertices
a,
b,
d,
and
e.
Vertex
d
is
adjacent
to
vertices
c
and
e.
Vertex
e
is
adjacent
to
vertices
c
and
d.
The
provided
adjacency
list
tells
us
which
vertices
are
connected
together.
The
graph
that
corresponds
to
this
adjacency
list
will
look
like
this and this graph is equal to the one that is present on the left in the
question.
Therefore,
the
2
graphs
are
considered
to
be
equal.
(b)
Figure
3:
An
undirected
graph
has
5
vertices.
The
vertices
are
arranged
in
the
form
of
an
inverted
pentagon.
Moving
clockwise
from
the
top
left
vertex
a,
the
other
vertices
are,
b,
c,
d,
and
e.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
a
and
c;
a
and
d;
d
and
c;
and
e
and
b.
The
provided
adjacency
matrix
tells
us
whether
an
edge
is
present
be-
tween
the
2
vertex
or
not.
If
the
value
of
(v1,v2)
in
the
matrix
is
equalto
1,
then
the
edge
is
present.
If
the
value
is
equal
to
0,
then
no
edge
is
present.
The
graph
corresponding
to
the
matrix
is
not
equal
to
the
one
present
at
the
left.
0
0
1
1
0
0
0
0
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
(c)
Prove
that
the
two
graphs
below
are
isomorphic.
Figure
4:
Two
undirected
graphs.
Each
graph
has
6
vertices.
The
ver-
tices
in
the
first
graph
are
arranged
in
two
rows
and
3
columns.
From
left
to
right,
the
vertices
in
the
top
row
are
1,
2,
and
3.
From
left
to
right,
the
vertices
in
the
bottom
row
are
6,
5,
and
4.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
1
and
2;
2
and
3;
1
and
5;
2
and
5;
5
and
3;
2
and
4;
3
and
6;
6
and
5;
and
5
and
4.
The
vertices
in
the
second
graph
are
a
through
f.
Vertices
d,
a,
and
c,
are
vertically
inline.
Vertices
e,
f,
and
b,
are
horizontally
to
the
right
of
vertices
d,
a,
and
c,
respectively.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
a
and
d;
a
and
c;
a
and
e;
a
and
b;
d
and
b;
a
and
f;
e
and
f;
c
and
f;
and
b
and
f.
Given
the
f
two
graphs,
Graph
1
(V
1
,
E
1
)
and
Graph
2
(V
2
,
E
2
),
where
V
1
f
=1,
2,3,4,5,
6,
f
E
1
f
=
f
(1,2),
(1,
5),
(2,
3),
(2,
4),
(2,
5)(,
3,
5)(3,
6),
(4,
5),
(5,
6),
V
2
=
a,
b,
c,
d,
e,
f,
E
2
=
(a,
b),
(a,
c),
(a,
d),
(a,
e),
(a,
f),
(b,
d),
(b,
f),
(c,
f),
(e,
f).The
one
to
one
correspondences
between
vertices
of
G
1
and
G
2
is
given
by
1
⟷ f
c,
2
⟷ f
f,
3
⟷ f
b,
4
⟷
e,
5
⟷
a,
6
⟷ f
d.
f
The
one
to
f
one
f
correspon-
dence between the edges of G1 and G2 is given by (1, 2) ⟷ (c, f ), (1, 5)
⟷
(c,
a),
(2,
3)
⟷
(f,
b),
(2,
4)
⟷
(f,e),
(2,
5)
⟷
(f,a),
(3,
5)
⟷
(b,
a),
⟷
(3,
6)
⟷
(b,
d),
(4,
5)
⟷
(e,
a),
(5,
6)
⟷
(a,
d).
Therefore,
the
graphs
can
be
considered
isomorphic.
(d)
Show
that
the
pair
of
graphs
are
not
isomorphic
by
showing
that
there
is
a
property
that
is
preserved
under
isomorphism
which
one
graph
has
and
the
other
does
not.
Figure
5:
Two
undirected
graphs.
The
first
graph
has
5
vertices,
in
the
form
of
a
regular
pentagon.
From
the
top
vertex,
moving
clockwise,
the
vertices
are
labeled:
1,
2,
3,
4,
and
5.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
1
and
2;
2
and
3;
3
and
4;
4
and
5;
and
5
and
1.
The
second
graph
has
4
vertices,
a
through
d.
Vertices
d
and
c
are
horizontally
inline,
where
vertex
d
is
to
the
left
of
vertex
c.
Vertex
a
is
above
and
between
vertices
d
and
c.
vertex
b
is
to
the
right
and
below
ver-
tex
a,
but
above
the
other
two
vertices.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
a
and
b;
b
and
c;
a
and
d;
d
and
c;
d
and
b.
The degree of f each f vertex f f f in f graph f H1 f f is f 2. f However, H2 f has
two ver- tices of degree 3 (b and d). With this in mind, we can’t find a one
to one correspondence f f between f vertices f f f H1 f f f f f and f f f H2, f f f which f f f is f f f
what f f f f f would preservethe degree of vertices. Since isomorphism f f
preserves f f the f degree of vertices,and f f we f f can’t f f find f f the f f one f f to f f one f
correspondences f f f in the provided graphs,the graphs can’t be considered
isomorphic.
P
ROBLEM
2
Refer
to
the
undirected
graph
provided
below:
Figure
6:
An
undirected
graph
has
9
vertices.
6
vertices
form
a
hexagon,
which
is
tilted
upward
to
the
right.
Starting
from
the
leftmost
vertex,
moving
clockwise,
the
vertices
forming
the
hexagon
shape
are:
D,
A,
B,
E,
I,
and
F.
Vertex
H
is
above
and
to
the
right
of
vertex
B.
Vertex
G
is
the
rightmost
vertex,
below
vertex
H
and
above
vertex
E.
Vertex
C
is
the
bottommost
vertex,
a
little
to
the
right
of
vertex
E.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
A
and
D;
A
and
B;
B
and
F;
B
and
H;
H
and
G;
G
and
E;
B
and
E;
A
and
E;
E
and
I;
I
and
C;
I
and
F;
and
F
and
D.
(i)
What
is
the
maximum
length
of
a
f
path
f
in
f
the
f
graph?
Give
f
an
f
example
ofa
path
of
that
length.
The
f
max
length
f
of
the
f f
path
f
is
f
8.
f
The
sequence
f
of
vertices
f f
C
f
I
f
F
D
AB
H
G
E
satisfies
5.
(ii)
What
is
the
maximum
length
of
a
cycle
in
the
graph?
Give
an
example
ofa
cycle
of
that
length.
The
max
length
of
the
cycle
is
8.
I
F
D
A
B
H
G
E
I
satisfies
7.
(iii)
Give
an
example
of
an
open
walk
of
length
five
in
the
graph
that
is
a
trailbut
not
a
path.
An
example
of
an
open
walk
is
when
the
first
and
last
vertices
are
dif-
ferent.
It
is
considered
to
be
a
trail
due
to
no
edges
being
repeated.
It
is
not
a
path
due
to
vertex
E
being
repeated.
(iv)
Give
an
example
of
a
closed
walk
of
length
four
in
the
graph
that
is
not
acircuit.
An
example
f
of
a
closed
walk
is
f
when
the
first
and
last
vertices
are
the
same.
It
is
not
a
circuit
due
to
it
also
not
being
a
trail
due
to
the
edgesbeing
separated.
(v)
Give
an
example
of
a
circuit
of
length
zero
in
the
graph.
An
example
of
a
circuit
is
when
the
first
and
last
vertices
are
the
same.In
this
case,
the
length
is
zero,
therefore
the
first
and
last
vertices
are
the
same.
P
ROBLEM
3
(a)
Find
the
connected
components
of
each
graph.
(i)
G
=
(V,
E).
f
V
=
{
a,
b,
c,
d,
e
}
.
E
=
∅
The connected components are 1:ad, 2:b, 3:e, 4:d, 5:jih, 6:5, 7:fj, 8:fi
(ii)
f
G
=
(V,
E).
f
V
=
{
a,
b,
c,
d,
e,
f
}
. E
=
{{
c,
f
}
,
{
a,
b
}
,
{
d,
a
}
,
{
e,
c
}
,
{
b,
f
}}
The connected components are 1:bac, 2:d,e 3:fjih, 4:g.
(b)
Determine
the
edge
connectivity
and
the
vertex
connectivity
of
each
graph.
(i)
Figure
7:
An
undirected
graph
has
8
vertices,
1
through
8.
4
ver-
tices
form
a
rectangular-shape
on
the
left.
Starting
from
the
top
left
vertex
and
moving
clockwise,
the
vertices
of
the
rectangular
shape
are,
1,
2,
3,
and
4.
3
vertices
form
a
triangle
on
the
right,
with
a
vertical
side
on
the
left
and
the
other
vertex
on
the
extreme
right.
Starting
from
the
top
vertex
and
moving
clockwise,
the
vertices
of
the
triangu-
lar
shape
are,
7,
8,
and
5.
Vertex
6
is
between
the
rectangular
shape
and
the
triangular
shape.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
1
and
2;
2
and
3;
3
and
4;
4
and
1;
2
and
6;
4
and
6;
3
and
6;
6
and
7;
6
and
8;
6
and
5;
7
and
5;
7
and
8;
and
5
and
8.
Edge
=
2,
Vertex
=
1.
(ii)
Figure
8:
An
undirected
graph
has
8
vertices,
1
through
8.
4
ver-
tices
form
a
rectangular
shape
in
the
center.
Starting
from
the
top
left
vertex
and
moving
clockwise,
the
vertices
of
the
rectangular
shape
are,
3,
7,
5,
and
6.
Vertex
2
is
at
about
the
center
of
the
rectangular
shape.
Vertex
8
is
to
the
right
of
the
rectangular
shape.
Vertex
1
and
4
are
to
the
left
of
the
rectangular
shape,
horizontally
in-line
with
vertices
3
and
6,
respectively.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
1
and
3;
3
and
7;
3
and
4;
3
and
6;
3
and
2;
4
and
2;
4
and
6;
6
and
2;
6
and
5;
2
and
5;
2
and
7;
2
and
8;
7
and
5;
7
and
8;
and
5
and
8.
Edge
=
1,
Vertex
=
1
P
ROBLEM
4
For
parts
(a)
and
(b)
below,
find
an
Euler
circuit
in
the
graph
or
explain
why
the
graph
does
not
have
an
Euler
circuit.
(a)
Figure
9:
An
undirected
graph
has
6
vertices,
a
through
f.
5
vertices
are
in
the
form
of
a
regular
pentagon,
rotated
90
degrees
clockwise.
Hence,
the
top
vertex
becomes
the
rightmost
vertex.
From
the
bottom
left
vertex,
moving
clockwise,
the
vertices
in
the
pentagon
shape
are
labeled:
a,
b,
c,
e,
and
f.
Vertex
d
is
above
vertex
e,
below
and
to
the
right
of
vertex
c.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
a
and
b;
a
and
c;
a
and
d;
a
and
f;
b
and
f;
b
and
c;
b
and
e;
c
and
d;
d
and
e;
and
d
and
f.
Edges
c
f,
a
d,
and
b
e
intersect
at
the
same
point.
The
provided
graph
contains
six
vertices,
with
each
vertex
degree
being
even.
Therefore,
using
the
characterization
theorem
of
Euler
graphs,
the
given
graph
is
Euler
and
also
contains
a
Euler
circuit.
This
is
due
to
every
edge
of
the
graph
being
used
only
once.
In
the
provided
graph,
we
find
the
Euler
circuit
starting
and
ending
at
Vertex
E.
The
complete
Euler
circuitis
E
D
F
A
B
C
D
A
f
C
F
B
E.
(b)
Figure
10:
An
undirected
graph
has
7
vertices,
a
through
g.
5
vertices
are
in
the
form
of
a
regular
pentagon,
rotated
90
degrees
clockwise.
Hence,
the
top
vertex
becomes
the
rightmost
vertex.
From
the
bottom
left
vertex,
moving
clockwise,
the
vertices
in
the
pentagon
shape
are
labeled:
a,
b,
c,
e,
and
f.
Vertex
d
is
above
vertex
e,
below
and
to
the
right
of
vertex
c.
Vertex
g
is
below
vertex
e,
above
and
to
the
right
of
vertex
f.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
a
and
b;
a
and
c;
a
and
d;
a
and
f;
b
and
f;
b
and
c;
b
and
e;
c
and
d;
c
and
g;
d
and
e;
d
and
f;
and
f
and
g.
The
provided
graph
contains
seven
vertices,
with
each
vertex
degree
being
even.
Therefore,
by
characterization
theorem
of
Euler
graphs,
the
provided
graph
is
Euler
and
also
contains
a
Euler
circuit.
In
the
provided
graph,
we
find
the
Euler
circuit
starting
and
ending
at
Vertex
E.
The
complete
Euler
circuit
is
E
D
f
C
B
A
F
G
C
A
D
F
B
f
E.
(c)
For
each
graph
below,
find
an
Euler
trail
in
the
graph
or
explain
why
the
graph
does
not
have
an
Euler
trail.
(Hint:
One
way
to
find
an
Euler
trail
is
to
add
an
edge
between
two
vertices
with
odd
degree,
find
an
Euler
circuit
in
the
resulting
graph,
and
then
delete
the
added
edge
from
the
circuit.)
(i)
Figure
11:
An
undirected
graph
has
6
vertices,
a
through
f.
5
vertices
are
in
the
form
of
a
regular
pentagon,
rotated
90
degrees
clockwise.
Hence,
the
top
vertex
becomes
the
rightmost
vertex.
From
the
bottom
left
vertex,
moving
clockwise,
the
vertices
in
the
pentagon
shape
are
labeled:
a,
b,
c,
e,
and
f.
Vertex
d
is
above
vertex
e,
below
and
to
the
right
of
vertex
c.
Undirected
edges,
line
segments,
are
between
the
following
vertices:
a
and
b;
a
and
c;
a
and
d;
a
and
f;
b
and
f;
b
and
c;
c
and
d;
c
and
f;
d
and
e;
and
d
and
f.
The
provided
graph
has
six
vertices
with
exactly
two
vertices
(B
and
E)
being
at
an
odd
degree.
The
provided
graph
has
an
Euler
trail
which
is
as
follows:
E
D
C
B
A
F
D
A
C
F
B.
(ii)
Figure
12:
An
undirected
graph
has
6
vertices,
a
through
f.
5
vertices
are
in
the
form
of
a
regular
pentagon,
rotated
90
degrees
clockwise.
Hence,
the
top
vertex
becomes
the
rightmost
vertex.
From
the
bottom
left
vertex,
moving
clockwise,
the
vertices
in
the
pentagon
shape
are
labeled:
a,
b,
c,
e,
and
f.
Vertex
d
is
above
vertex
e,
below
and
to
the right of vertex c. Undirected edges, line segments, are between the
following vertices: a and b; a and c; a and d; a and f; b and f; b
and c; b and e; c and d; d and e; and d and f. Edges c f, a d, and b e
intersect at the same point.
The
provided
graph
has
six
vertices,
none
of
which
containing
an
odd
vertex.
The
provided
graph
is
a
Euler
trail
which
is
as
follows:
E
D
C
B
A
F
D
A
C
F
B
E.
It
is
also
considered
to
be
an
Euler
circuit
dueto
it
being
a
closed
trail.
P
ROBLEM
5
Consider
the
following
tree
for
a
prefix
code:
Figure
13:
A
tree
with
5
vertices.
The
top
vertex
branches
into
character,
a,
on
the
left,
and
a
vertex
on
the
right.
The
vertex
in
the
second
level
branches
into
character,
e,
on
the
left,
and
a
vertex
on
the
right.
The
vertex
in
the
third
level
branches
into
two
vertices.
The
left
vertex
in
the
fourth
level
branches
into
charac-
ter,
c,
on
the
left,
and
character,
n,
on
the
right.
The
right
vertex
in
the
fourth
level
branches
into
character,
d,
on
the
left,
and
character,
y,
on
the
right.
The
weight
of
each
edge
branching
left
from
a
vertex
is
0.
The
weight
of
each
edge
branching
right
from
a
vertex
is
1.
(a)
Use
the
tree
to
encode
“day”.
Day
is
encoded
as
111001111.
(b)
Use
the
tree
to
encode
“candy”.
Candy is encoded as 11000110111101111
(c)
Use
the
tree
to
decode
“1110101101
′′
.
1110101101 is decoded as Den.
(d)
Use
the
tree
to
decode
“111001101110010
′′
.
111001101110010 is decoded as Dance.
P
ROBLEM
6
Figure
f
14:
A
tree
diagram
has
9
f
vertices.
f
The
f
top
f
vertex
f
is
f
d.
f
Vertex
f
d
f
has
three
branches
to
vertices,
f,
b,
and
a.
Vertex
b
branches
to
three
vertices,
i,
h,
and
e.
Vertex
a
branches
to
vertex
c.
Vertex
c
branches
to
vertex
g.
(a)
Give
the
order
in
which
the
vertices
of
the
tree
are
visited
in
a
post-
ordertraversal.
The
post-order
traversal
is
f
i
h
e
b
g
c
a
d.
(b)
Give
the
order
in
which
the
vertices
of
the
tree
are
visited
in
a
pre-
ordertraversal.
The
pre-order
traversal
is
d
f
b
i
g
e
a
c
g.
P
ROBLEM
7
Consider
the
following
tree.
Assume
that
the
neighbors
of
a
vertex
are
consid-
ered
in
alphabetical
order.
Figure
15:
A
graph
has
7
vertices,
a
through
g,
and
10
edges.
Vertex
e
on
the
left
end
is
horizontally
inline
with
vertex
g
on
the
right
end.
Vertex
b
is
below
and
to
the
right
of
vertex
e.
Vertex
c
is
above
vertex
e
and
to
the
right
of
vertex
b.
Vertex
f
is
between
and
to
the
right
of
vertices
c
and
b.
Vertex
f
is
horizontally
inline
with
vertices
e
and
g.
Vertex
a
is
above
and
to
the
right
of
vertex
f.
Vertex
d
is
below
and
to
the
right
of
vertex
f.
Vertex
a
is
vertically
inline
with
vertex
d.
Vertex
g
is
between
and
to
the
right
of
vertices
a
and
d.
The
edges
between
the
vertices
are
as
follows:
e
and
b;
f
b
and
c;
f
c
and
f;
f
c
and
a;
f
a
and
d;
f
b
and
f;
f
f
and
a;
f
f
and
d;
f
a
and
g;
and
d
and
g.
(a)
Give
the
tree
resulting
from
a
traversal
of
the
graph
below
starting
at
ver-tex
a
using
BFS.
The
BFS
Traversal
is
A
C
D
G
B
F
G
E.
(b)
Give
the
tree
resulting
from
a
traversal
of
the
graph
below
starting
at
ver-tex
a
using
DFS.
The
DFS
Traversal
is
A
C
B
E
F
D
G.
P
ROBLEM
8
An
undirected
weighted
graph
G
is
given
below:
(a)
Use Prim’s algorithm to compute the minimum spanning tree for the
weighted
graph.
Start
the
algorithm
at
f
vertex
f
a.
f
Show
f
the
f
order
f
in
f
which
f
the
edges
are
added
to
the
tree.
We
add
a
weight
of
2
to
edge
(a,e)
since
this
edge
has
the
minimum
weight
from
a.
We
then
add
a
weight
of
2
to
edge
(e,f)
since
this
edge
has
the
minimum
weight
from
a
and
e.
We
then
add
a
weight
of
1
to
edge
(f,d)
since
this
edge
has
the
minimum
weight
from
a,
e
and
f.
We
then
add
a
weight
of
5
to
the
edge
(e,c)
since
this
edge
has
the
minimum
weight
from
a,
d,
e
and
f.
We
then
add
a
weight
of
1
to
edge
(c,b)
since
this
edge
has
the
minimum
weight
from
a,
c,
d,
e,
and
f,
which
ultimately,
does
not
form
cycle.
(b)
What
is
the
minimum
weight
spanning
tree
for
the
weighted
graph
in
the
previous
question
subject
to
the
condition
that
edge
{
d,
e
}
is
in
the
span-
ning
tree?
We
add
a
weight
of
4
to
edge
(e,d)
since
we
have
reached
e.
We
add
a
weight
of
1
to
edge
(d,f)
since
this
edge
has
the
minimum
weight
from
a,d,
and
e.
We
add
a
weight
of
5
to
the
edge
(e,c)
since
this
edge
has
the
minimum
weight
from
a,
d,
e,
and
f.
We
add
a
weight
of
1
to
the
edge
(c,b)
since
this
edge
has
the
minimum
weight
from
a,
c,
d,
e
and
f
and
does
not
form
cycle.
(c)
How would you generalize this idea? Suppose you are given a graph G
and
a
particular
edge
u
{
,
v
}
in
f
the
f
graph.
f
How
f
would
f
you
f
alter
f
Prim’s
algorithm to find the minimum spanning tree subject to the condition that
{u, v} is in the tree?
Start
with
one
vertex.
From
there,
expand
the
tree
out
by
one
edge.
The
edges
that
won’t
connect
to
unless
the
minimal
weight
edge
is
found.
Con-
tinue
to
do
this
until
the
number
of
vertices
in
the
graph
have
been
added
to
the
tree.
