Homework 4

1.
           12
        c ---- f
      / |3     | \
 15 /   |     7|  |
  /     |  20  |  |
 |      b ---- d  |9
 |      |     /   |
 | 10-- |5 --     |
 | /    |        /
a ----- e ---- /
    1

a)

            
        c      f
        |      | \
        |3    7|  |
        |      |  |
        b      d  |9
        |         |
        |5        |
        |        /
a ----- e ---- /
    1

b) ae, eb, bc, ef, fd

c) (ae, bc, fd), (be, ef)

d) ae, cb, be, fd, ef


2.Since E = O(k^2) and N = O(k^2) all algorithms run in O( k^2log(k^2)).  By logarithmic reduction this can be presented as O( k^2log(k)).

3. No.  All vertices have odd degree.

4. 
a)

aebcfd
aebdfc
adbcfe
adbefc
acbdfe
acbefd

b)

aebcfd = 38 
(note: the value of a tour must include the edge to return to the start)