Discrete Mathematics for Computer Science

Exercises 389

(b)

log 2 (n!) = 1og 2 (n) + log 2 (n - 1) + + log 2 (n/2) + 1og 2 (n/2 - 1) +

+ log 2 (4) + log 2 (3) + log 2 (2) + log 2 (1)

> (n/2) log 2 (n/2) + (n/2) log 2 (2)

= (n/2) log 2 (n) - (n/2) log 2 (2) + (n/2) log 2 (2)

= (n/2)log 2 (n)

= (1/2)(n log 2 (n))

2 1og 2 (n!) > n log 2 (n)

Now, let c = 2 and No = 1. Since n log 2 (n) < clog 2 (n!) for all n > No, we conclude

n log 2 (n) E O(log 2 (n!)). 0

From Example 1, it follows that any sorting algorithm based on the comparison of a

pair of elements at each step will have the complexity given by a function at least as large

as c(n log 2 (n)) where n is the size of the input set and c E (0, 0).

Exercises

1. Construct all trees on six vertices. Find an algorithm for constructing all possible trees
   on six vertices if you know all possible trees on five vertices.


2. If the sequence dl, d2 ..... dn of nonnegative integers represents the degrees of the
   vertices of a tree with n vertices, then i=1 di = 2(n - 1). Show that the converse is
   false.


3. Let G be a tree with all vertices having odd degree. Prove that G contains an odd
   number of edges. Show that this is not true if G is not a tree.


4. Prove that a tree is a bipartite graph.


5. Use a graph to represent the possible paths through the maze shown. Use the graph to
   find a path from A to N.


6. Let T be a tree. Prove that if an edge e joins two nonadjacent vertices in T, then
   T U {e} contains a cycle.


7. Prove that any tree with two or more vertices has at least two vertices of degree one.


8. Prove that a graph T is a tree if and only if T is connected but the deletion of any edge
   disconnects T.