Hi,

I was wondering if anyone could help me with these Euler/Hamiltonian type problems;

Suppose we have a graph with 5 horizontal rows and 4 verticle columns

(G_(5,4))

So it looks something like:

Code:

*-*-*-*
| | | |
*-*-*-*
| | | |
*-*-*-*
| | | |
*-*-*-*
| | | |
*-*-*-*

All the horiz. edges have a weight of h and all the vertical ones have a weight of v, where both h and v are pos. numbers.

a.) Solve the TSP (Travelling Salesman Prob), that is: find a hamiltonian circuit (HC) of least total weight) if: h < v

b.) Solve the TSP, that is: find a HC of least total wght if: h > v

c.) Describe every m, n such that G_(m,n) has a HC

d.) Describe every m, n such that G_(m,n) has a Hamiltonian PATH.

2.) Eulerize G_(m,n) for every m, n >= 2. That is, what's the fewest # of edges you'll need to DUPLICATE such that the new graph will have an Eulerian circuit.