CHAPTER TEST 7

A. Give the definition of the following:

1. Graph
2. Degree of a vertex
3. Walk
4. Path
5. Trail
6. Parallel edges
7. Loop
8. Equivalent graphs
9. Complete graph
B. Let G be graph with V (G) = {1, 2, 3, 4, 5} and
E(G) = {[1, 2], [3, 4], [1, 4], [2, 5], [3, 5], [1, 3], [1, 5]}.
(a) Make a pictorial representation of G.
(b) Determine the order and the size of G.
(c) Construct a table for the degree of each vertex
C. Give an example of a graph G of order 6 and size 10 such that the
minimum and maximum degree of a vertex are 3 and 4 respectively.
D. Consider the graph G below. (2 pts each)
i. Find a walk of length 10.
ii. Find a closed walk of length 8.
iii. Find a path of length 5.
iv. Find a cycle of length 6.
v. Find a shortest path from a to e.
E. Give the definition of the following:

369
a............................................................b............................................................c..........................................................d
.............
... . .... . ... . .
... ... ... ...
.. .. .. ..
... ... ... ...
.. .. .. ..
.. .. .. ..
... ... ... ...
.. .. .. ..
j ...
. k ...
l ...
.......................................................................................................................................................................................................
. .
...
G: ... ... ... ...
e
.. .. .. ..
... ... ... ...
.. .. .. ..
... ... ... ...
.. .. .. ..
... ... ... ...
.. .. .. ..
. . . .
..................................................................................................................................................................................................
. . . . . . .

i h g f

i. Eulerian Circuit
ii. Eulerian Graphs.
iii. Hamiltonian Cycle
iv. Hamiltonian Graphs
F. Find a hamiltonian cycle in the given graph below. (10 pts each)

G. Give one example to each of the following graphs: (5 pts each)

a. Eulerian Graph
b. Hamiltonian Graph
H. Determine whether the graph below is a eulerian or not. Explain.
(10 pts)
I. Susan needs to mail a package at the post office, pick up several
items at the grocery store, return a rented video, and make a deposit

370
a............................................................b............................................................c..........................................................d
.............
... . .... . ... . .
... ... ... ...
.. .. .. ..
... ... ... ...
.. .. .. ..
.. .. .. ..
... ... ... ...
.. .. .. ..
j ...
. k ...
l ...
.......................................................................................................................................................................................................
. .
...
G: ... ... ... ...
e
.. .. .. ..
... ... ... ...
.. .. .. ..
... ... ... ...
.. .. .. ..
... ... ... ...
.. .. .. ..
. . . .
..................................................................................................................................................................................................
. . . . . . .

i h g f

Figure 5.43:

at her bank. The estimated driving time, in minutes, between each

of these locations is given in the table beow.
Use both of the algorithms(Greedy & Edge-Picking algorithms) to
design routes for Susan to follow that will help minimize her total
driving time. Assume she must start from home and return home
when her errands are done.

371
J. i. Draw a graph that represents the floor plan, where each vertex
represents a room and an edge connects two vertices if there is
a doorway between the two rooms.
ii. Is it possible to walk through the museum and pass through
each doorway without going through any doorway twice? Jus-
tify your conclusion.

K. Give the definition of the following: (3 pts each)

a. vertex coloring;
b. chromatic number.
L. Determine the chromatic number of the graph below. (10 pts)
a
.......
.............
.... .. ....
.. .... ... .......
.. . ....
.... ... ....
.... ... ....
.... .. ....
... ... .
.
....
....
..... .
. ....
..... .
.
. ....
........
f .................... ..
. .............
. b
.. ............. ... ............ ....
... .........
.........
.
.
. .........
.. ..
.
.. ......... . .
. .... .
... ......... ... ................. .
...
.............
H: ..
...
.. ...
.....
........ ..........
......... .... .................
.........
..
...
..
... ............. .
. .... ..
.
...... . .........
. .....
. . .
. ....................
e .................... ... ........ c
.... .
. ...
.
....
.... ... ....
.... ... ....
.... ... ....
.... . .. .....
.... . ....
....
.... ... ....
.... .... .......
.... . ....
............
.......

M. Eight different school clubs want to schedule meetings on the last

day of the semester. Some club members, however, belong to more
than one of these clubs, so clubs that share members cannot meet at
the same time. How many different time slots are required so that
all members can attend all meetings? Clubs that have a member
in common are indicated with an ??in the table below.

372
N. Six different groups of children would like to visit the zoo and feed
different animals. (Assume that each group will visit the zoo on
only one day.)
• Group 1 would like to feed the bears, dolphins, and gorillas.
• Group 2 would like to feed the bears, elephants,and hippos.
• Group 3 would like to feed the dolphins and elephants.
• Group 4 would like to feed the dolphins, zebras, and hippos.
• Group 5 would like to feed the bears and hippos.
• Group 6 would like to feed the gorillas, hippos, and zebras.
Use graph coloring to find the minimum number of days that are
required so that all groups can feed the animals they would like to
feed but no animals will be fed twice on the same day. Design a
schedule to accomplish this goal.

373