Chapter Review 419
(Another very important feature is how many "bottlenecks" there are in a graph. For
example, in the tree, all information from the left side to the right side must flow
through the root, making the root a bottleneck in the communication.)
- Use Fleury's algorithm to find an Eulerian circuit in each of the following graphs given
by the following adjacency list representation:
Vertices Lists of Adjacencies
1 2 3 4 6
Vertices Lists of Adjacencies 2 1 10 3 5
1 2 3 4 5 6 7 3 1 2 4 5
2 3 4 5 6 7 1 4 1 3 6 7 5 8
3 4 5 6 7 1 2 5 2 3 4 9 10 8
4 5 6 7 1 2 3 6 1 4 7 11
5 6 7 1 2 3 4 7 4 6 8 11
6 7 1 2 3 4 5 8 4 5 7 9
7 1 2 3 4 5 6 9 5 8 10 11
10 2 5 9 11
11 6 7 9 10
Fleury's algorithm is as follows:
(a) Choose an arbitrary vertex v and set W = v.
(b) Suppose that the trail Wi = v, vI .... vi has been chosen. Then, choose edge ei+1
from E - {el, e2 ... , ei} in such a way that
i.ei+l is incident to vi.
iiUnless there is no alternative, the removal of the edge ei+l does not disconnect
the graph remaining after isolated vertices are removed.
(c) Stop when part (b) can no longer be implemented.
- A Huffman code is a technique for compressing messages based on the frequency
of the characters that occur in the message. The procedure for creating a Huffman
tree starts by choosing the two characters with the lowest frequencies and creat-
ing a subtree with them as leaves. A character not in the message is used to name
the tree with the two chosen characters from the message as leaves. The special
character is given a frequency that is the sum of the frequencies of its leaves. The
process is repeated with the remaining characters augmented by this new character.
Draw the Huffman tree associated with the character with frequencies given in the
table:
ce 0.45
f6 0.07
y 0.12
3 0.08
E 0.15
" 0.13
